週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
昨日やっとFinger Treeのサイトにアクセスできました。読んでみます。
  • Abstを読んでオーダーだけ確認。
  • p. 4の図に激しく混乱。
  • とりあえずAbstの知識だけで説明。
  • p. 4をやっと理解。
  • p. 8 Concatenation に驚愕。concatが非常に短く記述できることに感動しました。
  • 別にconcatって、この構造ではないほかの木構造でもそれほど難しくないような気もしてきました。 ←今ここ

基本は両端がちょっと浅いTreeです。そのためにDequeの動作、つまり最初と最後に償却Θ(1)時間で要素を追加したり削除したりできます。それと別の理由で、concatが償却Θ(log n)時間でできます。時間の評価が償却なので慣れないとちょっと理解しにくいかもしれません。私はまだ慣れてません。

どうしてこの構造になったのかは少し興味があります。Abstractに、「この時間での動作を達成するデータ構造はすでにある。しかしFinger Treeはもっと単純である」とあるので、関連論文を読むことによってそのあたりの歴史的知識がつくかもしれません。

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