週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Purely functional data structuresを読んでいます。はるか昔に買ったものの、半分も読まずに中断していました。一部理解できなかったところを飛ばしつつ、9章の半分まで読んだところです。

6章以降は感動の嵐でした。この手のデータ構造は普通思いつきません。ちょっとこれはプログラマとして読んでおいたほうが良い本リストのtop 10に入ると思います。詳しい解説はまた今度。

9章のredundant binary numbersが完全にFinger Treeの基礎と同じでした。ならしO(1)でpush, popができて、O(log N)でindex accessができます。ここまで読めていれば、Finger Treeも、「Lazyにしておくと嬉しい」も簡単に理解できます。

6章のphysicist method based amortization with persistenceがまだ良く理解できていません。p. 70のBinomial Heapsは次のように理解すれば良いのでしょうか。

  • insertはいくらでも遅らせてよい。少なくともfindmin, deletemin, mergeが来るか、次のポテンシャル0まで遅らせてよい。insertの際に評価を強制する必要は全くない。
  • findmin, deletemin, mergeはどうせO(log N)かかるので、ついでにinsertの評価を行なってもO(log N)は変わらない。
  • emptyはあらかじめ結果を保存しておくことでO(1)を実現できる。

これは実は今日の帰りの電車で思いつきました。これで良さそうなら、他のphysicist methodの話を読んでから先に進みます。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/438-950126ca
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。