データが主食

データエンジニアの備忘録。分析だったり、読んだ本のメモだったり。

データ構造「Conc Tree」を調べた

Scalaで並列プログラミングを勉強している中で、今まで知らなかったデータ構造「Conc Tree」に出会ったので整理してみました。

原著

最初に紹介されたは2015年の論文のようです。

Conc-Trees for Functional and Parallel Programming

Oracle従業員のAleksandar ProkopecとScalaを作ったMartin Oderskyの共著です。 Martin Oderskyの共著ということもあって期待できます。

背景

並列処理をする際には、各プロセス/スレッドなどでの処理結果をまとめあげることで、最終成果物となります(下図)。この時、各プロセス/スレッドからメモリに書き込むことになるので、メモリがボトルネックになりがちです。

具体的には - 各プロセス/スレッドがflatMapした結果のelementを追記していく処理 - 各プロセス/スレッドの成果物をconcatする処理 を高速に扱えるデータ構造が求められます。

f:id:ktr89:20190202222112p:plain http://aleksandar-prokopec.com/slides/conc.html#/9

Conc Treeの実装

Conc Treeの特徴はこんな感じ。

  • 要素のSequence
  • append/prepend 計算量O(1)
  • insert/remove 計算量O(log n )
  • concat 計算量O(log n)

wikipediaにScalaでの実装例があったので拝借します。

trait Conc[T] {
  def left: Conc[T]
  def right: Conc[T]
  def level: Int
  def size: Int
}

case class Empty[T] extends Conc[T] {
  def level = 0
  def size = 0
}

case class Single[T](elem: T) extends Conc[T] {
  def level = 0
  def size = 1
}

case class <>[T](left: Conc[T], right: Conc[T]) extends Conc[T] {
  val level = 1 + math.max(left.level, right.level)
  val size = left.size + right.size
}

def concat(xs: Conc[T], ys: Conc[T]) {
  val diff = ys.level - xs.level
  if (math.abs(diff) <= 1) new <>(xs, ys)
  else if (diff < -1) {
    if (xs.left.level >= xs.right.level) {
      val nr = concat(xs.right, ys)
      new <>(xs.left, nr)
    } else {
      val nrr = concat(xs.right.right, ys)
      if (nrr.level == xs.level - 3) {
        val nr = new <>(xs.right.left, nrr)
        new <>(xs.left, nr)
      } else {
        val nl = new <>(xs.left, xs.right.left)
        new <>(nl, nrr)
      }
    }
  } else {
    // symmetric case
  }
}

case class Append[T](left: Conc[T], right: Conc[T]) extends Conc[T] {
  val level = 1 + math.max(left.level, right.level)
  val size = left.size + right.size
}

private def append[T](xs: Append[T], ys: Conc[T]) =
  if (xs.right.level > ys.level) new Append(xs, ys)
  else {
    val zs = new <>(xs.right, ys)
    xs.left match {
      case ws @ Append(_, _) => append(ws, zs)
      case ws => if (ws.level <= xs.level) concat(ws, zs) else new Append(ws, zs)
    }
  }
}

https://en.wikipedia.org/wiki/Conc-tree_list

Conc Treeの処理オーダー

concatはO(log n)で計算ができるようです。また、append処理は最悪でもO(log n)で計算できます。並列処理なので、最低でもO(log n)であって欲しいところですが、これであれば並列処理で十分に利用できそうです。

f:id:ktr89:20190202225127p:plain

http://aleksandar-prokopec.com/slides/conc.html#/28

参考