<a class="info_title emj" href="https://togetter.com/li/36609" title="続:Haskellのfibが遅い件">続:Haskellのfibが遅い件

@gusmachine いやあ、実は図をアップしないというポリシーがあって崩すほどではないかなと思ったのです。

2010-07-18 23:04:05

@ainsophyao なんと。じゃあ代わりにこちらで図を描いてあげよう << 酷い人

2010-07-18 23:09:25

@gusmachine エクセルで適当に描いたグラフくらいは持ってますけれども。

2010-07-18 23:14:16

http://d.hatena.ne.jp/nuc/20100716/p17 理論的に実行時の動きを考えるとO(n**2)「…回の加算とcons/de-consを行う」まで言えても、それ以上（例えばO(n**2)の実行時間となる等）はこのレイヤでは何も言えぬので言わぬが吉と思うの

2010-07-19 02:56:58

. @kinaba はーい。一番言いたかったのはO(n^2.6)じゃないってことで。理論的にはともかく、実際に O(n^2)の実行時間となる、までは言っていないつもりでしたが、筆が滑っていましたか。 http://d.hatena.ne.jp/nuc/20100716/p17

2010-07-19 03:02:34

@ainsophyao 最初８行は同意するのですが、はい、「理論的に実行時の動きを考えるとO(n**2)」という部分、直前まで時間の話をしているのでここも「（理論的には）時間のオーダがO(n**2)」と読めてしまうのですが計算モデルを示さず時間の話をするのは危ういなあと思いました

2010-07-19 03:30:28

適当なGCの実装を仮定すると実行時間がO(n**2.6)になるようなモデルは作れると思いますし、実際、例のコードでもマイナーGCヒープを思いっきり大きくすると綺麗に演算回数に比例した実行時間になる（なったはず）ので、その辺考えずに"時間の"理論評価をしても意味が薄いと思う

2010-07-19 03:34:51

@kinaba はい。たしかに計算モデル依存ですね。そうか。今回の僕は色々とまずいみたいです。shinh さんが解析してくださったみたい。 http://shinh.skr.jp/m/?date=20100719#p01 今フィットやり直してますが、もしかしてアーキテクチャ依存?

2010-07-19 03:39:02

@ainsophyao アーキテクチャ依存のような気がします。自分の手元の環境だとfibではそんなに"遅く"ならなかったのですが、1:1: を 0:0: に変えてみたところ superlinear な実行時間に見える実験結果になったのでそれで実験したりしてました。

2010-07-19 03:52:30

一見O(n)に見えるコードの裏で、メモリアロケータがそれ以上に時間かかっていた事例 http://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb/ruby/ruby-dev/13652?13515-14611

2010-07-19 04:01:38

@kinaba ああ、こちらも手元で"遅く"ならなかったのですが思ったよりも複雑なのですね。ちなみに fib::[Int] (桁あふれする)では、n^1.3 程度になりました。

2010-07-19 04:12:24

「この処理の(時間)計算量は〜である」という言明は厄介だ。通常、専門家の間ではこれは(動的)メモリ確保のオーバーヘッドを含まないことを意味するし、実務家はそこを無視した近似で言っているか、見落としているか、オーバーヘッドの機種／OS／アプリ依存性に気づいていない。

2010-07-19 09:25:09

実務家の間でこれだけ理解がばらばらなのに意思疎通できてるように見えるのは、「オーバーヘッドを含む実測値を理論値と混同してるだけ」という論外な最低線が収束先だから

2010-07-19 09:35:07

小飼氏の「階乗はO(1)」という話と西尾氏の「Haskellのfibは遅い」という話に共通の混乱はこういう事情があるので、非常にあたまがいたい

2010-07-19 09:41:01

ていうか小飼氏の話もそもそもJavaScript上のfibの話から始まっている。個人的偏見によればfibは能力を誇示したい理論蔑視タイプの人の玩具になりがちであるという真実がここに照らし出されている。なお理論蔑視の諸相についてはカントが「理論と実践」の序文であっさり書いている

2010-07-19 09:49:36

偏見に任せてさっきから酷いことを呟いているが誰かれを非難する意図は自分には無い。これらの混乱が生じるのは必然であって、計算機が人間の玩具である間は決してなくならない

2010-07-19 09:52:27

というわけで誰かP⊂LINSPACEをとっとと証明してください。これでも混乱は無くならないけれども大分減るはず

2010-07-19 09:55:37

ついでに言うとfibの計算をしたがる人々を見ていると「整数論的の試練」とかいうのもあんまり現代ではあてにならんなと思う

2010-07-19 10:02:13

この記述はちょっと疑問。アルゴリズムの実行時間をNとしたときにO(N)より多く時間がかかるメモリ管理はまずいんじゃないかしら。修正してやる! RT: @kinaba http://twitter.com/kinaba/status/18857028120

2010-07-19 10:12:59

まず私は何がO(n**0.6)の原因なのか調べないと. fib(N)問題は何も調べずに簡単な問題だと誤認してたので。

2010-07-19 10:14:22

古典的なアルゴリズムの本は、もちろんならし計算量(amortized complexity)について(すくなくとも明示的には)考察していないから、現代では必要なメモリが最初から割り当てられるような一部の組み込み用途以外では「教科書に書いてある」とは言えない

2010-07-19 10:21:28

Borodin and El-Yaniv(1998) が学界における理論的定式化で、これは金融工学アプリのリアルタイム性要求が高まっていたという現実的な背景がある

2010-07-19 10:25:03