/ 最近 .rdf 追記 設定 本棚

脳log[Ruby: 2022-02-02~]



2022年02月02日 (水)

最終更新: 2022-02-11T22:02+0900

[Ruby] Ruby が謎に止まる。(解決済み)

先日解いていた「JOIG 2021/2022 本選競技課題」(テストケースのダウンロードができる) の F 問題へのこの提出に関して>20220129p01.05

Hash#shift を意味がある限り繰り返したあとで Hash#clear を呼ぶようにしている(25 行目)。shift は破壊的なメソッドだから shift を十分に呼び出した後の Hash は空になっているはずで、clear を呼ぶ意味はなさそうに思える。それでも呼ぶようにしているのは、これがないとテストケースの in/05-01.txt に限ってスクリプトの応答がなくなって TLE になると思ったから。少なくともローカル Windows 環境では Ruby-2.7 と Ruby-2.5 で止まる。Ruby-1.9 は平気。他のテストケースでは止まらないけど、問題のケースでは必ず止まる。止まるタイミングはバラバラだけど、いずれも Hash への代入で止まっているようだった。

再現スクリプトはこんな感じ(これを見つけたから日記に書いている)。他所で再現するかは、どうでしょうね。

Many = 100 # 10 回では少ない。テキトーに大きく。
Some = 100 # ウチでは 30 回目までは到達しない。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]

Some.times{|some|
	warn "#{some} begin"
	hash = {}
	Many.times{
		some.times{|j|
			k = Random.rand 0..Many
			hash[k] = 1 # maybe hang
		}
		0 while hash.shift
	}
	warn "#{some} end"
}
warn :exit

Ruby-2.5 と Ruby-2.7 では "N begin" (N は 20 前後) を表示して止まる。2.5 より 2.7 の方が早く止まるという傾向はあるけど、具体的な回数にはバラツキがある。それはまあ乱数を使ってるからだと思うけど、ハッシュのキーを k に代えて j にしたり、シャッフルした順列にしたりすると止まらなくなるので(正常動作)、乱数は外せない。

こういう Issue「Bug #17779: 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる - Ruby master - Ruby Issue Tracking System」を思い出したけど、全然関係はなさそう? 全然わからない。

AtCoder のコードテストを使わせてもらったら(目的外失礼)、こういう結果。AtCoder の Ruby も今のバージョンは 2.7。

終了コード9
実行時間10501 ms
メモリ9112 KB

標準エラー出力は 30 begin で途切れている。完走しても 10 秒もかかるはずないから、ハングして実行を打ち切られたのだと思う。コードテストとジャッジサーバーが同じだとして、ジャッジサーバーのスペックはこう>Linux ip-***-***-***-*** 4.15.0-1041-aws #43-Ubuntu SMP Thu Jun 6 13:39:11 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux*

 ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x64-mingw-ucrt]

Ruby-3.1 が「ウチの Ruby」に今日加わりました。大体ループの 20 から 30 回目で止まるんだけど、弾みで 2 回だけ完走したりもした。

 テスト(改訂版)

パラメータが2つもあると面倒なので。

改訂するにあたって予想外に止まらなくなったりした(正常動作)のを通して、たぶん直接的な原因もわかった。

# ウチではだいたい 20 から 30 回で "empty?: true" を最後にして止まる。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
# ウチの Ruby-3.1: ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x64-mingw-ucrt]

H = {}
100.times{|n|
	while H.size < n
		k = Random.rand 0..1<<30
		H[k] = 1 # たぶんここで止まる。
	end
	warn "size: #{H.size} before shifting."
	H.shift until H.empty?
	raise if H.shift # no exception. だけど Hash が空になった後の shift が後でハングをひき起こす?
	warn "empty?: #{H.empty?}"
}
warn :exit

