clases de iteradores perezosos en Scala?

Question

He leído que en haskell, al ordenar un iterador, solo evalúa la cantidad de qsort necesaria para devolver el número de valores realmente evaluados en el iterador resultante (es decir, es vago, es decir, una vez que se ha completado) el LHS del primer pivote y puede devolver un valor, puede proporcionar ese valor en una llamada a "siguiente" en el iterador y no continuar girando a menos que se vuelva a llamar al siguiente).

Por ejemplo, en haskell, head (qsort list) es O (n). Solo busca el valor mínimo en la lista y no ordena el resto de la lista a menos que se acceda al resto del resultado del qsort list.

¿Hay alguna manera de hacer esto en Scala? Quiero utilizar sortWith en una colección, pero solo ordenar tanto como sea necesario, de modo que pueda mySeq.sortWith (<) .tomar (3) y no tener que completar la operación de clasificación.

Me gustaría saber si otras funciones de ordenación (como sortBy) se pueden usar de forma perezosa, y cómo garantizar la pereza, y cómo encontrar cualquier otra documentación sobre cuándo las clases en Scala son o no evaluadas perezosamente .

ACTUALIZAR/EDITAR: Estoy idealmente buscando maneras de hacer esto con funciones de clasificación estándar como sortWith. Prefiero no tener que implementar mi propia versión de quicksort solo para obtener una evaluación perezosa. ¿No debería estar integrado en la biblioteca estándar, al menos para colecciones como Stream que admiten la pereza?

Answer 1

He usado Scala de priority queue implementation para resolver este tipo de problemas de clasificación parcial:

import scala.collection.mutable.PriorityQueue 

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

Ahora podemos llamar dequeue:

scala> q.dequeue 
res0: Int = 1 

scala> q.dequeue 
res1: Int = 12 

scala> q.dequeue 
res2: Int = 123 

Cuesta O(n) para construir la cola y O(k log n) tomar los primeros elementos k.

Desafortunadamente PriorityQueue no itera en orden de prioridad, pero no es demasiado difícil escribir un iterador que llame al dequeue.

Answer 2

Puede usar un Stream para construir algo así. Aquí hay un ejemplo simple, que definitivamente se puede mejorar, pero funciona como un ejemplo, supongo.

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) 
} 

Answer 3

Como ejemplo, he creado una implementación del perezoso rápido clase que crea una estructura de árbol perezoso (en lugar de producir una lista de resultados). Esta estructura se puede solicitar para cualquier elemento i -th en O(n) tiempo o una porción de elementos k. Pedir nuevamente el mismo elemento (o un elemento cercano) toma solo O(log n) ya que la estructura de árbol construida en el paso anterior se reutiliza. Atravesar todos los elementos lleva O(n log n) tiempo. (Todos suponiendo que hemos elegido pivotes razonables.)

La clave es que los subárboles no se crean de inmediato, sino que se retrasan en un cálculo lento. Por lo tanto, cuando se solicita solo un elemento, el nodo raíz se calcula en O(n), luego uno de sus subnodos en O(n/2) etc. hasta encontrar el elemento requerido, tomando O(n + n/2 + n/4 ...) = O(n). Cuando el árbol se evalúa por completo, seleccionar cualquier elemento toma O(log n) como con cualquier árbol balanceado.

Tenga en cuenta que la implementación de build es bastante ineficiente. Quería que fuera simple y tan fácil de entender como sea posible. Lo importante es que tiene los límites asintóticos apropiados.

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); 
    } 
} 

La salida será algo así como

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