Hatena::ブログ(Diary)

ボクノス このページをアンテナに追加 RSSフィード

2007-05-12

GNU globalすげぇ。

GNU globalが気になったので使ってみた。

何といっても凄いのは、「global -r hoge」で参照元に飛べる点。コードリーディングには必修です。

Vimとの連携は以下を参照。

うちの環境では、/usr/share/gtags/gtags.vimプラグインが入ってた。パッチを当てないとエンターで飛べないので当てた方がいい。

タグの作成は、

% gtags

これだけ。簡単杉。

では、Vimから使ってみる。rubyソースを読む。

: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]

Rubyクイックソートの場合、中心を起点に交換する。

-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 すごい便利って事で。

Konsoleメモ。

イマイチ使用法をつかんでいなかったKDE付属のKonsole。

実は・・・Screen要らずだった!!

ポイントはshiftキー。

面倒なのでSで省略する。

S-←→タブ切替
S-↑↓1行スクロール
S-Page↑↓1画面スクロール
S-Insert貼り付け

もちろんキーバインドの変更も効く。ガンガン登録しておくと便利。

C-A-hにメニューバーのトグルを入れると,Altキーを押してもメニューバーにフォーカスを取られなくなる。必修。