つかびーの技術日記

情報系修士卒のWeb系技術日記です。現在のフォーカス分野はアドテクです。

ScalaのListとListBufferとScalazのDListで要素追加したときの速度

      2015/03/22

ScalazにDListというデータ構造があります。今日はその話です。

DListはappendがO(1)らしいです。こいつはいい!という訳で早速試してみました。

O(1)ということはリストのサイズが0だろうが、100万だろうが、appendする速度は同じ、ということです。では早速確認して行きます。

DListのO(1)とscala.ListのO(n)の確認

DListとScalaのListを2つずつ(要素0と要素100万を2つずつ)用意します。これらに対して10000回appendしてみます。

DList(初期要素0) 125 ms
DList(初期要素100万) 69 ms
ScalaList(初期要素0) 841 ms
ScalaList(初期要素100万) 243941 ms

ScalaのListはやはり遅いですね。それに比べてDList凄いです。DListは125msと69msなので、まあ誤差でしょう。これならO(1)と言ってよいレベルですね。

※実はtimeOfの実行順序を入れ替えると微妙に結果が変わったりします。JITのせいなのか確証はありませんが、一番始めに実行したものは微妙に遅くなるようです。

ListBufferも含めて先頭追加、末尾追加の速度比較

既に100万個要素が存在するList, ListBuffer, DListに対して10000回末尾または先頭に要素を追加したときの速度を比較してみました。

DList 末尾追加 263 ms
DList 先頭追加 70 ms
ScalaList 末尾追加 94814 ms
ScalaList 先頭追加 3 ms
ListBuffer 末尾追加 3 ms
ListBuffer 先頭追加 8 ms

DList 末尾追加は(多分)JITの関係上少し先頭追加より遅いですが、まあ同じですね。早い!ScalaのListの末尾追加はやはり遅いです。先頭への追加は恐ろしく早いです。これならListBufferいりませんね。そしてListBufferはやはり早かったです。

そんな訳で今回はDListを見てみました。かなり使えるデータ構造ですね!

 - Scala, ライブラリ ,