aptitude のパターン展開機能は非常に強力で、これを使わぬ手はない、 という話はよく聞くのだが、 なかなかめんどくさそうで手を出してなかった。
このほど、どこかでコマンドを打ち損じて全てのパッケージを hold してしまい、 (パタン展開されて全部 hold されたものと思われる。コマンドは失念) upgrade が一切動かなくなってしまったので、 背に腹はかえられず、必要な範囲で探してみた。 ちなみに hold とはとくに明示的に指示しない限り、 今入っている版から動かさない、というコマンドである。
aptitude search '~ahold'
これで hold されているもの全てが検索対象になる。つまり、 hold されているもの全てを unhold するには、
aptitude unhold '~ahold'
これでいい。
最初は search の結果をじゅんぐりに unhold の引数に zsh のループで 食わせていたが。 これではとにかくむちゃくちゃにCPUを食ってどうにもならない。
無事、 upgrade が普通に動くようになった。良かった。
無名関数の再帰が Twitter でわしが見てる人たちで話題になっていたので、 なんとなくわしもやりたくなった。といっても scheme でそういうのがあるのは 当り前なので、というか scheme の関数は lambda に名前をつけたものなので、 違う環境で、ということでまたしても Ruby で。 そして、せっかくだから、お題は fib で。キャッシュ使わず高速化してみよう。
高速化というより、よくある実装が無駄が多い、という事なのですが。 この記事にある漸化式の行列表現をそのまま Array で実装すればいい。 再帰に Proc クラスを使ってみる。なお、メソッド sum は Array の中身を加算するもの。
fib=lambda{|i|if i==0; [0, 1];else;[(f=fib.call(i-1))[1], f.sum];end}
ちょっとよみにくいかもしれないので、 よみくだしてみると、初期値として fib(0) の戻り値は [0, 1]。 fib(i) は i番のフィボナッチ数 と i-1番のフィボナッチ数 + i番の フィボナッチ数の二つをメンバとする Array です。 これを再帰の表現に直せば、 fib(i-1) の後ろ半分と fib(i-1) のメンバの合算からなる Array です。 行列の体裁を保つために、メモ変数 f に fib(i-1) の戻り値を入れて使いまわしました。
さて戻り値は Array なので、使い方はこんな感じ。100まで計算してみる。
(0..100).gen{|i|fib.call(i)[0]}
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
中略
31940434634990099905, 51680708854858323072, 83621143489848422977,
135301852344706746049, 218922995834555169026, 354224848179261915075]
上の呼出はわしの環境では 0.02 秒弱で終る。(実際には101番まで計算している)
web記事を見ると fib(40) を計算するのに 100秒以上というベンチマークもあるようだ. これはナイーブに f(n)=f(n-1)+f(n-2) って計算してるからで、 これでは計算量が n の exponential になる。 手もとの環境で Proc でやってみたら同じ処理に300秒かかった。
よくかんがえたら、行列の巾で表現できますね。しかもそっちのほうがスケーラブル。 まいった！ とかいいだしたら、漸化式じゃない、あのsqrt(5)が出て来るカッコいい式で 計算するのが一番速いわけですが。
なお、 ? と : で if then else を表現するのは、 やまだあきらさんに教わりました。 いつもありがとうございます！ これは irb でたくさん書いて計算するときに、重宝します。
それにしてもフィボナッチ数列の人気は永遠ですね。
統計処理をするまえに、かならずプロットしてみよう。
たとえば期待値(平均)。我々が扱うデータは有限個なので、 かならず足し算もできれば、その個数で割ってみる事もできる。 たとえそれがどんな分布でもこの操作は可能だ。
平均値が存在しない分布がある、という事は知識としては知っていても、 実際のデータではそれが計算可能なので、ついやってしまうのだ。しかしその結果に意味があるかどうかは、分布に依存する。
たとえば本来は発散する関数の最大値を計算したつもりになってみても、 そんな数値は数学的には何の意味も無いのだ。 そしてこういう間違いはプロットしてみればすぐ判るし防げるのである。
なかのさんとの会話から。
http://en.wikipedia.org/wiki/Buckingham_%CF%80_theorem
この記事凄い面白い。 特に、ちゃんと線形代数で証明がつくところが、あたりまえなんだけど 非常に面白い。 次元といっても極大正規直交系のサイズばかりではない。 基底のメンツがそれぞれ意味を持って区別され、実在の対象とわかちがたく 結び付いているからこそ、物理学は役に立つのだ。 そこを断ち切って数理表現上の洗練だけを求めると、 物理的対象との関連とのトレード オフ になる。 新たに用意した基底に、ちゃんとした解釈がつく場合もあるとは思うが。