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

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

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

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

DListとScalaのListを２つずつ（要素０と要素１００万を２つずつ）用意します。これらに対して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を見てみました。かなり使えるデータ構造ですね！