tipi di iteratori pigri in Scala?

Question

Ho letto che in haskell, quando si ordina un iteratore, si valuta solo il qsort necessario per restituire il numero di valori effettivamente valutati sull'iteratore risultante (cioè, è pigro, cioè una volta completato l'LHS del primo pivot e può restituire un valore, può fornire un valore su una chiamata a "next" sull'iteratore e non continuare a pivoting a meno che il prossimo non venga chiamato di nuovo).

Ad esempio, in haskell, head (elenco qsort) è O (n). Trova solo il valore minimo nell'elenco e non ordina il resto dell'elenco a meno che non venga eseguito il resto del risultato di qsort list.

C'è un modo per farlo in Scala? Voglio usare sortWith su una raccolta ma solo ordinare il necessario, in modo tale che io possa mySeq.sortWith (<) .take (3) e non abbia bisogno di completare l'operazione di ordinamento.

Mi piacerebbe sapere se altre funzioni di ordinamento (come sortby) possono essere utilizzati in modo pigro, e come garantire la pigrizia, e come trovare qualsiasi altra documentazione su quando i tipi di Scala sono o non sono pigramente valutati .

UPDATE/EDIT: Sono idealmente alla ricerca di modi per farlo con le funzioni di ordinamento standard come sortWith. Preferirei non dover implementare la mia versione di quicksort solo per ottenere una valutazione pigra. Non dovrebbe essere incorporato nella libreria standard, almeno per le raccolte come Stream che supportano la pigrizia ??

Answer 1

ho usato Scala di priority queue implementation per risolvere questo tipo di parziale problema di ordinamento:

import scala.collection.mutable.PriorityQueue 

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

Ora possiamo chiamare dequeue:

scala> q.dequeue 
res0: Int = 1 

scala> q.dequeue 
res1: Int = 12 

scala> q.dequeue 
res2: Int = 123 

Il costo è O(n) per costruire la coda e O(k log n) a prendere i primi elementi k.

Sfortunatamente PriorityQueue non itera in ordine di priorità, ma non è troppo difficile scrivere un iteratore che chiama dequeue.

Answer 2

È possibile utilizzare uno Stream per creare qualcosa del genere. Ecco un semplice esempio, che può essere sicuramente migliorato, ma funziona come un esempio, immagino.

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

Per fare un esempio, ho creato un'implementazione del pigro quick-sort che crea una struttura ad albero pigro (invece di produrre un elenco dei risultati). Questa struttura può essere richiesta per qualsiasi elemento i -th nel tempo O(n) o una porzione di elementi . Richiedere di nuovo lo stesso elemento (o un elemento vicino) richiede solo O(log n) quando viene riutilizzata la struttura ad albero costruita nel passaggio precedente. Attraversare tutti gli elementi richiede il tempo O(n log n). (Tutti supponiamo di aver scelto pivot ragionevoli.)

La chiave è che i sottoalberi non sono costruiti subito, sono ritardati in un calcolo pigro. Quindi, quando si richiede un solo elemento, il nodo radice viene calcolato in O(n), quindi uno dei suoi nodi secondari in O(n/2) ecc. Fino a quando non viene trovato l'elemento richiesto, prendendo O(n + n/2 + n/4 ...) = O(n). Quando l'albero è completamente valutato, il prelievo di qualsiasi elemento richiede O(log n) come con qualsiasi albero bilanciato.

Si noti che l'implementazione di build è piuttosto inefficiente. Volevo che fosse semplice e facile da capire il più possibile. L'importante è che abbia i giusti limiti asintotici.

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

L'output sarà qualcosa di simile

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