prog_0002
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* スキップリスト
-(by [[K]], 2014.10.14)
** (0)
-今回はスキップリスト（SkipLists）の話。
** (1)
-多数のオブジェクトがある状態で、オブジェクトを高速に検索...
-行いたい操作は、次の通り。
--(a)要素の追加
--(b)要素の削除
--(c)要素をキーで整列させておいた状態において、i番目の要...
---これができれば先頭や末尾も取れる
--(d)ある要素を指定した時に、その要素が先頭から何番目であ...
--(e)あるキーを指定して、それより小さい要素のうちで最大の...
---つまり、2,4,6,8,10が登録されているときに、key=7で検索...
--(f)あるキーを指定して、それよりも大きい要素のうちで最小...
--(g)2つの要素の間にいくつの要素があるかを返す
--(h)2つの要素の間の要素を順番に列挙する
--なお、前提条件として、キーの重複はないとする。
-これらをやりたいならスキップリストがよさそうだと思った。
--http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%8...
--http://www.dd.iij4u.or.jp/~okuyamak/Information/SkipLis...
-スキップリストなら、(a)～(g)の操作がO(logN)でできそう。(...
--上記のwikipediaのページによれば、B木はさらに優秀らしい...
** (2)
-僕は先日これを実装した。高速化を少し意識して冗長な部分も...
-ちなみにp=1/4くらいがちょうどいいかなと思っている。p=1/2...
-この実装では、もちろん一般化された比較関数を採用して（参...
** (3)
-乱数を使うというのは、結果が乱数によって左右されてしまう...
--乱数が主役というのがいいすぎだとしても、確率計算が重要...
** (4)
-JavaにはTreeMapが標準で用意されていてちょっとうらやまし...
* こめんと欄
-実際にベンチマークを書いて少し試したところでは、p=1/2よ...
#comment
終了行:
* スキップリスト
-(by [[K]], 2014.10.14)
** (0)
-今回はスキップリスト（SkipLists）の話。
** (1)
-多数のオブジェクトがある状態で、オブジェクトを高速に検索...
-行いたい操作は、次の通り。
--(a)要素の追加
--(b)要素の削除
--(c)要素をキーで整列させておいた状態において、i番目の要...
---これができれば先頭や末尾も取れる
--(d)ある要素を指定した時に、その要素が先頭から何番目であ...
--(e)あるキーを指定して、それより小さい要素のうちで最大の...
---つまり、2,4,6,8,10が登録されているときに、key=7で検索...
--(f)あるキーを指定して、それよりも大きい要素のうちで最小...
--(g)2つの要素の間にいくつの要素があるかを返す
--(h)2つの要素の間の要素を順番に列挙する
--なお、前提条件として、キーの重複はないとする。
-これらをやりたいならスキップリストがよさそうだと思った。
--http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%8...
--http://www.dd.iij4u.or.jp/~okuyamak/Information/SkipLis...
-スキップリストなら、(a)～(g)の操作がO(logN)でできそう。(...
--上記のwikipediaのページによれば、B木はさらに優秀らしい...
** (2)
-僕は先日これを実装した。高速化を少し意識して冗長な部分も...
-ちなみにp=1/4くらいがちょうどいいかなと思っている。p=1/2...
-この実装では、もちろん一般化された比較関数を採用して（参...
** (3)
-乱数を使うというのは、結果が乱数によって左右されてしまう...
--乱数が主役というのがいいすぎだとしても、確率計算が重要...
** (4)
-JavaにはTreeMapが標準で用意されていてちょっとうらやまし...
* こめんと欄
-実際にベンチマークを書いて少し試したところでは、p=1/2よ...
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
