多分, shuffle して head するのがいい. shuffle するのは sort になんかそういうオプションがあるんじゃないか, って事で探すと
sort -R
というのがある. つまり
sort -R | haed -件数
でできるわけだ.
そこで気になって, たとえば入力ファイルのフォーマットが(CSVみたいに)決まってれば, 特定のフィールドで sort なんてできるんじゃないかと思って調べてみた. はたして,
sort -k 1 -k 2nr
ということらしかった. sort はそのままだと辞書順なので, n つけると数値順になる. r は逆順(大から小)
こんだけできたら, もう大概SQL要らんがな.
前後の桁を計算せずに必要なところだけ取り出せるアルゴリズム. 何のはなし? ってつまり円周率とかの話ですわ.
円周率ものすごい桁数計算した, みたいな話があるじゃないですか. あれをどうやって検算してんの? って事なんすよ. これが \(\sqrt 2\) なら2乗して2になるか確かめられるけど, なんせ超越数だけに何か簡単な検算式に放り込んでみるわけにいかないわけですよ.
Weisstein, Eric W. "Pi Digits." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PiDigits.html\(\pi\) はこうやって計算できるらしいよ. すごいね. どうやって思いついたんかね.
とりあえず msieve.rb on github をどっかに開いてください.
general number sieve アルゴリズムその他の実装として有名な msieve を Ruby から使うインタフェースだよ. msieve の実装は C で書いてあるネイティブコードだから, 普通だったら C で拡張ライブラリを書くところだが, もう C は書けないし, 最近はこういう便利なものがあるので, それを使いながら覚えてみよう, という企画.
なお, 俺のコードの使い方だが,
irb(main):015:0> (2**181 -1).msieve_factorize [43441, 1164193, 7648337, 7923871097285295625344647665764672671]
こんな感じでメルセンヌ数をばらしてみる. 素因数の配列を返す仕様なので, 戻り値の長さが1なら素数だと判るしくみ. ちょいと検算してみる
irb(main):018:0> (2**181 -1).msieve_factorize.map{|i|i.msieve_factorize}
[[43441], [1164193], [7648337], [7923871097285295625344647665764672671]]
確かに素因数分解されてる. アルゴリズムの説明も書こうかと思ったけど, 分量的にアレなので次回ということで.
ffi の説明はこちらにある. わしは apt-get install ruby-ffi でインストールした.
ffi とは要するに,
require "ffi"
しておけば, 呪文をちょいと Ruby で書いとけば, ネイティブコードの関数やデータに Ruby からアクセスできる, というクソ便利なものなのだ. コツがわかってくれば, C を書くよりかなり簡便で, 大抵必要になるものは用意されている印象. なにより irb で即座にチェックしながらコードをかけるので捗る.
では, msieve.rb を例にして解説していくよ.
require "ffi" は呪文ですな. 次の module を定義するところは, class ではなく module を定義するのだ. module になってる事情はあとで説明します. 次の extend も呪文で,
ffi_lib "libmsieve.so"
というのがこの名前の shared library を link するぞ, という呪文.
class Msieve_obj < FFI::Struct
layout :input, :pointer, # the input here
:factors, :pointer, # output here, as a linked list
:max_relations, :int # some setting
end
次に module のなかのクラスを定義している. これはリンクする shared library で定義されていて, 今回自分が使いたいデータ(Cの構造体)を Ruby のクラスとしてアクセスするためのマッピングだ. クラスの名前は構造体のそれをそのまま使う. 前述の module 定義は, 名前の衝突を避けるうえで役に立つ. layout 宣言の中身は構造体メンバの名前と, その型だ.
構造体メンバにアクセスするのは, こうやる. ちょっとめんどくさい.
def Msieve.cast_to_mo(ptr)
Msieve_obj.new ptr
end
Msieve.cast_to_mo(mo)[:factors]
こういう感じ. 変数 mo に構造体へのポインタが入ってるとすると, 一旦これを cast すると, 定義した構造体クラスのインスタンスになる. すると, [:メンバ] というメソッドで構造体メンバにアクセスできるようになる. hash を元にして定義されてんすかね. そういえば Ruby のオブジェクトも全部ポインタなのだった.
attach_function :msieve_run, [ Msieve_obj ], :void
これはほぼ自明ですな. モジュール関数としてネイティブコードの関数を呼び出せようにする呪文. 最初が引数(の型)のリストで, 二つめが戻り値(の型). 引数が100個あったら100個用意しないといけないので, 順序や数を間違えずに関数を attach したり呼び出すのはかなりめんどくさい.
このあたりまでは, ちょっとCの事情を加味したRuby だけど, この先は徐々に何語を書いてるのかわからなくなってくるかも.
bufptr=FFI::MemoryPointer.new(:char, 400).write_string(str, len)
これは char が 400並んだ配列へのポインタを確保して, そこに文字列を書き込む処理. 指定した長さ分だけが書き込まれる. なんで400かというと, 元のソースでそういう作りになってて, digit な文字以外が出てくるまで buffer を読みつづけて, char の列から多倍長整数を作るようになってるからだ. つまり400桁以上の数値だと動かないし, 文字列の終端を教えるためにバッファの端に 0x00 が入ってる必要がある.
このあたりは実際にコンパイルされたコードが動いてるところを追いかけて, そのへんの事情を調べたうえで, その状況を Ruby 側で再現してやらないといけないので, 最低限そのあたりの知識と経験がないと, さすがに Pure Ruby で拡張機能を書けますよ, とはいっても要求される暗黙知は案外多い.
何かを書き込まないと, 単にポインタを宣言して初期化したものができるのも C と同じだ. 元のコードで, 初期化したままのポインタを引数にしている場合はそれに習って, ポインタを作っただけで何もしないまま渡してやる必要がある.
p1, p2, p3, p4 = Array.new(4){FFI::MemoryPointer.new(:int, 1)}
こういうかんじで座席を埋めるためだけにポインタを作ってます. 適当に nil を渡したり, 引数をとばしたりすると動かない. 変なアドレスを参照しても大抵は exception で判るが, 場合によっては vm ごと OS に終了されてしまう.
Msieve::msieve_run(mo)
戻り値が void の関数は Ruby 的には hoge! な感じなので, そういうコンベンションで名前をつけていくのもいいのかもしれない. void 関数を呼ぶと, 破壊的に副作用が発生して元の変数が書き換わるので, もはや何語だかわからん. 上のコードでポインタ変数 mo が指す先の構造体に, 素因数分解の結果が格納される. 今回の目的でいえば, 他のすべてはこれをやって, 結果を引っ張り出すためだけに存在しているといっていい.
null pointer かどうかを調べるのは, .null? である.
文句ばっかり言ってるみたいだけど, ここで紹介した方法で作る限りはポインタを作りっぱなしにしてもガベコレしてくれるらしいのだ. 普通の C で拡張機能を書くよりも断然楽だ. それだけでも使う価値は大きいと俺は思う.
enum も定義できて, enum が戻り値になってる関数も, それで扱えるのであるが, Cでの enum の作り方が, よくわかってないので, cpu の種類を調べる関数を使うところがきちんと書けておらず, いまは generic cpu を使う設定で動いてる.(enum が戻り値の関数を使うと, 戻りの enum を Ruby 側で定義しておかないと戻り値が nil になってしまう. symbol から数値をマップする hash として enum を置き換えているのかね)
msieve は, そのままだと static library をビルドするようになっているので, shared library を作って, どこか ld の解る場所にその .so を置くと, 動くと思う. shared library の作り方は, ずばり gcc how to build shared library とかいって検索すれば記事がある.