編集部が厳選した「いま、みんなに見てほしいまとめ」をイチオシとして紹介しています!グサッと刺さる良質まとめはこちら!

続:Haskellのfibが遅い件

前回のあらすじ: http://togetter.com/li/31078 http://d.hatena.ne.jp/nishiohirokazu/20100720/1279595270 > まとめるのが大変なので誰かTwitter上の発言だけでもTogetter作ってくれないかなぁ(他力本願 続きを読む
3058view 0コメント
3
ログインして広告を非表示にする
Yu SUGAWARA @gusmachine
そして私は http://code.google.com/apis/chart/docs/chart_wizard.html をどうにかするか自分用のを書くかすべきであると思った。simple encodingだと長すぎてtwitterに貼れない.
{白,黒}のカピバラの左随伴右随伴 @ainsophyao
@gusmachine いやあ、実は図をアップしないというポリシーがあって崩すほどではないかなと思ったのです。
Yu SUGAWARA @gusmachine
@ainsophyao なんと。じゃあ代わりにこちらで図を描いてあげよう << 酷い人
{白,黒}のカピバラの左随伴右随伴 @ainsophyao
@gusmachine エクセルで適当に描いたグラフくらいは持ってますけれども。
kinaba @kinaba
http://d.hatena.ne.jp/nuc/20100716/p17 理論的に実行時の動きを考えるとO(n**2)「…回の加算とcons/de-consを行う」まで言えても、それ以上(例えばO(n**2)の実行時間となる等)はこのレイヤでは何も言えぬので言わぬが吉と思うの
{白,黒}のカピバラの左随伴右随伴 @ainsophyao
. @kinaba はーい。一番言いたかったのはO(n^2.6)じゃないってことで。理論的にはともかく、実際に O(n^2)の実行時間となる、までは言っていないつもりでしたが、筆が滑っていましたか。 http://d.hatena.ne.jp/nuc/20100716/p17
kinaba @kinaba
@ainsophyao 最初8行は同意するのですが、はい、「理論的に実行時の動きを考えるとO(n**2)」という部分、直前まで時間の話をしているのでここも「(理論的には)時間のオーダがO(n**2)」と読めてしまうのですが計算モデルを示さず時間の話をするのは危ういなあと思いました
kinaba @kinaba
適当なGCの実装を仮定すると実行時間がO(n**2.6)になるようなモデルは作れると思いますし、実際、例のコードでもマイナーGCヒープを思いっきり大きくすると綺麗に演算回数に比例した実行時間になる(なったはず)ので、その辺考えずに"時間の"理論評価をしても意味が薄いと思う
{白,黒}のカピバラの左随伴右随伴 @ainsophyao
@kinaba はい。たしかに計算モデル依存ですね。そうか。今回の僕は色々とまずいみたいです。shinh さんが解析してくださったみたい。 http://shinh.skr.jp/m/?date=20100719#p01 今フィットやり直してますが、もしかしてアーキテクチャ依存?
kinaba @kinaba
@ainsophyao アーキテクチャ依存のような気がします。自分の手元の環境だとfibではそんなに"遅く"ならなかったのですが、1:1: を 0:0: に変えてみたところ superlinear な実行時間に見える実験結果になったのでそれで実験したりしてました。
kinaba @kinaba
一見O(n)に見えるコードの裏で、メモリアロケータがそれ以上に時間かかっていた事例 http://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb/ruby/ruby-dev/13652?13515-14611
{白,黒}のカピバラの左随伴右随伴 @ainsophyao
@kinaba ああ、こちらも手元で"遅く"ならなかったのですが思ったよりも複雑なのですね。ちなみに fib::[Int] (桁あふれする)では、n^1.3 程度になりました。
状態(の変化)* @TuvianNavy
「この処理の(時間)計算量は〜である」という言明は厄介だ。通常、専門家の間ではこれは(動的)メモリ確保のオーバーヘッドを含まないことを意味するし、実務家はそこを無視した近似で言っているか、見落としているか、オーバーヘッドの機種/OS/アプリ依存性に気づいていない。
状態(の変化)* @TuvianNavy
実務家の間でこれだけ理解がばらばらなのに意思疎通できてるように見えるのは、「オーバーヘッドを含む実測値を理論値と混同してるだけ」という論外な最低線が収束先だから
状態(の変化)* @TuvianNavy
小飼氏の「階乗はO(1)」という話と西尾氏の「Haskellのfibは遅い」という話に共通の混乱はこういう事情があるので、非常にあたまがいたい
状態(の変化)* @TuvianNavy
ていうか小飼氏の話もそもそもJavaScript上のfibの話から始まっている。個人的偏見によればfibは能力を誇示したい理論蔑視タイプの人の玩具になりがちであるという真実がここに照らし出されている。なお理論蔑視の諸相についてはカントが「理論と実践」の序文であっさり書いている
状態(の変化)* @TuvianNavy
偏見に任せてさっきから酷いことを呟いているが誰かれを非難する意図は自分には無い。これらの混乱が生じるのは必然であって、計算機が人間の玩具である間は決してなくならない
状態(の変化)* @TuvianNavy
というわけで誰かP⊂LINSPACEをとっとと証明してください。これでも混乱は無くならないけれども大分減るはず
状態(の変化)* @TuvianNavy
ついでに言うとfibの計算をしたがる人々を見ていると「整数論的の試練」とかいうのもあんまり現代ではあてにならんなと思う
Yu SUGAWARA @gusmachine
この記述はちょっと疑問。アルゴリズムの実行時間をNとしたときにO(N)より多く時間がかかるメモリ管理はまずいんじゃないかしら。修正してやる! RT: @kinaba http://twitter.com/kinaba/status/18857028120
Yu SUGAWARA @gusmachine
まず私は何がO(n**0.6)の原因なのか調べないと. fib(N)問題は何も調べずに簡単な問題だと誤認してたので。
状態(の変化)* @TuvianNavy
古典的なアルゴリズムの本は、もちろんならし計算量(amortized complexity)について(すくなくとも明示的には)考察していないから、現代では必要なメモリが最初から割り当てられるような一部の組み込み用途以外では「教科書に書いてある」とは言えない
状態(の変化)* @TuvianNavy
Borodin and El-Yaniv(1998) が学界における理論的定式化で、これは金融工学アプリのリアルタイム性要求が高まっていたという現実的な背景がある
Yu SUGAWARA @gusmachine
メモリ管理で計算時間が多くなってた例が挙がっているけど、これは結局修正対象になったように見えます。 http://twitter.com/kinaba/status/18858351065
残りを読む(87)
ログインして広告を非表示にする
ログインして広告を非表示にする