Jak korzystać takeWhile z iterator w Scala

Question

Mam iteratorem elementów i chcę, aby spożywać je dopóki warunek jest spełniony w kolejnym elemencie, jak:

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

res1 daje oczekiwane List(1,1,1,1) ale res2 zwraca List(2,2), ponieważ iterator musiał sprawdzić element na pozycji 4.

Wiem, że lista zostanie zamówiona, więc nie ma sensu przechodzić przez całą listę, taką jak partition. Lubię zakończyć, gdy tylko warunek nie zostanie spełniony. Czy jest jakiś sprytny sposób na zrobienie tego z Iteratorami? Nie mogę wykonać iteratora z toList, ponieważ pochodzi on z bardzo dużego pliku.

Answer 1

Z drugiej moją odpowiedź (co zostawiłem osobna, ponieważ są one w dużej mierze związana), myślę, że można wdrożyć groupWhen na Iterator następująco:

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

Kiedy uruchamiam go na przykład:

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

mam List(List(1, 1, 1, 1), List(2, 2, 2))

Answer 2

Można użyć metody toStream na Iterator.

Stream to leniwy odpowiednik List.

Jak widać z implementation z toStream tworzy Stream bez przechodzenia przez cały Iterator.

Przechowuje wszystkie elementy w pamięci. Należy zlokalizować użycie łącza do Stream w niektórych zakresach lokalnych, aby zapobiec wyciekom pamięci.

Z Stream należy użyć span takiego:

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

Answer 3

Zgaduję trochę tutaj, ale w oświadczeniu „dopóki warunek jest spełniony w kolejnym elemencie”, to brzmi jak ty może zajrzeć do sposobu groupWhen na ListOps w 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)) 

Zasadniczo „porcjach "w górę sekwencji wejściowej po spełnieniu warunku ((A, A) => Boolean) między elementem a jego następcą. W powyższym przykładzie warunkiem jest równość, tak długo, jak element jest równy jego następcy, będą one w tym samym kawałku.

Answer 4

miałem podobną potrzebę, ale solution z @oxbow_lakes nie bierze w aby uwzględnić sytuację, w której lista zawiera tylko jeden element lub nawet jeśli lista zawiera elementy, które nie są powtarzane. Ponadto to rozwiązanie nie nadaje się dobrze do nieskończonego iteratora (chce "zobaczyć" wszystkie elementy, zanim da wynik).

Potrzebna mi była możliwość grupowania elementów sekwencyjnych zgodnych z predykatem, ale także pojedynczych elementów (zawsze mogę je odfiltrować, jeśli ich nie potrzebuję).Potrzebowałem, aby te grupy były dostarczane w sposób ciągły, bez czekania, aż oryginalny iterator zostanie całkowicie zużyty, zanim zostaną wyprodukowane.

wymyśliłem następujące podejście, które pracuje dla moich potrzeb, i że powinienem dzielić:

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

powyższe jest przy użyciu kilku klas pomocników:

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 
} 

Przykład użycia:

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

daje: List(List(1), List(2, 2), List(3, 3, 3), List(4), List(5, 5))
Jeśli chcesz odfiltrować pojedyncze elementy, po prostu zastosować filter lub withFilter po groupWhen

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

daje: List(List(34, 66), List(87, 13), List(97, 3))

Answer 5

najprostsze rozwiązanie znalazłem:

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

wyjściowy:

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

Bardzo krótki, ale dalej musisz użyć nowego iteratora.

Z każdej niezmiennej kolekcji byłoby podobne:

• użytku takeWhile kiedy chcesz tylko trochę prefiks kolekcji
• użycie rozpiętość kiedy trzeba odpocząć również.