Hash を空にする方法として 0 while H.shift を選ぶとその後の Hash#[]= でハングするが、Hash を空にする方法として H.shift until H.empty? を選ぶとハングしなかった。条件を揃えていくと、Hash#empty? が作用してハングを回避しているのではなく、Hash が空になったあとの Hash#shift がハングをひき起こしているようだった。ちなみに Hash#clear にハングを回避する効果があるらしいのは、JOIG の問題への提出で確認済み(とはもう書いた)。

 対応していただきました! (Bug #18578)

投稿して次に見たときにはすべてが終わっていた。早いぜ。

こういう仕組みだったようです。

メモ:entries_bound は使用中のビン(DELETEDになったビンを含む)の数に(ほぼ)対応していて、これをみてテーブルをリビルドしている(rebuild_table_if_necessary)。空のハッシュに対する Hash#shift はなぜか entries_bound を 0 にしているので、リビルドすべきタイミングを逃し、ビンがすべて使用中になった状態で空きビンを探そうとするので無限ループに陥っていた(find_table_bin_ind)。

* [[Language Test 202001 - AtCoder|https://atcoder.jp/contests/language-test-202001]]

 [[AtCoder 2019/7 Language Update - Google スプレッドシート|https://docs.google.com/spreadsheets/d/1PmsqufkF3wjKN6g1L0STS80yP4a6u-VdGiEv5uOHe0M/edit]]


2021年04月22日 (木)

最終更新: 2021-06-11T11:27+0900

[Ruby] 多重代入の評価順

以前書いた。「最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな? 右辺の一時記憶が必要? 多重代入は遅くて時々評価順が難しい、というのが現在の評価。」「クイズです。a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあ

そしてこの PR が多重代入について>Evaluate multiple assignment left hand side before right hand side by jeremyevans · Pull Request #4390 · ruby/ruby マージされている。

3.1.0 から変わりそう? 評価順が変わってパフォーマンスがさらにちょっと遅くなる? 新しい評価順っていうのが、

  1. 左辺の変数、レシーバ(メソッド引数も?)を左から
  2. 右辺の値を左から
  3. 左辺の変数代入、代入メソッドを左から

従来は2が最初にあって、1と3がインターリーブされていた。……ということが PR の概要欄と NEWS の修正に書いてある。

パフォーマンス劣化の理由は左辺の評価結果を一時的に蓄える必要があるからか?

いやあ、あっさり変えるし変えられるもんなんだなあ。まあたぶん、Ruby ユーザーの 1 % も変化に気がつかないだろうとは思う。

 新展開@2021-05-06

  1. https://bugs.ruby-lang.org/issues/4443#change-91847
  2. https://bugs.ruby-lang.org/issues/15928#note-10

非効率だしバグらせやすいし、作り込む価値がないと言っている?

自分はもうこの仕様について(穴にはまった実体験から)知っているので、常に穴を意識して書くし、逆に評価順を利用することもあるけど、これまで幸運にも意識せずに来られた大多数のユーザーが、将来的潜在的には驚きとともに多重代入の評価順の詳細を理解させられるんだろうな、ということを考えると、「作り込む価値はある。ただしうまく実装できる限りにおいては」という評価が妥当かなと思う。


2020年11月24日 (火)

最終更新: 2020-12-08T00:48+0900

[Ruby] 多重代入の難しさの一例。(Ruby 2.7 と Ruby 1.9 で確認)

4月に「多重代入は遅くて時々評価順が難しい」と書いたけど、さらに難しいケースを考えた。クイズです。

a = *0..5 #=> [0,1,2,3,4,5]
b = *0..5 #=> [0,1,2,3,4,5]
a[i=2] #=> 2
b[j=2] #=> 2

a[i+=1] = a[i] # a はどうなる?
b[j+=1],= b[j] # b はどうなる?

a #=> [0,1,2,3,4,5]
b #=> [0,1,2,2,4,5]

a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあと、それが遅くなる理由かなあと、思いました。

ゴルファーしかこんなコードを書こうとはしない? その通り。


2020年09月30日 (水)

最終更新: 2021-01-19T03:44+0900

[Ruby] 平衡二分探索木

 前置き

最近こういう記事を読んだ(20200912p01)。「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita

その少し前に雰囲気で書こうとしたけど、バランスの取り方に対する理解が雑で完成しなかった(20200604p01.04)。

Ruby の標準添付ライブラリにある SortedSet は内部構造がハッシュテーブルでありキーの順序付けが利用できない。ありていに言えばキーの二分探索をしたいができない。「RBTree ライブラリ (https://rubygems.org/gems/rbtree) が利用可能である場合、内部記憶としてハッシュの代わりに RBTree を使用します 」ということが書いてあるけど、RBTree が利用可能だったことがない。

 再挑戦した。sset.rb (3.8 KiB)

  • SortedSet と食い違いが見つかるまで無限ループさせてみたけど、限られた範囲のキーと限られた時間では止まらなくなった(こういうときはテストの失敗を疑う。だから最初に失敗するテストを書いて、それを満足させるように実装を埋める)。
  • 性能はまったく期待できない。まったく。

    注意すれば省メモリにはなるかもしれないけど、出し入れのたびに配列の全長のおよそ半分を右へ左へ動かしていたのでは、他に何も期待できない。

    注意を要するのは rotate_l/rotate_r の実装。このとき(20200905p01.07)のように、不必要に膨大なメモリ要求が実行速度まで低下させかねない。

    すばらしき(20200912p01.03) Array#fill メソッドにならって、Array#rotate も第2引数以降を使って対象範囲を受け付けたらいい。

  • 内部構造は「社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど」(20200607p01.02)と書いたときのものと同じ。

    その後の検索で「最小共通祖先 [いかたこのたこつぼ]」というページを見つけて、「LCA」「オイラーツアー」という用語を仕入れている。そんな感じの構造。

    ちょっと待て、このドメイン名は……。20200905p01.03 で参照した AtCoder の ikatakos さんと同じでは?

  • 苦労の 70 % くらいは sink と push の2メソッドを見出すところにあった気がする。実装することではなくシグニチャを発見するまでのところに。でも、どういう操作が必要か、どういう操作であれば十分か、実装を始めてデバッグをする過程でしか見つけられないジレンマ。

    以前にも似たようなことを書いている。「メソッド名を決めるまでで 9割が終わってる。」 そのときはその後の検索で「最小全域木」「プリム法」「クラスカル法」という用語を仕入れてクラスカル法で再実装しているが、今回はどうか。AVL木とか赤黒木とか知らないよ?>「平衡二分探索木 - Wikipedia

  • key の順序(SSet#index(key))と内部配列の添字の変換に何か魔法がないものか。ありそうではないか。
    • 最大値と最小値を蓄えている内部配列における位置は計算で求まることがわかった。
    • ソート列における順序と内部配列における添字という、2つの数字を元にして each メソッドが簡略化できそうな気がする。したい。

      つまり、現在の向き(行きか帰りか)と次の添字がわかるならスタックがいらなくなる。開始点(最小値の添字)はもうわかっている。

あっ、これ二分探索のためにあらかじめ並べ替えたソート済み配列だ(いま気がついた)。Array#bsearch_index と Array#insert で済むものをよくも難しく書き直したものだ。

メモリブロックの移動を減らすためにギチギチに詰め込まないでルーズに管理しようとしたら、固定長の大きさを持っていて最大値と最小値で特徴付けられる疎な配列(リスト)の入れ子構造に行き当たって、ピボットはいらないな、そうするとこれ木じゃないな、ただの(入れ子になった)ソート列になっちゃったな、と。じゃあ原点に戻ってあれも(並べ方が素直じゃないだけの)ソート列だな、と気がついた次第。

持っていることも忘れていた『[単行本] K. メールホルン, P. サンダース【アルゴリズムとデータ構造―基礎のツールボックス】 シュプリンガー・ジャパン株式会社』をぱらぱらめくってると、(a,b)-木という構造があって、これは木の各ノードが最長で長さ b の子ノード列を持つらしくて、つまりは入れ子になったソート列なんだけど……。

入れ子になったソート済み配列もやっぱり木?


2013年04月14日 (日)

最終更新: 2013-04-15T03:23+0900

[SakuraEditor][Ruby] サクラエディタBBS[7601]

  • Editor定数の参照で落ちる。他の名前なら問題なし。
  • $Editorとすることで Editorオブジェクトが得られる。
  • マクロコマンドは先頭を小文字にしないと呼べない。(TraceOut→traceOutなど)
  • Editorオブジェクトに SCRIPTITEM_GLOBALMEMBERSフラグが付いてると、Rubyマクロのばあい ITypeLibが必要になる。(ITypeInfo->GetContainingTypeLibを実装する必要がある)
  • ITypeInfo->GetFuncDescがマクロコマンドの数(271)×3回、マクロを実行する前に呼ばれる。
  • 3回目に取得された ITypeInfoがリリースされない。
  • Editorオブジェクトもリリースが足りない。
  • 実行の成否にかかわらず一回につき 100KBぐらいメモリ使用量が増える。
  • リソースリークをなくしたければ参照カウントを捨てて、マクロ実行の前後ですべてのオブジェクトの作成・破棄を行うのが確実。
  • 12回目のマクロ呼び出しが必ず失敗する。例外が発生しているもよう。
  • TYPEATTR.cFuncsの数を減らしてマクロコマンドの数をごまかすと 11回を超えて成功するようになったり。リリースモードにしても回数は変化する。
  • 失敗しても繰り返しマクロを実行してるとときどき成功する。
  • マクロ実行に失敗するとき、IActiveScriptParse->ParseScriptText直前の IActiveScript->SetScriptState(SCRIPTSTATE_STARTED)呼び出しから足取りがつかめなくなる。
  • SetScriptStateを飛ばして ParseScriptTextを実行するようにすると例外はなく、正常にエラーメッセージ("実行に失敗しました")が表示される。なんにせよ失敗。
  • スクリプトエンジンをマクロ実行ごとにきれいに片付けられていれば、○回目から失敗みたいなことは起こらないと思うんだけど。なにが継続しているのか、あるいはこちらの何が破壊されていってるのか。

どうせ Rubyマクロはコマンドの先頭を小文字にする必要があって他のマクロと同じように書けないのだし、使われてないからこれまでに書かれたマクロ資産との互換性を図る必要もないし、例外とリークの元になり実行前の負荷も発生させる SCRIPTITEM_GLOBALMEMBERSフラグを落とすのがいいと思う。ScriptEngine名が "RubyScript." で始まるときとかに限って。

SCRIPTITEM_GLOBALMEMBERSフラグを落とすと $Editor.insTextだけのマクロは何十回でも問題なく実行できてるけど、それだけで安心してよいものか。Editorと書いたときのように(数字で始まるマクロコマンドを呼んだときも?)初回で確実に落ちるというだけならいいけど、何回も実行してるうちに運が悪ければ落ちるというのがあれば(たち)が悪い。


2013年02月13日 (水) 見られてる。わかってるのに何度でも振り向いてしまう。PERSIは美猫だにゃー。■パーシーって読んでる(呼んではいない)。■目。赤外線で目をポイントするとこちらへ焦点を合わせるようなギミックはないものか。ありそうなのは赤外線より磁石かな。近づける、動かす、方向を保ったまま遠ざける。グラスアイの追視は運要素が強すぎるよ。■■■もう一体。乳首と爪を同じ色で塗ろうかとものぐさな計画をたてていたが、これが思いがけずエロティックな想像だった。だって、爪を見られるとき乳首を見られてるような気持ちになるってことだ。<おっさん自重。■せっかくの球体関節人形(※英語だとball-jointed dollとかいうんだろうか。雰囲気台無し。ガンプラみたいだ(子供の頃は混在期で2種類のグレーのポリキャップのどちらかが使われていた。新しいものにボールジョイント))なんだから膝が見える丈のスカートがいいね。■■■美猫ってびびょうって読むんだろうか。イメージ喚起能力に乏しいしきれいな音でもないけど、美人や美姫も先入観を取り除けば似たようなものか。何も考えないとびねこって読みたくなる。みびょうの可能性もなくはないかなと思うが予防医学か漢方のイメージが先に立つ。みねことなると誰かの名前みたいだ。■228「「美猫」に振られるルビは「びじん」 これ常識なw ソースは「綿の国星」とかw」228が大正解w■■■前からちらちら物色してるんだけどデジカメが欲しくなるなあ。三脚も必要だ。重視したい機能は GPSとヒトの目を超える分解能と目を見開かされるような解像感。(セクション3へつづく)

最終更新: 2013-02-22T00:42+0900

[Ruby] どうしていいのか困り果てるバグに当たったのでバージョンアップする。

日本語を含むフルパスを File.expand_pathすると、文字列そのものは変化しない(ように見える)のにファイルを見失う。

C:\>irb19
irb(main):001:0> File.directory? "C:/コピー"
=> true
irb(main):002:0> File.directory? File.expand_path "C:/コピー"
=> false
irb(main):003:0> "C:/コピー" == File.expand_path("C:/コピー")
=> true
irb(main):004:0> RUBY_DESCRIPTION
=> "ruby 1.9.3dev (2011-09-23 revision 33323) [i386-mswin32_100]"
irb(main):005:0> $:
=> ["C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/site_ruby/1.9.1", "C:/Program Fi
les (x86)/ActiveScriptRuby-1.9/lib/ruby/site_ruby/1.9.1/i386-msvcr100", "C:/Program Files
(x86)/ActiveScriptRuby-1.9/lib/ruby/site_ruby", "C:/Program Files (x86)/ActiveScriptRuby-1
.9/lib/ruby/vendor_ruby/1.9.1", "C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/vend
or_ruby/1.9.1/i386-msvcr100", "C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/vendor
_ruby", "C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/1.9.1", "C:/Program Files (x
86)/ActiveScriptRuby-1.9/lib/ruby/1.9.1/i386-mswin32_100"]
irb(main):006:0>

ところで Rubyは Unicode文字を含む(Shift_JIS(※)に含まれない文字を含む)パスを扱えるようになっているだろうか。方法はあるけどやり方を間違えていただけだろうか。


2009年に書いた自分のスクリプトをきちんと動くようにしようと引っ張り出してきた。Rubyの対象バージョンを 1.8から 1.9.3にして ruby-mp3infoを GitHubからダウンロードしてきた最新版に差し替えただけで肝心な部分はほとんど終了。それにしても、4年前の自分がきっちりボトムアップでプログラムを構造化していたことに驚いた。最近 PRS-650のために書いたスクリプトとは比べられない。Rubyは、こうあるべきと書き手が考えるソースコードの流れを比較的自由に表現できる言語であるから、言語の制約を気にせず頭の中に理想形を持っておくのが大事。クラス構文があるからクラスを作るんでなく、こう書きたいという欲求を満たす選択肢としてクラスがある。理想の有無が同じ書きたいように書いた結果に雲泥の差が生じる理由。忘れてた。


このバグだ。>Backport #5629: Windows環境で日本語を含むパスに対して、File.expand_path が存在しないパスを返すパターンが存在する。 - Backport93 - Ruby Issue Tracking System。一年前に 1.9.3にバックポートされて解決してる。Ruby-1.9.3-p385にアップデートするにはいいタイミングだったし、都合のいい理由付けになった。


似たような問題がまだ requireに残ってたみたい >Bug #7881: Windows でパスに日本語を含むスクリプトからの require が失敗する - ruby-trunk - Ruby Issue Tracking System

最終更新: 2013-03-03T06:08+0900

[Ruby] moumar/ruby-mp3info at 9e08852356ff46716d00fac3b553904c8ea503d3 · GitHubに加えた変更点。

  • ID3v1がもともと存在しないファイルに ID3v1を付け加えないように。removetag1してさえ ID3v1が書き出されて困惑した。<<同じ対応を ID3v2にもとったらタグなしの mp3ファイルにタグをセットすることができなくなる。v1が v2がと気にするのなら tagでなく tag1と tag2を使い分けるべきなのかも。でも "universal tag"を使いたいのだよね。もともと v1と v2を両方書き出していたけど v1があると v1を優先してしまう困ったソフトがあるために v2だけにしたい、という今の自分がおかれた状況で、タグを操作する部分から tag1に関連する部分を削除してまわるというのはうまい考えではない。使用するソフトが変わってやっぱり v1もあった方がいいとなったらどうする?タグ操作は universal tagで共通化したい。なら、universal tagを制御するフラグが足りてないように思う。
  • tag["tracknum"]を文字列として扱い、ID3v1に書き出すときにだけ to_iするように。文字列で扱った方が(全体で何トラックあるのかという)情報のロスがないので。
--- ruby-mp3info-master\lib\mp3info.rb~	Wed Feb 13 16:34:42 2013
+++ ruby-mp3info-master\lib\mp3info.rb	Wed Feb 13 20:48:38 2013
@@ -272,7 +272,7 @@
             next unless tag_value
             @tag[key] = tag_value.is_a?(Array) ? tag_value.first : tag_value
 
-            if %w{year tracknum}.include?(key)
+            if %w{year}.include?(key)
               @tag[key] = tag_value.to_i
             end
             # this is a special case with id3v2.2, which uses
@@ -381,7 +381,7 @@
       puts "@tag has changed" if $DEBUG
 
       # @tag1 has precedence over @tag
-      if @tag1 == @tag1_orig
+      if @tag1 == @tag1_orig && ! @tag1.empty?
         @tag.each do |k, v|
           @tag1[k] = v
         end
@@ -418,7 +418,7 @@
             ((@tag1_orig["year"] != 0) ? ("%04d" % @tag1_orig["year"].to_i) : "\0\0\0\0"),
             @tag1_orig["comments"]||"",
             0,
-            @tag1_orig["tracknum"]||0,
+            @tag1_orig["tracknum"].to_i,
             @tag1_orig["genre"]||255
             ].pack("Z30Z30Z30Z4Z28CCC")
           file.write(str)

 利用側でのモンキーパッチング

Vistaの Windows Explorerでタグを書き換えると encoding_indexが 0(iso-8859-1)になるんだけど、これを信用して変換すると日本語文字が化けるので Windows-31Jにしてみた。

require "mp3info"
ID3v2::TEXT_ENCODINGS[0] = "Windows-31J"

2011年09月30日 (金)

最終更新: 2011-10-01T04:28+0900

[Ruby] Google Code Jam Japan 練習問題

練習問題。それも Aだけ。Bは撃墜されました。

# small用
def last_output(n, k)
	snappers = [false] * n
	k.times{
		# 電流をたどってひっくり返す。
		0.upto(n-1){|i|
			snappers[i] = ! snappers[i]
			break if snappers[i] # previously OFF (=next snapper's IN was OFF)
		}
	}
	return snappers.all?
end

# large用
def last_output(n, k)
	# k1 = 2**n-1 # k1:最初に n個の snapperがすべて ONになる操作回数.
	# k = p*k1+(p-1) を満たす自然数pが存在するなら電球は ON.
	return (k+1)%(1<<n) == 0
end

caseno = 0
$stdin.readline; # drop # of cases.
$stdin.each_line{|ln|
	n,k = *ln.scan(/\d+/).map(&:to_i)
	break unless k
	caseno += 1
	puts "Case ##{caseno}: #{last_output(n,k)?'ON':'OFF'}"
}

2011年05月19日 (木) Logicoolの製品情報ページ。URLのフラグメント(ハッシュの後ろ)と onclickハンドラで小賢しい見た目の操作をしてるけど「戻る」に対応していない。読み手の感覚として明らかにページ移動をしている(ヘッダ・フッタといったテンプレートを除いてページ全体が書きかわってる)のに、URLが変わっておらず履歴にも残っていないからだ。枝葉にこだわるなら徹底的にやりな。一方ダイソンは……クエリストリングを使い、スクリプトが有効ならページを動的に書き換え、無効化されていても情報を表示できないなんて間抜けはおかさなかった。何が主で何が従かがわかってる。

最終更新: 2011-05-19T13:48+0900

[Ruby] lostと lots of? だとしても informationに lots?

7. In app code, never use force_encoding to convert BINARY data into a particular encoding. By the time you've reached app code, you have lost the information about which encoding is being used. Instead, find where the String came into Ruby, and fix it to set up the encoding based on the information it knows.

アプリケーションコードの場合、バイナリデータを特定のエンコーディングに変換するために force_encoding を決して使わないこと。アプリケーションコードをいじっているのであれば 使用されているエンコーディングに関する情報をたたくさん持っているはずである。 この場合、その文字列がどこからRubyにやってきたかを突き止め、わかっている情報に 基づいてエンコーディングを設定するように修正すること。

いまもって Ruby 1.9のエンコーディングに関するベストプラクティスがわからないので、すごくためになるリスト。7はこう理解した。

(文字列のエンコーディング情報が失われた)末端コードで、(その場で必要とされるエンコーディングに基づいて場当たり的に) force_encodingしないこと。その文字列の来歴をたどって一番根っこ(※ライブラリの修正が必要かも)で正しい情報(※ないのなら慣習に従うか、その不完全なプロトコルを捨てる)に基づいて force_encodingすること。(末端コードで必要に応じて行うのは encodeだったり encode!)


2011年04月11日 (月)

最終更新: 2011-04-16T21:35+0900

[Ruby] 「HsbtDiary(2011-04-11) rubygems の taint と LOAD_PATH と $SAFE について

前にこうならんかな?って書いたのをもう一度。

require 'hoge'

したときに hoge.rbなり hoge.soなりが taintedな $LOAD_PATH要素に基づいて発見されたときは SecurityError。見つからなければ taintedな要素はスルー。という動作を Rubyに期待したい。今は taintedな $LOAD_PATH要素を無造作に File.expand_pathして SecurityErrorが起こるに任せているんではなかったか。


 @2011-04-16 Ruby 1.9.2p136と 1.8.7p330で挙動が違うのが SecurityErrorへの疑問を増す。

1.9.2では(確かめたわけではないけど)汚染されたパスの展開がセキュリティエラーにつながってるから、汚染されたパスが $LOAD_PATHの末尾にあった場合は $SAFE=1の状況下で require 'cgi'が成功する。require '存在しないファイル'はセキュリティエラー。汚染されたパスを基に展開を試行したかどうかが分かれ目。

1.8.7では $SAFE=1の状況下で汚染された文字列を引数にした File.expand_pathは 1.9.2と違い成功するものの、上のような場合でも require 'cgi'に失敗する。これは requireが内部的に File.expand_pathを呼び出し――これは 1.9.2とは違いセキュリティエラーを起こさないけれど 1.9.2同様汚染された文字列を返す――、その汚染された戻り値を使った require_internal(仮名)が 1.9.2とは違い $SAFE=1のときにセキュリティエラーを起こしてるのだと思う。挙動からの推測。

一貫性が欲しかったね。できれば実用的なものが。特定のディレクトリ(汚染された$LOAD_PATH要素)に特定の .rb, .soファイル(requireされたファイル)があるかないか判った(SecurityError or not)ところでどうだというの。


2011年03月12日 (土) combinationメソッドを調べるために Ruby 1.8.7のドキュメントを少し読んだ(常用のリファレンスは20051129だ)。choiceから sampleへの名前変更は良かった。choiceは意思を明らかにする行為だと思うからランダム抽出とは相容れないよ(それとも神の選択か)。「Ruby 1.8.8 以降では Array#sample を使ってください。」 Ruby 1.8.8 は出るんでしょうか?

最終更新: 2011-03-15T00:15+0900

[ProjectEuler][Ruby] Problem 71, 72

 Problem 71

「HCF(n,d)=1」には用語の説明があると思ったんだけどなかった。n/dの nと dは最大公約数が 1の既約分数だとすると意味がとおるので HCF=Highest Common Factorだと決めた(でっちあげ)。

分数とはなんぞやだとか切断だとか小難しく考えてしまったが(実際には考えられるほど知らない)、ワンライナーだった。3/7より少し小さい100万個の分数を小数になおして、一番小さいものを見つける。有理数にして比較しないのは時間がかかるから。公約数をみつけたりする時間だろうか。

require 'rational'
p Rational(*(2..1_000_000).inject([0,1]){|answer,d|
	answer[0]/answer[1].to_f < (d*3-1)/7/d.to_f ? [(d*3-1)/7,d] : answer
})

 @2011-03-14 なにこれ!

Project Euler Problem #71 « KeyZero Conversation

分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか!

 Problem 72

分単位のお時間がかかります。(訳:一時間はかからないけど……)

何倍も速くなるので「Integer#prime_division」を使う代わりに 100万要素の配列を使ってる。トレードオフで使用メモリは数MBから 100MB超になるが。 小手先のチューンよりアルゴリズムを改良しろってのはもっともだけど、かなしいかな、できることとできないことがあるのです。

LIMIT = 1_000_000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
	print d,"\r"
	count += d-1 # 1) とりあえず d-1 通りの分子を計上し、
	d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
	# 2) 8分の6など通分可能なものを差し引きする。
	(1..(pfs[d].size)).each{|r|
		cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
		count -= (-1)**(r%2+1) * cms.map{|cm| (d-1)/cm }.inject(&:+)
	}
}
p count

Ruby 1.9からバックポートされてきた(のだと思われる見覚えのないメソッド) cycle, tap, combination, permutation, productといったメソッドが便利だ。あとは自然数を無限に生成し続ける無限リストのようなものをどれだけ簡単に書けるかだ。なにかショートカットがあるのだろうか。これでは長すぎる。

Enumerable::Enumerator.new(lambda{|&block| n=0; loop{ block.call n+=1 } }, :call).each{|x| p x }

それと、block.callの部分を yieldにできないのもわかりにくい。Procと blockと lambdaの微妙な違いによるものなのだろうか。

Rubyによる他所の Project Eulerの解答をみていてこういう書き方も知ってるけど、カウンタが Floatになっちゃうのが不満。

1.upto(1/0.0){|n| p n }

あれ? Fixnumだ。Floatになるのは stepだった。

1.step(1/0.0){|n| p n } # 1.0, 2.0, 3.0,...

明示的に Fixnumの増分: 1を指定しても n は Float. この違いはなんだろう。


cycleの使い道として zipを想定していたが拒否されてしまった。

irb> [1,2,3,4,5].zip([0])
=> 1, 0], [2, nil], [3, nil], [4, nil], [5, nil
irb> [1,2,3,4,5].zip([0].cycle)
TypeError: can't convert Enumerable::Enumerator into Array
        from (irb):2:in `zip'
        from (irb):2
        from :0
irb> RUBY_DESCRIPTION
=> "ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32]"

2010年07月30日 (金)

最終更新: 2012-11-01T13:41+0900

[SakuraEditor][SHJS][Ruby] Rubyの %リテラルの色分けを修正。

説明が面倒なのと誰も知りたくないだろうから適当に、備忘のためだけに。

  1. まさか %{literal}literal部分で \{\} を使う人間がいるとは思わなかった。(違う種類の括弧を使えばいいじゃない。開閉の釣り合いがとれてれば同じ種類の括弧でもエスケープ不要だし)
  2. だのに Ruby1.9の rake.rbにこんなパターンが……

    %r{[*?\[\{]}
  3. エスケープされた { 2のはの考慮がないから、閉じ括弧が足りないとしてファイル末尾まで正規表現として色分けされてしまう。
  4. ちょちょちょいと .rkw2ファイルにエスケープ文字を追加してサクラエディタに対する修正は完了
  5. SHJSの lang/sh_ruby.js(自作)への対応も同じですむはずが、入力の末尾に達した時点で意図せぬバックトラックが発動し、閉じ括弧が足りなくても色分けが適当な閉じ括弧で終了してしまう現象に遭遇。これは自業自得(20090808p01)なので自分でなんとかせねば。間違いが埋没してしまうのはよろしくない。
  6. こうした

    %r{余分な開き括弧{。間違いはインタープリタを通す前から目立つように}

2のは Rubyインタープリタに対するエスケープ、と同時に正規表現パターンとしてのエスケープですよ。%r[\[] と /\[/ が同じパターンになって、%r[[] がRubyのシンタックスエラー、/[/ がパターンのコンパイルエラーになるんだから。(ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32] / ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-mswin32])


2010年04月21日 (水)

最終更新: 2010-04-22T02:07+0900

[Ruby] 「まつもと ゆきひろのRuby検定 - ITpro EXPO検定---ITpro EXPO 2008:ITpro

やってみた。Time.parseの問題がわからなかったのと、ブロック変数が外のローカル変数を変更してしまうかどうかという問題(Rubyのバージョンは?回答形式が)以外はたぶん問題なし。で、回答を送信すると一分かそれ以上待たされた後、「一度しか回答できません」だって。ええええ。たしかにそう書いてあるのは読んだけど、以前回答したことも忘れてるんですよ。そんなこと言われても。

そういう要求をするのも、それを額面通りに実施してしまうのも、ある意味感心するけど首を傾げてしまう。回答は適当に受け付けて、後でフィルタリングしてから利用すればいいじゃない。とここで「すでに受験した方は,前回の回答結果を参照できます。」とも書かれてるのに気付いた。ログインを要求されたから見られなかったけど、回答を(回答者の要求に応じて参照できるようにしながら)抱え続けるのって誰得? Ruby検定の予想問題からのピックアップに過ぎないんですよ、この問題って。

回答形式が 一つ選べという問題だったのにチェックボックスが使われていた。他は問題形式によってラジオボタンとチェックボックスが適切に使い分けられていたから、出題形式を間違えたかフォームを間違えたか後でフォームだけ変更されたか。はてさて。


2010年04月05日 (月) とうとう Refererスパムも来始めた。コメントスパムの方も、NGワードが設定されていることを察知するのか vigraとか ciallisだとか微妙にキーワードを変えてきている。こういう段階的対応が自動化されてたらこっちはたまったもんじゃないよ。

最終更新: 2013-08-20T01:04+0900

[Ruby] 「少なくとも優秀ではない」ことを否定する(≠優秀である)。

makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ」経由で「人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか

粘菌でも迷路問題を解けるというのだから負けてはいられない。Rubyで一時間半弱かかった。

#! ruby
# coding: Shift_JIS

# 迷路データ

maze = <<MAZE
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
MAZE

# マップ

class Point
	def initialize(x, y)
		@x, @y = x, y
	end
	attr_reader :x, :y

	def ==(other)
		@x == other.x && @y == other.y
	end
	def to_s
		"(#{@x},#{@y})"
	end

	def left
		Point.new(@x-1, @y)
	end
	def right
		Point.new(@x+1, @y)
	end
	def up
		Point.new(@x, @y-1)
	end
	def down
		Point.new(@x, @y+1)
	end
end

class Map
	def initialize(maze)
		lines = maze.strip.split(/\r\n?|\n/)
		@height = lines.length
		@width = lines.first.length
		y = -1
		@map = lines.map{|line| y += 1
			x = -1
			line.split(//).map{|ch| x += 1
				if(ch == 'G')
					@goal = Point.new(x, y)
					nil
				elsif(ch == 'S')
					@start = Point.new(x, y)
					nil
				elsif(ch == '*')
					-1
				else
					nil
				end
			}
		}
	end
	attr_reader :height, :width
	attr_reader :start, :goal

	def []=(point, value)
		@map[point.y][point.x] = value
	end
	def [](point)
		@map[point.y][point.x]
	end
	def up(point)
		return -1 if point.y-1 < 0
		return @map[point.y-1][point.x]
	end
	def down(point)
		return -1 if self.height <= point.y+1
		return @map[point.y+1][point.x]
	end
	def left(point)
		return -1 if point.x-1 < 0
		return @map[point.y][point.x-1]
	end
	def right(point)
		return -1 if self.width <= point.x+1
		return @map[point.y][point.x+1]
	end
end

map = Map.new(maze)
#puts "width×height = #{map.width}×#{map.height}"
#puts "start:#{map.start} / goal:#{map.goal}"

map[map.goal] = 0;
#puts "goal=#{map[map.goal]}"

# 先端

nodes = [map.goal]
while node = nodes.shift
	next if node == map.start
	[node.left, node.right, node.up, node.down].each{|nxt|
		case(map[nxt])
		when -1
			# 壁
		when nil
			# 未踏
			map[nxt] = map[node] + 1
			nodes.push(nxt)
		else
			# 既に到達したルートがある
			if(map[node] + 1 < map[nxt])
				map[nxt] = map[node] + 1
				nodes.push(nxt) unless nodes.include?(nxt)
			end
		end
	}
end

# Map to result

map.height.times{|y|
	map.width.times{|x|
		point = map[Point.new(x,y)]
		print point == -1 ? '***' : ("% 3d"%point)
	}
	puts
} if false

result = maze.strip.split(/\r\n?|\n/)

node = map.start
until node == map.goal
	[node.left, node.right, node.up, node.down].each{|nxt|
		if(map[nxt] == map[node] - 1)
			node = nxt
			result[nxt.y][nxt.x] = '$'
			break
		end
	}
end

puts result.join("\n")

ノードっていうのはひとマスのこと。「先端」っていうコメントが適当すぎる(植物では頂端分裂組織っていうらしい)。方針はゴールからスタートに向けて、一マス移動するごとに一ポイントを加算しながら全方位に触手を伸ばしていき、すでに他の触手が通過した道は、自分が最適な場合にのみ侵入するこの判断は不要。全ての触手が行き場を失うかスタートに到達するかしたら終了。スタートから一ずつ減っていく数字をたどると(一少ない数をもつ隣接マスが二つ以上あっても解答に求められていないので無視する)ゴールへ着き、それが最短経路(だったらいいな)。

最初は粘菌方式をまねようと思ったが、通路をすべて覆った状態からスタートして、スタートとゴールにつながっていない島を切り捨て、袋小路から撤退するのはいい。遠回りと近道を取捨選択するためにどういう評価をすればいいのかを決められなかった。どうすればいいの?粘菌は何を考えてる?例えば


二番目のリンク先のトラックバックを見てる。みんな優秀なのね、C++で一時間もかかってないし。何人かが言及している「BFS」。それって一般的知識? 幅優先探索(Breadth-First Search)か最良優先探索(Best-First Search)の略だということはわかった。


壁のもつポイントを -1 に設定したことで、壁に侵入しないことを保証する when節を省略してもよかったんじゃないだろうか。気付くのが遅れたが。


ゴールにも $ って書き込んでら。(スタートには書きこまんように気をつけたんだが)


粘菌すごい。

培地に、三個以上の餌を置く。粘菌は迷路の実験のように最短距離を結ぶか?

結果は違った。

粘菌は、丸く、複数の経路を持つ管を作った。「最短経路だと一カ所故障したら必ず孤立する場所が出ます。だから粘菌は、一カ所が故障しても全体はつながり、なおかつ距離がなるべく短い経路を作ったのです」

部分部分がどういう反応をするとそういう結果になるんだろ???


 @2013-08-19 こういうことらしいです。わかりません。

粘菌の行動原理は、量子ドット間の近接場光を介したエネルギー移動プロセスに類似している

この判断は不要 @2010-04-11 不要だったらしい。ノードリストが FIFO(=push/shiftを使う=幅優先)なら起こりえないみたい。

例えば 粘菌が電気を好む抵抗(集まると抵抗が下がる)だとしてスタートとゴールに電圧をかけるイメージ?

本日のツッコミ(全2件) ツッコミを入れる

BorsJoigreeBS GE VC KX LJ UZ ZY RW MS IS ML JE AL FWUN BR EJ AV DD XQ..

ds14050解析班はどこだ?