ToDo:
http://shinh.skr.jp/m/?date=20100721#p04
自分でやらずに shortest は無いなーとか言うのもずるい気がしたので書いてみた。 前に書いた通り exec すると意味なくなるから exec 封印で。 適当に書いて 490B 。別にゴルフはしてない…
import sys;s=[];reduce(lambda a,_:(a[0]or sys.exit(0))and[1>a[3]and a[0][0]==']'and s.pop()or a[0][1:],a[1]+[(a[0][0]=='>')-(a[0][0]=='<'),0][a[3]>0],a[2][:a[1]]+[1>a[3]and a[0][0]==','and ord(sys.stdin.read(1)or'\0')or a[2][a[1]]+(1>a[3]and a[0][0]=='+')-(1>a[3]and a[0][0]=='-')]+a[2][a[1]+1:],a[3]+(a[0][0]=='['and(0==a[2][a[1]]or 1==s.append(a[0])))-(a[3]and a[0][0]==']'),1>a[3]and a[0][0]=='.'and sys.stdout.write(chr(a[2][a[1]]))],iter(set,0),[file(sys.argv[1]).read(),30,[0]*200,0])
(01:03)
http://d.hatena.ne.jp/nishiohirokazu/20100721/1279687613
つまり kinaba さんの説通りっぽい感じだなぁ。
まとめておくか
あたりでみんな O(N^2) 以上の計算量になってたって感じか。
D に関しては O(N^3) なんだけど、 GC の頻度少ないので、 O(N^3) の係数が大変小さくて 間くらいのオーダに見えた、と。
正直色々やりたいことある時期に 比較的どうでもいい議論に時間を使いすぎた感もあるけど、 しかし GC は結構むつかしいもんだなーという勉強になった。
そういえば Haskell は stack が O(N) になっちゃうのは避けられないんだろうか。 うーん僕の脳内 Haskell 処理系では無理げだな。 つーことは、無限リストの 1億要素目をいきなり取り出すとか だいたい無理みたいなことになるのかあ。
(04:06)
| 前 | 2010年 7月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | ||||
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 | 31 |
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
Ruby の場合しか考えてませんが、
- GC が起きるのは allocation のときだけのはず
- Ruby の Bignum#+ は見たところ定数回しか allocation しない
- fib は毎回 Bignum#+ と Array#<< を呼ぶだけなので allocation は O(N) 回のはず
と考えると、なんで「GC 頻度が O(N) より大きくなった」のかわからないんですが、前提がどれか間違ってる？
あと Ruby の場合、前半は Bignum のオブジェクト生成 (rb_newobj_from_heap) による GC が多く起こり、後半は Bignum の多倍長整数のデータ領域確保 (vm_xmalloc) による GC が多く起こる、となっている感じでした。前半と後半の境は fib[50000] くらい。で、vm_xmalloc による GC ではオブジェクトのヒープは不足していないにも関わらず、GC がヒープを拡張しているみたいで、要するに無駄なヒープを確保しているようでした。なんか関係あるかなあ。
ObjectSpace.count_objects の :FREE (使われてないヒープのエントリ数) と :TOTAL (:FREE を含めた全エントリ数) をグラフ化したら、fib[50000] と fib[120000] あたりの 2 段階で傾向が変わる不思議な現象が観測されました。理由はわかりませんが、GC の allocation 戦略に関係するのかなあ。
http://dame.dyndns.org/misc/misc/fib_free.png
横から失礼します。
- http://twitter.com/kinaba/status/19088258013
- http://twitter.com/shinh/status/19088385052
- http://twitter.com/kinaba/status/19088690088
この辺りで説明がつきませんか。
仮定を置いた部分は「100MBメモリをallocateするたびにGCが動く」のようにGC起動の閾値ヒープサイズが定数であるという仮定（と、この定数＞Nであること）ですが、ghcについては実際、マイナーGCヒープのサイズは動的拡大しないようなので、これが当てはまるように見えます。
Rubyの場合は全然調べてないのですが、:TOTAL とやらが増えていってるのならthresholdが定数というのは当てはまらなそう。けど、「ヒープは不足していないにも関わらず、GC が」とのことだと、何故かわかりませんがやっぱり当てはまってもいそう。
Nを無限に大きくしていくと仮定が崩れるので (参照: http://twitter.com/taru/status/19096644571)、O(N) とか O(N^2) という記法は正しくないんですけども、気分としてはそんな感じで…
なるほど。1 回の allocate で GC が複数回起きうる (1GB なら 10 回？) という仮定なんですね。
- Ruby では 1 回の allocate で高々 1 回しか GC しないはずなので、fib は理論上は O(N^2) になると思われる (Bignum 1 つが 100 MB を超えるくらい N がでかければ)
- 今回の実験ではそこまで GC 飽和状態ではないので、GC の起動回数が影響してしまった
ということであってる？ まあ、現実にはそんな N に達する前にメモリ不足になりそうだけど。
ちなみに Ruby は初期状態では「8MB メモリを malloc したら GC が動く」なんだけど、その閾値は GC が起きるたびに増えます。その増加分は以下のよくわからない式なんですが、
malloc_limit += (size_t)((malloc_increase - malloc_limit) * (double)objspace->heap.live_num / (heaps_used * HEAP_OBJ_LIMIT));
掛け算なのでなんとなく例の 1.5 倍みたいに増やすと思いきや、printf してみると実質は定数増加、それも 10 KB 程度足すだけなのでほとんど不変のようです (バグかも？) 。というわけで、現状の Ruby でも @kinaba んの予言通りな気がします。
> ということであってる？
と思います。
100%完璧に伝わっているのでよいのですけど、
> なるほど。1 回の allocate で GC が複数回起きうる (1GB なら 10 回？) という仮定なんですね。
こう表現するのは、自分としては違和感が…。
- 入力パラメタをN、GC起動の閾値をこれもパラメタ変数Tとして N/ceil(T/N) 回GCが動く（と仮定）
- Tを定数と見なしてNに関するオーダをO記法で書くと、GCの回数は"O(N)である"
- "GC 頻度が O(N) より大きくなった"という表現は正しくない
- N≪T の範囲では、N/ceil(T/N)≒N^2/T なので、GCの回数は"N^2に正比例しているように見える"
のような気分です。
そうそう、N/ceil(T/N) 回。わかりやすい説明ありがとうございます。
この問題は閾値を 2 倍だか 1.5 倍だかで増やすようにすると対処できる気がするけれど、対処すべきなのかなあ。現実のプログラムでもこの問題は発生しているのか。対処したらむしろメモリ食い過ぎなど負の影響を与えはしないか。うーん。
と、ここで考える話じゃないですね。おじゃましました。
なにか議論が行なわれていた!
なんか Ruby コミッタ様によって Ruby もこれで問題なさげですね。あとは Java コミッタ様が降臨されれば勝てます。
あと O(x) は使わずに普通に x 回とか言うべきですねたぶん…オーログエヌとかなんかカッコいいからつい使ってしまう中二病に我々は罹患しているのかもしれません…
そもそも、一連の議論を読んでいて、最も重要な「参照透過性と動的計画法をどう両立するか」の問題について、触れてる人がいないのが不思議です。
「代入による副作用」が許された普通の逐次型言語ならば、N 番目のフィボナッチ数列の十進桁数は O(N)、使用する変数個数は動的計画法を用いれば配列なんて使う必要もなく O(1) ですから、後は多倍長整数加法のコストに依存するだけです。
ところで、N^2 も N も log N も O(N^2) なので(「N^2の定数倍を上界とする関数の集合」に過ぎない)、むしろ下界 Ω(N^2) を使うとか、あるいは上下界 Θ(N^2) を使うとカッコいいかも知れませんね ;-)
さらに、o(x) とか ω(x) を使うと、「解析学やってる人っぽさ」を醸し出せますよ(ホンマかいな
あーうーんと、「参照透過性と動的計画法をどう両立するか」という問題は本当に最も重要なんでしょうか。
僕個人としては、そのテーマの文言だけ見ると、「何やら面白そうなテーマだなぁ」と思いますが、まぁ土日に誰かがまとめていたら読んでみるかなーくらい、つまり今回みたいにわざわざ平日にコミュニケーションを取る努力をしてみて解決したいとは思わんかなーと思ってしまいます。
というのは単に sin-x さんと知識を共有してないというかありていに言って僕の理解のレベルが低いからだと思うのですが、しかしまぁ、「その話ならそのテーマAよりテーマBの方が面白いよ」というのに説得されるには、ある程度テーマBについて語っていただかないとわからんというか、面白い話キボンヌ的な催促がつまりしたいという話をこの文で書きたかったことなんだと思います :)
でまぁ上のよくわからない文はともかく、本題としては、ええともちろん O(N) な配列なんて使ってないフィボナッチの計算は計算回数は O(N) ですし、実際 Haskell だって計算回数は O(N) だし多倍長整数の加法だって O(N) だろうし、ということでどっから O(N**a) の a が 2 より大きくなったんか、ってのがまぁ面白がられたことかと思います。
例えば、今回以前だと、配列とか別に使ってない fibonacci のコードを GC のある言語で書いたとして、 O(N) 以外になるとは思ってなかったと思うのですが、今は O(N) に見えないグラフができてもあーそいうこともあるかもなぁと考えると思います(たぶん実際にそう見える値域もあるんじゃないかな…と思いますがちょっと難しいかも)。まぁそういう部分が今回は面白かったです。
あと、カッコ良さ講習はありがとうございます。 O() って NP とかみたいにそれ以下のもの含んじゃうんですね…
あああ、申し訳ないです。一般的な話をしていたつもりだったんですが、shinh さん個人へのコメントのような書き方でしたね。それに「誰かがコメントしたらそれへのコメントの労力」も必要ですし。以後気をつけます m(..)m
私の言いたかったことはは、「ネタ元の人(や関数型言語にこだわる人)が動的計画法に触れていない」こと、つまり、「アルゴリズムを改善しないまま議論することに意味があるとは思えない」ただそれだけです。
とは言え、私自身が関数型言語をあんまり理解していないので、実はあのコードが動的計画法を考慮しているかもしれません。しかしそれでも、Ω(N^2)-時間かかるのだとしたら、あんまり使う気にはなれないです。
まあ、N^1000-時間とかかかっても、高々 P なので、個人的には十分効率的で全く問題ないです(マテ
ああなるほど。そういう意味であれば、 Haskell のコードは普通に動的計画法で書いた時のコードに近いものになってるかと思います。無限リストは先っちょから GC されてるはず。サイズ N のスタックを作ってるのは珍妙な感じではありますけど。
Haskell 以外に関しても、無駄に途中結果の値を保持していることを除けばまぁ動的計画法のコードと言っていいんじゃないかと思います。
Ω(N^2) かかるのは、動的計画法的な手段で計算すれば必ずかかるかと思います。計算回数が N で、多倍長整数の加算で N です。例えば C++ も N^2 かかってました。みんなが興味を持ったのは、 GC のある言語で N^2 よりやや大きく見えたことだと思います。
あと、アルゴリズムの改善ということなら、そもそも fibonacci は N log(N) で計算できるはず(黄金比の N 乗なり行列の N 乗)なので、そういう意味では、動的計画法の話をすること自体がナンセンスなのでは。
ああ、仰せのとおりです orz 多倍長加算のコストを途中で忘れてました。その計算量で良いです。
ところで、計算量理論では「poly(N)-時間かかる場合, poly(N)-空間使う可能性がある」ことになっているので(チューリングマシンを仮定するから仕方ないのですが)、線形空間スタックを使う可能性はありえます(P = DTIMESPACE(poly(n),poly(n))が、この問題で定数空間スタックに収まらないことは奇妙ですね。
ちなみにサイズ N のスタックになってるのは、
遅延評価された N 番目の fib を取ろうとする =>
あっまだ計算してねえや計算しよう =>
遅延評価された N-1 番目の fib を取ろうとする =>
あっまだ計算してねえや計算しよう =>
遅延評価された N-2 番目の fib を取ろうとする =>
あっまだ計算してねえや計算しよう =>
...
という関数呼び出しになってるからだと思います。
でまぁプログラマは遅延する必要無いのはよく知ってるのでこれ正格評価してくだっせーと教えてやれば stack 使わんよというのがこのへんかなと思います。
http://d.hatena.ne.jp/kazu-yamamoto/20100624/1277348961
あれ、文中のリストが大きくなる、は誤認かなと思います。
あと、前から順にアクセスすればサイズ N の stack できないよーというのがこのへんかと。
http://d.hatena.ne.jp/mkotha/20100623/1277286946
Haskell を毛嫌いしてる人間による Haskell 弁護でした。
理解しました。解説ありがとうございました。というかわざわざすみません m(..)m