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してみます。
import scala.collection.mutable.ListBuffer import scalaz.DList object Main { def main(args: Array[String]) { val defaultListSize: Int = 1000000 val addCount = 10000 // defaultListSizeで指定した長さのListBufferを作成しておきます val lb: ListBuffer[Int] = ListBuffer() for (i <- 0 until defaultListSize) { lb += i } // 上記ListBufferから各型のリストを作成しておきます var dListZero: DList[Int] = DList() var dListMillion: DList[Int] = DList.fromList(lb.toList) var scalaListZero: List[Int] = List() var scalaListMillion: List[Int] = lb.toList timeOf { for (i <- 0 until addCount) { dListZero = dListZero :+ i } dListZero.toList } timeOf { for (i <- 0 until addCount) { dListMillion = dListMillion :+ i } dListMillion.toList } timeOf { for (i <- 0 until addCount) { scalaListZero = scalaListZero :+ i } } timeOf { for (i <- 0 until addCount) { scalaListMillion = scalaListMillion :+ i } } } def timeOf[A](f: => A): A = { val start = System.currentTimeMillis val result = f val end = System.currentTimeMillis println("[Time] %s ms".format(end - start)) result } }
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回末尾または先頭に要素を追加したときの速度を比較してみました。
import scala.collection.mutable.ListBuffer import scalaz.DList object Main { def main(args: Array[String]) { val defaultListSize: Int = 1000000 val addCount = 10000 // defaultListSizeで指定した長さのListBufferを作成しておきます val lb: ListBuffer[Int] = ListBuffer() for (i <- 0 until defaultListSize) { lb += i } // 上記ListBufferから各型のリストを作成しておきます var dList: DList[Int] = DList.fromList(lb.toList) var dList2: DList[Int] = DList.fromList(lb.toList) var scalaList: List[Int] = lb.toList var scalaList2: List[Int] = lb.toList val scalaListBuffer: ListBuffer[Int] = ListBuffer() lb.copyToBuffer(scalaListBuffer) val scalaListBuffer2: ListBuffer[Int] = ListBuffer() lb.copyToBuffer(scalaListBuffer2) // ある程度の要素がある各Listに対してaddCountの数だけ要素を追加します。追加はListの前方と後方に半分ずつ追加します。 // DList末尾追加の場合 timeOf { for (i <- 0 until addCount) { dList = dList :+ i } dList.toList } // DList先頭追加の場合 timeOf { for (i <- 0 until addCount) { dList2 = i +: dList2 } dList2.toList } // List末尾追加の場合 timeOf { for (i <- 0 until addCount) { scalaList = scalaList :+ i } } // List先頭追加の場合 timeOf { for (i <- 0 until addCount) { scalaList2 = i +: scalaList2 } } // ListBuffer末尾追加の場合 timeOf { for (i <- 0 until addCount) { scalaListBuffer += i } scalaListBuffer.toList } // ListBuffer先頭追加の場合 timeOf { for (i <- 0 until addCount) { i +=: scalaListBuffer2 } scalaListBuffer2.toList } } def timeOf[A](f: => A): A = { val start = System.currentTimeMillis val result = f val end = System.currentTimeMillis println("[Time] %s ms".format(end - start)) result } }
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を見てみました。かなり使えるデータ構造ですね!