GNU globalすげぇ。
GNU globalが気になったので使ってみた。
何といっても凄いのは、「global -r hoge」で参照元に飛べる点。コードリーディングには必修です。
Vimとの連携は以下を参照。
うちの環境では、/usr/share/gtags/gtags.vimにプラグインが入ってた。パッチを当てないとエンターで飛べないので当てた方がいい。
タグの作成は、
% gtags
これだけ。簡単杉。
:Gtags -r malloc dir.c|957| #define GLOB_ALLOC(type) (type *)malloc(sizeof(type)) dir.c|958| #define GLOB_ALLOC_N(type, n) (type *)malloc(sizeof(type) * (n)) dln.c|1877| vms_filespec = malloc(strlen(filespec)+1); ...(略
mallocがどこで使われているかわかる。対応言語が少ないのが残念だけど、参照元を見たいときはGNU global。
あんまり意味が無いけど、zshの補完もヤバい。
% global -t m<tab> main match_string method_inspect main_thread match_to_a method_missing
ステキ過ぎる。
Rubyで配列のランダムソート
Rubyでランダムソートをしようと思ったら、色々な発見が出来た。試行錯誤の記録。
結論
ランダムソートならsort_by(rand)がいい。
p (1..10).sort_by{rand} #=> [10, 3, 5, 9, 8, 6, 2, 4, 7, 1]
シェルスクリプトとして活躍中〜。
% random() { ruby -e 'print STDIN.to_a.sort_by{rand}' } % printf "%d\n" {1..5} | random 2 1 3 4 5
かなり便利っす。
では、最適解が出るまでの記録をどうぞ。
ランダムソート
sortを使ってランダムに並び替えてみる。
p (1..10).sort{rand(3) - 1} [5, 2, 10, 1, 4, 9, 6, 3, 7, 8]
rand(3) - 1だと、並び替える確率が低くなってしまうと思い、(rand(2) == 0) ? -1 : 1とした。
p (1..10).sort{(rand(2) == 0) ? -1 : 1} #=> [2, 9, 1, 6, 3, 4, 5, 10, 7, 8]
しかし、この方式には罠があった。
よく見てみよう。
p (1..10).sort{(rand(2) == 0) ? -1 : 1} #=> [2, 9, 1, 6, 3, 4, 5, 10, 7, 8]
よく見ると、うまく混ざってない。2,1が端、10,7,8も端
ふとした疑問
値が固定なのにバラバラになったぞ!!
p (1..10).sort{1} #=> [10, 6, 1, 7, 3, 8, 5, 9, 4, 2]
何故だ!?
Rubyのソートアルゴリズムを確かめる
p (1..10).sort{|a,b| puts "#{a} #{b}"; 0} #=> 1 6 #=> 6 10 #=> 2 6 #=> 3 6 #=> 4 6 #=> 5 6 #=> 7 6 #=> 8 6 #=> 9 6 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
真ん中と端を比べてソートしている。おぉ!クイックソート!
色々実験してみると、
rand(3) - 1の方がよく混ざることが判明した。
p (1..10).sort{rand(3) - 1 } #=> [5, 9, 8, 4, 10, 6, 1, 3, 2, 7]
-1,1のランダム化では、交換してもう一度交換することになり、元の位置に近い場所へ戻ることになる。
-1,0,1のランダム化によって、値を交換しない時を作った方が、より遠くへ運ぶことができる。
しかし、中心にいくほどよく混ざるsortを使ったランダム化は正確にランダムな配列を作ることは出来なそうだ。
sortでは正確にランダム化出来ない事がわかってきたので、
別の方法を試すことにした。無駄にモジュール化。
module Random def random old = clone new = self.class.new while n = old.delete_at(rand(old.length)) new << n end return new end end class Array include Random end p((1..10).to_a.random) #=> [4, 5, 1, 10, 8, 2, 9, 7, 6, 3]
ランダムにポップして、新しい配列にプッシュする。ばらつきのない配列を作ることが出来た。
案外使えそう。
てことで、randomコマンド 0.0.1
#!/usr/bin/ruby # random.rb 0.0.1 module Random def random old = clone new = self.class.new while n = old.delete_at(rand(old.length)) new << n end return new end end class Array include Random end begin print STDIN.to_a.random rescue => ex abort ex.message end
パスの通ったところに,randomと言う名前で登録しておいて、
% random < books.txt | sort BINARY HACKS Fedora Core6 ビギナーズバイブル Linux コマンドポケットリファレンス Vi IMproved-Vim
なかなか便利。
しかし・・
Rubyist - 只今Ruby勉強中 - ランダム配列の話題より。
こっちの方が断然早かった・・・。
% time ruby -e '100000.times {|i| puts i}' | random
で計測したところ、
# ボクノス法 random 5.97s user 0.18s system 52% cpu 11.767 total # Ruby勉強中法 random2 1.31s user 0.35s system 21% cpu 7.742 total
sort_by{ rand }でランダムな数列をインデックス化してソートをかけた方が断然早い。
ボクノス法は、delete_atやpushでメモリをいじりまくるので、重い処理になっていた。
Rubyで配列のランダムソートをする場合は、
sort_by{ rand }
がいい。Perl,JavaScriptに関しては、hail2u.net - Weblog - JavaScriptで配列をシャッフルが参考になります。
ようするに sort_by すごい便利って事で。