У меня есть итератор строк, где каждая строка может быть "H"
(заголовок) или "D"
(деталь). Я хочу разделить этот итератор на блоки, где каждый блок начинается с одного заголовка и может содержать от 0 до многих деталей.
Я знаю, как решить эту проблему, загружая все в память. Например, код ниже:
Seq("H","D","D","D","H","D","H","H","D","D","H","D").toIterator
.foldLeft(List[List[String]]())((acc, x) => x match {
case "H" => List(x) :: acc
case "D" => (x :: acc.head) :: acc.tail })
.map(_.reverse)
.reverse
возвращает 5 блоков - List(List(H, D, D, D), List(H, D), List(H), List(H, D, D), List(H, D))
- это то, что я хочу.
Однако вместо List[List[String]]
в результате я хочу использовать Iterator[List[String]]
или некоторую другую структуру, которая позволяет мне лениво оценивать результат и не загружать весь ввод в память, если весь итератор в потребляемом я хочу загрузить в память только блок, потребляемый за один раз (например: когда я вызываю iterator.next
).
Как я могу изменить приведенный выше код для достижения желаемого результата?
РЕДАКТИРОВАТЬ: мне нужно это в Scala 2.11, в частности, поскольку среда, которую я использую, придерживается этого. Рад также принять ответы для других версий, хотя.
Всего 3 ответа
Вот самая простая реализация, которую я смог найти (это универсально и лениво):
/** takes 'it' and groups consecutive elements
* until next item that satisfy 'startGroup' predicate occures.
* It returns Iterator[List[T]] and is lazy
* (keeps in memory only last group, not whole 'it').
*/
def groupUsing[T](it:Iterator[T])(startGroup:T => Boolean):Iterator[List[T]] = {
val sc = it.scanLeft(List.empty[T]) {
(a,b) => if (startGroup(b)) b::Nil else b::a
}
(sc ++ Iterator(Nil)).sliding(2,1).collect {
case Seq(a,b) if a.length >= b.length => a.reverse
}
}
используйте это так:
val exampleIt = Seq("H1","D1","D2","D3","H2","D4","H3","H4","D5","D6","H5","D7").toIterator
groupUsing(exampleIt)(_.startsWith("H"))
// H1 D1 D2 D3 / H2 D4 / H3 / H4 D5 D6 / H5 D7
Вот спецификация:
X | GIVEN | EXPECTED |
O | | | empty iterator
O | H | H | single header
O | D | D | single item (not header)
O | HD | HD |
O | HH | H,H | only headers
O | HHD | H,HD |
O | HDDDHD | HDDD,HD |
O | DDH | DD,H | heading D's have no Header as you can see.
O | HDDDHDHDD | HDDD,HD,HDD |
scalafiddle с тестами и дополнительными комментариями: https://scalafiddle.io/sf/q8xbQ9N/11
(если ответ полезен, проголосуйте, пожалуйста. Я потратил на это слишком много времени :))
ВТОРАЯ РЕАЛИЗАЦИЯ:
Вы предлагаете версию , в которой не используется sliding
. Вот оно, но у него есть свои проблемы, перечисленные ниже.
def groupUsing2[T >: Null](it:Iterator[T])(startGroup:T => Boolean):Iterator[List[T]] = {
type TT = (List[T], List[T])
val empty:TT = (Nil, Nil)
//We need this ugly `++ Iterator(null)` to close last group.
val sc = (it ++ Iterator(null)).scanLeft(empty) {
(a,b) => if (b == null || startGroup(b)) (b::Nil, a._1) else (b::a._1, Nil)
}
sc.collect {
case (_, a) if a.nonEmpty => a.reverse
}
}
Черты:
T>:Null
типы. Нам просто нужно добавить элемент, который закроет последнюю коллекцию в конце (null идеально, но это ограничивает наш тип). Вот скалафддл: https://scalafiddle.io/sf/q8xbQ9N/11
Если вы используете Scala 2.13.x, вы можете создать новый Iterator
, развернув его поверх исходного Iterator
.
import scala.collection.mutable.ListBuffer
val data = Seq("H","D","D","D","H","D","H","H","D","D","H","D").iterator
val rslt = Iterator.unfold(data.buffered){itr =>
if (itr.hasNext) {
val lb = ListBuffer(itr.next())
while (itr.hasNext && itr.head == "D")
lb += itr.next()
Some((lb.toList, itr))
} else None
}
тестирование:
rslt.next() //res0: List[String] = List(H, D, D, D)
rslt.next() //res1: List[String] = List(H, D)
rslt.next() //res2: List[String] = List(H)
rslt.next() //res3: List[String] = List(H, D, D)
rslt.next() //res4: List[String] = List(H, D)
rslt.hasNext //res5: Boolean = false
Я думаю, scanLeft
операция scanLeft
может помочь в этом случае, если вы хотите использовать версию Scala 2.11.
Я хотел бы предложить следующее решение, но, боюсь, оно выглядит сложнее, чем оригинальное:
def main(args: Array[String]): Unit = {
sealed trait SequenceItem
case class SequenceSymbol(value: String) extends SequenceItem
case object Termination extends SequenceItem
/**
* _1 - HD sequence in progress
* _2 - HD sequences which is ready
*/
type ScanResult = (List[String], List[String])
val init: ScanResult = Nil -> Nil
val originalIterator: Iterator[SequenceItem] = Seq("H","D","D","D", "H","D", "H", "H","D","D", "H","D")
.toIterator.map(SequenceSymbol)
val iteratorWithTermination: Iterator[SequenceItem] = originalIterator ++ Seq(Termination).toIterator
val result: Iterator[List[String]] = iteratorWithTermination
.scanLeft(init) {
case ((progress, _), SequenceSymbol("H")) => List("H") -> progress
case ((progress, _), SequenceSymbol("D")) => ("D" :: progress) -> Nil
case ((progress, _), Termination) => Nil -> progress
}
.collect {
case (_, ready) if ready.nonEmpty => ready
}
.map(_.reverse)
println(result.mkString(", "))
}
Типы добавлены для удобства чтения. Надеюсь, это поможет!