2015-07-05 16 views
5

Ho bisogno di un metodo che può dividere Iterator[Char] in linee (separati da \n e \r)dividere un iteratore da un predicato

Per questo, ho scritto un metodo generale che ottiene un iteratore e un predicato e dividerà l'iteratore ogni volta che il predicato è vero. Questo è simile a span, ma sarà diviso ogni volta che il predicato è vero, non solo la prima volta

questa è la mia realizzazione:

def iterativeSplit[T](iterO: Iterator[T])(breakOn: T => Boolean): Iterator[List[T]] = 
new Iterator[List[T]] { 
    private var iter = iterO 
    def hasNext = iter.hasNext 

    def next = { 
    val (i1,i2) = iter.span(el => !breakOn(el)) 
    val cur = i1.toList 
    iter = i2.dropWhile(breakOn) 
    cur 
    } 
}.withFilter(l => l.nonEmpty) 

e funziona bene su piccoli ingressi, ma sugli ingressi larges , questo funziona molto lenta, ed eccezione di overflow a volte vengo impilare

qui è il codice che ricrea il problema:

val iter = ("aaaaaaaaabbbbbbbbbbbccccccccccccc\r\n" * 10000).iterator 
iterativeSplit(iter)(c => c == '\r' || c == '\n').length 

l'analisi dello stack durante la corsa è:

... 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:615) 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
at scala.collection.Iterator$$anon$18.hasNext(Iterator.scala:591) 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:615) 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
at scala.collection.Iterator$$anon$18.hasNext(Iterator.scala:591) 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
at scala.collection.Iterator$$anon$19.hasNext(Iterator.scala:615) 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
at scala.collection.Iterator$$anon$18.hasNext(Iterator.scala:591) 
at scala.collection.Iterator$$anon$1.hasNext(Iterator.scala:847) 
... 

guardando il codice sorgente (sto usando Scala 2.10.4) linea 591 è la hasNext del secondo iteratore dalla span, e la linea 651 è il hasNext nel iteratore da dropWhile

Credo che sto utilizzando quei 2 iteratori in modo non corretto, ma non riesco a capire perché

risposta

4

è possibile semplificare il codice come segue, che sembra risolvere il problema:

def iterativeSplit2[T](iter: Iterator[T])(breakOn: T => Boolean): Iterator[List[T]] = 
    new Iterator[List[T]] { 
     def hasNext = iter.hasNext 

     def next = { 
     val cur = iter.takeWhile(!breakOn(_)).toList 
     iter.dropWhile(breakOn) 
     cur 
     } 
    }.withFilter(l => l.nonEmpty) 

Invece di utilizzare span (quindi è necessario sostituire iter a ogni chiamata a next), è sufficiente utilizzare takeWhile e dropWhile sull'originale iter. Quindi non è necessario il var.

penso che la causa del tuo stack overflow originale è che chiamando ripetutamente span crea una lunga catena di Iterator s, ciascuna di cui hasNext metodi chiama la hasNext del suo genitore Iterator. Se si guarda lo source code per Iterator, è possibile vedere che ogni span crea nuovi iteratori che inoltrano le chiamate a hasNext all'iteratore originale (tramite uno BufferedIterator, che aumenta ulteriormente lo stack di chiamate).

Aggiornamento dopo aver consultato il documentation sembra che, anche se la mia soluzione di cui sopra sembra funzionare, non è consigliabile - vedi in particolare:

E 'di particolare importanza per notare che, salvo diversa indicazione, non si dovrebbe mai usare un iteratore dopo aver chiamato un metodo su di esso. [...] L'uso del vecchio iteratore non è definito, è soggetto a modifiche e potrebbe comportare anche modifiche al nuovo iteratore.

che si applica a takeWhile e dropWhile (e span), ma non next o hasNext.

E 'possibile utilizzare span come nella soluzione originale, ma utilizzando i flussi piuttosto che iteratori, e ricorsione:

def split3[T](s: Stream[T])(breakOn: T => Boolean): Stream[List[T]] = s match { 
    case Stream.Empty => Stream.empty 
    case s => { 
     val (a, b) = s.span(!breakOn(_)) 
     a.toList #:: split3(b.dropWhile(breakOn))(breakOn) 
    } 
    } 

Ma la prestazione è abbastanza terribile. Sono sicuro che ci deve essere un modo migliore ...

Aggiornamento 2: Ecco una soluzione molto imperativo che ha prestazioni migliori:

import scala.collection.mutable.ListBuffer 

    def iterativeSplit4[T](iter: Iterator[T])(breakOn: T => Boolean): Iterator[List[T]] = 
    new Iterator[List[T]] { 
     val word = new ListBuffer[T] 
     def hasNext() = iter.hasNext 

     def next = { 
     var looking = true 
     while (looking) { 
      val c = iter.next 
      if (breakOn(c)) looking = false 
      else word += c 
     } 
     val w = word.toList 
     word.clear() 
     w 
     } 
    }.withFilter(_.nonEmpty) 
+0

Ben fatto, grazie. E ora anche il 'dropWhile' non è necessario poiché il filtro si prenderà cura degli elementi che si spezzano. – lev

+0

Ho aggiornato la mia risposta, poiché mi sono reso conto che la mia soluzione originale utilizza tecniche fortemente scoraggiate nella documentazione. – DNA

+1

Questo è grandioso, grazie! Per prevenire un errore durante l'uso di 'toList' sull'iter iter diviso, ho aggiunto' while (cercando && iter.hasNext) ' – ValD

Problemi correlati