एक उदाहरण के रूप में, मैं आलसी जल्दी तरह का कार्यान्वयन और एक आलसी वृक्ष संरचना (एक परिणाम सूची का निर्माण करने के बजाय) बनाता है बनाया। इस संरचना को i- O(n) समय में 0 तत्व या k तत्वों का एक टुकड़ा के लिए पूछा जा सकता है। उसी तत्व को फिर से पूछना (या पास के तत्व) को केवल O(log n) लगता है क्योंकि पिछले चरण में निर्मित पेड़ संरचना का पुन: उपयोग किया जाता है। सभी तत्वों को स्थानांतरित करने में O(n log n) समय लगता है। (सभी मानते हैं कि हमने उचित पिट्स चुना है।)
कुंजी यह है कि subtrees तुरंत नहीं बनाया गया है, वे आलसी गणना में देरी हो रही हैं। तो जब केवल एक तत्व के लिए पूछते हैं, तो O(n) में रूट नोड की गणना की जाती है, फिर 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
मेरे अपने प्रश्न की तरह लग रहा है का डुप्लिकेट का एक सा: http://stackoverflow.com/questions/2690989/lazy-quicksort-in- स्कैला/26 9 2084 # टिप्पणी 17053282_2692084 ... हालांकि वास्तव में मैं लाइब्रेरी अंतर्निहित कार्यक्षमता को समझने की कोशिश कर रहा हूं, न कि मैं अपने आप को क्या कार्यान्वित कर सकता हूं। – Brian