SkipListのベンチマーク

要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ

上記エントリに書いたSkipListとSkipListSetのベンチマークを取ってみました。数値の単位はミリ秒、CPUはCore Duo 1.66GHzです。

タスク ArrayList LinkedList SkipList SkipListSet
insert[tail] 25 119 294 406
insert[head] 2821 145 264 349
insert[middle] 1376 8785 344 419
remove[tail] 13 17 160 160
remove[head] 2581 15 63 65
remove[middle] 1294 7660 148 154
indexOf 40887 46102 42206 169
get 6 7984 64 68
iterator 15 9 10 10

タスクの中身はこんな感じです。

insert[tail/head/middle]
空のリストの末尾/先頭/中間位置に要素を20000個挿入×10セット
remove[tail/head/middle]
20000個の要素が入ったリストの末尾/先頭/中間位置から要素を20000回削除×10セット
indexOf
20000個の要素が入ったリストの全要素のインデックスをindexOf()で順に取得×10セット
get
20000個の要素が入ったリストの全要素をget()で順に取得×10セット
iterator
20000個の要素が入ったリストの全要素をiterator()で順に取得×10セット