諸事情で jq で Array shuffle を実装したので、 実装や実装に必要となった初歩的なアルゴリズムについて記録する。
とりあえずできたものはこちら。 jq -nrcf usage.jq でシャッフルされた配列が返ってくるはず。
gist.github.com
jqとは
jq には
jq is a lightweight and flexible command-line JSON processor.
と書かれている。 JSONを入力として、それに対するフィルターを書くことでJSONの加工が行えるくん。なのだけれども、JSONを入力とせずともフィルターのみでコーディングすればおおよそなんでもできる。
jqが用意してくれているもの
条件分岐
jq は if 文が使える。
2 | if . == 0 then "zero" elif . == 1 then "one" else "many" end # => "many"
関数
jq は関数を作ることができる。作った関数はパイプを通すことができる。引数も渡せる。
def increment: . + 1; 1 | increment # => 2
変数
jq は変数を定義できる。
["Amy", "Basil", "Clara"] as $children
と書いておけばパイプの後からでも $children を呼べる。
これら以外にもたくさん jq はできることがあって、それらは jq Manual (development version) に記載されている。変数宣言が "Advanced features" の項目にいるのは、本来の使い方を考えるとまあそうだよね。といった感じ。
モジュール
jq は別のjqファイルを読み込むことができる。 上の usage.jq でやっているように import PATH as Name でPATHを読み込む。読み込んだファイルの関数は Name::function のように呼べる。
デバッグ出力
jq は debug 関数を使うことで計算途中でも関数実行時点での値を出力することができる。実装中長いパイプを通す必要が出てきたときに重宝した。
["A", "B", "C", "D", "E", "F", "G"] | { "key": .[] } # {"key":"A"} # {"key":"B"} # {"key":"C"} # {"key":"D"} # {"key":"E"} # {"key":"F"} # {"key":"G"}
["A", "B", "C", "D", "E", "F", "G"] | { "key": (.[] | debug) } # ["DEBUG:","A"] # {"key":"A"} # ["DEBUG:","B"] # {"key":"B"} # ["DEBUG:","C"] # {"key":"C"} # ["DEBUG:","D"] # {"key":"D"} # ["DEBUG:","E"] # {"key":"E"} # ["DEBUG:","F"] # {"key":"F"} # ["DEBUG:","G"] # {"key":"G"}
jq が用意してくれていないもの
乱数
jq には乱数が用意されていない。精度はまったく気にしていなかったので、擬似乱数について調べた。線形合同法を用いた疑似乱数が古典的でシンプルというのを見たので雑に書いた。定数はC言語のライブラリにある Park and Millerによって提案された「最小標準」の実装を参考にした。 ちょっと散らすために何回か繰り返しかけるようにしているが、個人的なおまじないレベル。
refs: Question 13.15
シャッフル
jq には配列のシャッフル関数が用意されていない。乱数が用意されていないのでそれはそう。どういったアルゴリズムが適しているのか調べると、 フィッシャー-イェーツのシャッフルというアルゴリズムがあることを知った。配列の要素ごとに無作為に選んだ要素と場所を入れ替える、というのを要素数分繰り返すことでシャッフルを実現している。畳み込みでも実現できそうだったので、今回は reduce を使って畳み込むことにした。配列の要素を指定してSwapした結果を別の配列として返す、というのが意外とめんどくさくて、上の実装では Array Slice を使って無理やり配列を組み立てている。もう少しどうにかなりそう。
refs: Fisher–Yates Shuffle
懸念していること
乱数の偏りについてなにも考えられていないので検証が必要。カルドセプト サーガを思い出した。
学び
- 乱数、シャッフルの初歩的なアルゴリズムの復習ができた
- jq 意外と何でもできることがわかった
- 上記のような変なこと意外にも関数一通り眺めたので、どんなことができるかは把握できた。
- ついでに配列、ハッシュの操作を行うコードも別件でちゃんと書いたので、大体jqわかった。
なぜこのようなことを
知り合いがjqでProject Eulerを解いているという話を聞いて興味が出たので。
参考
- jq Manual (development version)
- 全部書いてある。
- jq/builtin.jq at master · stedolan/jq
- ビルトインの関数の実装。どんな感じで関数を書けば良さそうかの雰囲気はつかめる。
- Fisher–Yates Shuffle
- フィッシャーイェーツの図解
- Question 13.15
- C言語における疑似乱数の実装についてのQA
