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セット