Как использовать TakeWhile с итератора в Scala

Question

У меня есть итератор элементов, и я хочу, чтобы потреблять их, пока условие не будет выполнено в следующем элементе, как:

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

res1 дает ожидаемый List(1,1,1,1) но res2 возвращает List(2,2), потому что итератору пришлось проверить элемент в позиции 4.

Я знаю, что список будет заказан, поэтому нет смысла перебирать весь список, как partition. Мне нравится закончить, как только условие не будет выполнено. Есть ли какой-нибудь умный способ сделать это с помощью итераторов? Я не могу сделать toList итератору, потому что он исходит из очень большого файла.

Answer 1

С моим другим ответом (который я оставил отдельным, поскольку они в значительной степени связаны), я думаю, что вы можете реализовать groupWhen на Iterator следующим образом:

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

Когда я бег это на примере:

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

я List(List(1, 1, 1, 1), List(2, 2, 2))

Answer 2

Вы можете использовать способ toStream на Iterator.

Stream - ленивый эквивалент List.

Как вы можете видеть от implementation от toStream, он создает Stream без пересечения всего Iterator.

Stream сохраняет все элементы памяти. Вы должны локализовать использование ссылки на Stream в некоторых локальных целях, чтобы предотвратить утечку памяти.

С Stream вы должны использовать span так:

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

Answer 3

Я угадал немного здесь, но в заявлении «пока условие не будет выполнено в следующем элементе», это звучит, как вы могли бы хочу посмотреть на groupWhen методом на ListOps в 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)) 

в основном это «кусковые «вверх входная последовательность при условии (a (A, A) => Boolean) встречается между элементом и его преемником. В приведенном выше примере условие равно равенству, поэтому, пока элемент равен его преемнику, они будут в одном куске.

Answer 4

у меня была подобная необходимость, но solution от @oxbow_lakes не принимает в для учета ситуации, когда список имеет только один элемент, или даже если список содержит элементы, которые не повторяются. Кроме того, это решение не поддается бесконечному итератору (он хочет «видеть» все элементы, прежде чем он даст вам результат).

Мне нужна была возможность группировать последовательные элементы, которые соответствуют предикату, но также включают в себя отдельные элементы (я всегда могу отфильтровать их, если они мне не нужны).Я нуждался в том, чтобы эти группы были доставлены непрерывно, не дожидаясь полного потребления оригинального итератора до их производства.

я придумал следующий подход, который работает для моих потребностей, и думал, что я должен поделиться:

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

Выше, используя несколько вспомогательных классов:

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 
} 

Пример использования:

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

дает: List(List(1), List(2, 2), List(3, 3, 3), List(4), List(5, 5))
Если Вы хотите, чтобы отфильтровать отдельные элементы, просто применить filter или withFilter после groupWhen

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

дает: List(List(34, 66), List(87, 13), List(97, 3))

Answer 5

Самое простое решение я нашел:

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

выход:

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

Очень короткий, но в дальнейшем вам нужно использовать новый итератор.

С любым неизменным коллекции было бы похоже:

• использование TakeWhile когда вы хотите только некоторый префикс коллекции,
• использование диапазона, когда вам нужно отдохнуть также.