Come usare TakeWhile con un iteratore in Scala

Question

Ho un Iterator di elementi e voglio consumare loro fino a quando viene soddisfatta una condizione nell'elemento prossimo, come:

val it = List(1,1,1,1,2,2,2).iterator 
val res1 = it.takeWhile(_ == 1).toList 
val res2 = it.takeWhile(_ == 2).toList 

res1 dà un atteso List(1,1,1,1) ma res2 restituisce List(2,2) perché l'iteratore doveva controllare l'elemento nella posizione 4.

So che l'elenco verrà ordinato in modo che non vi sia alcun punto in cui attraversare l'intero elenco come partition. Mi piace finire non appena la condizione non è soddisfatta. C'è qualche modo intelligente per farlo con Iterators? Non posso fare un toList per l'iteratore perché proviene da un file molto grande.

Answer 1

Con la mia altra risposta (che ho lasciato a parte in quanto sono in gran parte estranei), penso che si può implementare groupWhen su Iterator come segue:

def groupWhen[A](itr: Iterator[A])(p: (A, A) => Boolean): Iterator[List[A]] = { 
    @annotation.tailrec 
    def groupWhen0(acc: Iterator[List[A]], itr: Iterator[A])(p: (A, A) => Boolean): Iterator[List[A]] = { 
    val (dup1, dup2) = itr.duplicate 
    val pref = ((dup1.sliding(2) takeWhile { case Seq(a1, a2) => p(a1, a2) }).zipWithIndex collect { 
     case (seq, 0)  => seq 
     case (Seq(_, a), _) => Seq(a) 
    }).flatten.toList 
    val newAcc = if (pref.isEmpty) acc else acC++ Iterator(pref) 
    if (dup2.nonEmpty) 
     groupWhen0(newAcc, dup2 drop (pref.length max 1))(p) 
    else newAcc 
    } 
    groupWhen0(Iterator.empty, itr)(p) 
} 

quando l'eseguo su un esempio:

println(groupWhen(List(1,1,1,1,3,4,3,2,2,2).iterator)(_ == _).toList) 

ottengo List(List(1, 1, 1, 1), List(2, 2, 2))

Answer 2

È possibile utilizzare il metodo toStream su Iterator.

Stream è un equivalente pigro di List.

Come si può vedere da implementation di toStream crea un Stream senza attraversare l'intero Iterator.

Stream conserva tutto l'elemento in memoria. È necessario localizzare l'utilizzo del collegamento su Stream in un ambito locale per evitare perdite di memoria.

Con Stream si dovrebbe usare span come questo:

val (res1, rest1) = stream.span(_ == 1) 
val (res2, rest2) = rest1.span(_ == 2) 

Answer 3

sto cercando di indovinare un po 'qui, ma dalla dichiarazione "fino a quando una condizione è soddisfatta nel successivo elemento", suona come si potrebbe vuole guardare il metodo groupWhen su ListOps in scalaz

scala> import scalaz.syntax.std.list._ 
import scalaz.syntax.std.list._ 

scala> List(1,1,1,1,2,2,2) groupWhen (_ == _) 
res1: List[List[Int]] = List(List(1, 1, 1, 1), List(2, 2, 2)) 

fondamentalmente questo "pezzi "la sequenza di input su una condizione (a (A, A) => Boolean) viene soddisfatta tra un elemento e il suo successore. Nell'esempio sopra la condizione è l'uguaglianza, quindi, finché un elemento è uguale al suo successore, si troveranno nello stesso blocco.

Answer 4

ho avuto una simile esigenza, ma il solution da @oxbow_lakes non prendere in per rendere conto della situazione quando la lista ha un solo elemento, o anche se la lista contiene elementi che non sono ripetuti. Inoltre, quella soluzione non si presta bene a un iteratore infinito (vuole "vedere" tutti gli elementi prima che ti dia un risultato).

Ciò di cui avevo bisogno era la possibilità di raggruppare elementi sequenziali che corrispondono a un predicato, ma anche includere i singoli elementi (posso sempre filtrarli se non ne ho bisogno).Avevo bisogno che quei gruppi venissero consegnati continuamente, senza dover aspettare che l'iteratore originale fosse completamente consumato prima di essere prodotto.

mi si avvicinò con il seguente approccio che funziona per le mie esigenze, e ho pensato che avrei dovuto condividere:

implicit class IteratorEx[+A](itr: Iterator[A]) { 
    def groupWhen(p: (A, A) => Boolean): Iterator[List[A]] = new AbstractIterator[List[A]] { 
    val (it1, it2) = itr.duplicate 
    val ritr = new RewindableIterator(it1, 1) 

    override def hasNext = it2.hasNext 

    override def next() = { 
     val count = (ritr.rewind().sliding(2) takeWhile { 
     case Seq(a1, a2) => p(a1, a2) 
     case _ => false 
     }).length 

     (it2 take (count + 1)).toList 
    } 
    } 
} 

È possibile che questo

sta usando un paio di classi di supporto:

abstract class AbstractIterator[A] extends Iterator[A] 

/** 
* Wraps a given iterator to add the ability to remember the last 'remember' values 
* From any position the iterator can be rewound (can go back) at most 'remember' values, 
* such that when calling 'next()' the memoized values will be provided as if they have not 
* been iterated over before. 
*/ 
class RewindableIterator[A](it: Iterator[A], remember: Int) extends Iterator[A] { 
    private var memory = List.empty[A] 
    private var memoryIndex = 0 

    override def next() = { 
    if (memoryIndex < memory.length) { 
     val next = memory(memoryIndex) 
     memoryIndex += 1 
     next 
    } else { 
     val next = it.next() 
     memory = memory :+ next 
     if (memory.length > remember) 
     memory = memory drop 1 
     memoryIndex = memory.length 
     next 
    } 
    } 

    def canRewind(n: Int) = memoryIndex - n >= 0 

    def rewind(n: Int) = { 
    require(memoryIndex - n >= 0, "Attempted to rewind past 'remember' limit") 
    memoryIndex -= n 
    this 
    } 

    def rewind() = { 
    memoryIndex = 0 
    this 
    } 

    override def hasNext = it.hasNext 
} 

uso Esempio:

List(1,2,2,3,3,3,4,5,5).iterator.groupWhen(_ == _).toList 

dà: List(List(1), List(2, 2), List(3, 3, 3), List(4), List(5, 5))
Se si desidera filtrare i singoli elementi, basta applicare un filter o withFilter dopo groupWhen

Stream.continually(Random.nextInt(100)).iterator 
     .groupWhen(_ + _ == 100).withFilter(_.length > 1).take(3).toList 

dà: List(List(34, 66), List(87, 13), List(97, 3))

Answer 5

La soluzione più semplice che ho trovato:

val it = List(1,1,1,1,2,2,2).iterator 
val (r1, it2) = it.span(_ == 1) 

println(s"group taken is: ${r1.toList}\n rest is: ${it2.toList}") 

uscita:

group taken is: List(1, 1, 1, 1) 
rest is: List(2, 2, 2) 

Molto breve ma più avanti devi usare il nuovo iteratore.

Con qualsiasi raccolta immutabile sarebbe simile:

• uso TakeWhile quando si desidera solo alcuni prefisso raccolta,
• utilizzo arco quando si ha bisogno di riposo anche.