Ленивые сорта итераторов в Scala?

Ответ 1

Я использовал Scala реализацию очереди приоритетов для решения этой проблемы частичной сортировки:

import scala.collection.mutable.PriorityQueue

val q = PriorityQueue(1289, 12, 123, 894, 1)(Ordering.Int.reverse)

Теперь мы можем вызвать dequeue:

scala> q.dequeue
res0: Int = 1

scala> q.dequeue
res1: Int = 12

scala> q.dequeue
res2: Int = 123

Для построения очереди и O(k log n) стоит O(n), чтобы взять первые k элементы.

К сожалению, PriorityQueue не выполняет итерацию в порядке приоритета, но не так сложно записать итератор, который вызывает dequeue.

Ответ 2

В качестве примера я создал реализацию ленивого быстрого сортировки, создающую ленивую древовидную структуру (вместо создания списка результатов). Эта структура может быть запрошена для любого i -го элемента в O(n) времени или фрагмента элементов k. Повторный запрос того же элемента (или ближайшего элемента) принимает только O(log n), поскольку древовидная структура, построенная на предыдущем шаге, используется повторно. Для перемещения всех элементов требуется время O(n log n). (Все полагают, что мы выбрали разумные опорные точки.)

Ключ состоит в том, что поддеревья не построены сразу, они задерживаются в ленивом вычислении. Поэтому, когда вы запрашиваете только один элемент, корень node вычисляется в 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 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

Ответ 3

Вы можете использовать Stream для создания чего-то подобного. Вот простой пример, который определенно может быть улучшен, но, по-моему, он работает как пример.

def extractMin(xs: List[Int]) = {
  def extractMin(xs: List[Int], min: Int, rest: List[Int]): (Int,List[Int]) = xs match {
    case Nil => (min, rest)
    case head :: tail if head > min => extractMin(tail, min, head :: rest)
    case head :: tail => extractMin(tail, head, min :: rest)
  }

  if(xs.isEmpty) throw new NoSuchElementException("List is empty")
  else extractMin(xs.tail, xs.head, Nil)
}

def lazySort(xs: List[Int]): Stream[Int] = xs match {
  case Nil => Stream.empty
  case _ =>
    val (min, rest) = extractMin(xs)
    min #:: lazySort(rest)
}