2010-07-20

*1279585816*海の哺乳類展に行ってきた

f:id:nishiohirokazu:20100719124244j:image

イッカク！これは1本だけある歯だそうな。超出っ歯。

*1279595270*続:Haskellのfibが遅い件

とても勉強になる流れなのでとりあえずざっくりとまとめる

- a href='http://d.hatena.ne.jp/nishiohirokazu/20100622/1277208908' Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅い/a

-- Haskellの有名なfibの定義は素朴なループでの定義に比べて格段に遅く、O(n^2.6)くらいの実行時間がかかり、N = 100000でPythonにすら負ける

- a href='http://togetter.com/li/31078'Togetter - 「Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅い件」/a

-- Integerの足し算のコストとかも絡んでくるのでややこしいという話など

- a href='http://d.hatena.ne.jp/mkotha/20100623/1277286946'fib = 1 : 1 : zipWith (+) fib (tail fib) が遅いかどうかは、使い方に依存する - www.kotha.netの裏/a

-- fibを先頭から順に使って行った場合(例:sum (take 300000 fib))の方が、fib !! 300000よりずっと速いという話

-- 僕の書いた早いバージョンのfibは正格性が(コード上には明記されていないが)コンパイラによって推論されているという話

-- 巨大なリストから要素1つだけを取り出す時と2つ以上取り出すときではかかる時間や消費メモリがぜんぜん違うという話

-- 正格評価するzipWith'を作ればよい、という話など

- a href='http://d.hatena.ne.jp/nuc/20100716/p17'haskell の fib は遅くない - 白のカピバラの逆極限 S.144-3/a

-- 空間計算量が一時的に影響与えたと考えるのが自然、という話

- 「まずふたりともグラフを描くべきである」 http://twitter.com/gusmachine/status/18840198768

-- 「2.77618e-13*x^2.55 の方が 2.10854e-10*x^2 よりどう見てもマッチしてるな。特異的って感じもないと思う。」空間計算量が一時的に影響与えたのではないのではないか、という話

- a href='http://togetter.com/li/36609'Togetter - 「続:Haskellのfibが遅い件」/a

-- 環境依存の可能性が高いという話、GCやメモリアロケータのせいでO(n)に見える処理に実際にはそれ以上に掛かるケースがある話(Rubyで過去にあった例)、など