例として、(結果リストを生成する代わりに) レイジー ツリー構造を作成するレイジー クイック ソートの実装を作成しました。iこの構造は、時間内の 番目の要素O(n)または要素のスライスを求めることができますk。同じ要素 (または近くの要素) をもう一度尋ねるとO(log n)、前のステップで構築されたツリー構造が再利用されるだけです。すべての要素をトラバースするには時間がかかりますO(n log n)。(すべて、妥当なピボットを選択したと仮定しています。)
重要なのは、サブツリーがすぐに構築されるのではなく、遅延計算で遅延することです。したがって、単一の要素のみを要求する場合、ルート ノードは で計算されO(n)、次にそのサブノードの 1 つが で計算され、O(n/2)必要な要素が見つかるまで、 が取得されO(n + n/2 + n/4 ...) = O(n)ます。ツリーが完全に評価されると、バランスの取れたツリーと同じように要素を選択できO(log n)ます。
の実装buildは非常に非効率的であることに注意してください。できるだけシンプルでわかりやすいものにしたかったのです。重要なことは、適切な漸近境界があることです。
import collection.immutable.Traversable
object LazyQSort {
/**
* Represents a value that is evaluated at most once.
*/
final protected class Thunk[+A](init: => A) extends Function0[A] {
override lazy val apply: A = init;
}
implicit protected def toThunk[A](v: => A): Thunk[A] = new Thunk(v);
implicit protected def fromThunk[A](t: Thunk[A]): A = t.apply;
// -----------------------------------------------------------------
/**
* A lazy binary tree that keeps a list of sorted elements.
* Subtrees are created lazily using `Thunk`s, so only
* the necessary part of the whole tree is created for
* each operation.
*
* Most notably, accessing any i-th element using `apply`
* takes O(n) time and traversing all the elements
* takes O(n * log n) time.
*/
sealed abstract class Tree[+A]
extends Function1[Int,A] with Traversable[A]
{
override def apply(i: Int) = findNth(this, i);
override def head: A = apply(0);
override def last: A = apply(size - 1);
def max: A = last;
def min: A = head;
override def slice(from: Int, until: Int): Traversable[A] =
LazyQSort.slice(this, from, until);
// We could implement more Traversable's methods here ...
}
final protected case class Node[+A](
pivot: A, leftSize: Int, override val size: Int,
left: Thunk[Tree[A]], right: Thunk[Tree[A]]
) extends Tree[A]
{
override def foreach[U](f: A => U): Unit = {
left.foreach(f);
f(pivot);
right.foreach(f);
}
override def isEmpty: Boolean = false;
}
final protected case object Leaf extends Tree[Nothing] {
override def foreach[U](f: Nothing => U): Unit = {}
override def size: Int = 0;
override def isEmpty: Boolean = true;
}
// -----------------------------------------------------------------
/**
* Finds i-th element of the tree.
*/
@annotation.tailrec
protected def findNth[A](tree: Tree[A], n: Int): A =
tree match {
case Leaf => throw new ArrayIndexOutOfBoundsException(n);
case Node(pivot, lsize, _, l, r)
=> if (n == lsize) pivot
else if (n < lsize) findNth(l, n)
else findNth(r, n - lsize - 1);
}
/**
* Cuts a given subinterval from the data.
*/
def slice[A](tree: Tree[A], from: Int, until: Int): Traversable[A] =
tree match {
case Leaf => Leaf
case Node(pivot, lsize, size, l, r) => {
lazy val sl = slice(l, from, until);
lazy val sr = slice(r, from - lsize - 1, until - lsize - 1);
if ((until <= 0) || (from >= size)) Leaf // empty
if (until <= lsize) sl
else if (from > lsize) sr
else sl ++ Seq(pivot) ++ sr
}
}
// -----------------------------------------------------------------
/**
* Builds a tree from a given sequence of data.
*/
def build[A](data: Seq[A])(implicit ord: Ordering[A]): Tree[A] =
if (data.isEmpty) Leaf
else {
// selecting a pivot is traditionally a complex matter,
// for simplicity we take the middle element here
val pivotIdx = data.size / 2;
val pivot = data(pivotIdx);
// this is far from perfect, but still linear
val (l, r) = data.patch(pivotIdx, Seq.empty, 1).partition(ord.lteq(_, pivot));
Node(pivot, l.size, data.size, { build(l) }, { build(r) });
}
}
// ###################################################################
/**
* Tests some operations and prints results to stdout.
*/
object LazyQSortTest extends App {
import util.Random
import LazyQSort._
def trace[A](name: String, comp: => A): A = {
val start = System.currentTimeMillis();
val r: A = comp;
val end = System.currentTimeMillis();
println("-- " + name + " took " + (end - start) + "ms");
return r;
}
{
val n = 1000000;
val rnd = Random.shuffle(0 until n);
val tree = build(rnd);
trace("1st element", println(tree.head));
// Second element is much faster since most of the required
// structure is already built
trace("2nd element", println(tree(1)));
trace("Last element", println(tree.last));
trace("Median element", println(tree(n / 2)));
trace("Median + 1 element", println(tree(n / 2 + 1)));
trace("Some slice", for(i <- tree.slice(n/2, n/2+30)) println(i));
trace("Traversing all elements", for(i <- tree) i);
trace("Traversing all elements again", for(i <- tree) i);
}
}
出力は次のようになります
0
-- 1st element took 268ms
1
-- 2nd element took 0ms
999999
-- Last element took 39ms
500000
-- Median element took 122ms
500001
-- Median + 1 element took 0ms
500000
...
500029
-- Slice took 6ms
-- Traversing all elements took 7904ms
-- Traversing all elements again took 191ms