为什么我的 `zipAll` 会出现 OutOfMemoryError 错误以及如何修复它？

Question

我正在尝试编写一个好的

zipAll

函数——不像 Scala 的函数，而是像 C++ 的

zip_view

：只是 Kotlin 的 zip，具有并行迭代的任意数量的序列，长度等于最短。

我想出了：

fun <T> zipAll(vararg seq: Sequence<T>): Sequence<List<T>> {
    return sequence { 
        while (seq.all { it.iterator().hasNext() }) 
            yield(seq.map { it.take(1).first() }) 
    }
}

fun main() {
    val s = sequenceOf(1,2,3)
    val s2 = sequenceOf(3,4,5,6)    
    println(zipAll(s, s2).toList())
}

但是 Kotlin Playground 提供了（编辑：使用来自我本地 IntelliJ Idea 的更完整的堆栈跟踪）

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.Arrays.copyOf(Arrays.java:3512)
    at java.base/java.util.Arrays.copyOf(Arrays.java:3481)
    at java.base/java.util.ArrayList.grow(ArrayList.java:237)
    at java.base/java.util.ArrayList.grow(ArrayList.java:244)
    at java.base/java.util.ArrayList.add(ArrayList.java:454)
    at java.base/java.util.ArrayList.add(ArrayList.java:467)
    at kotlin.sequences.SequencesKt___SequencesKt.toList(_Sequences.kt:816)

我做错了什么？

Answer 1

Sequence.iterator()

不一定会为 Sequence 的

rest

创建迭代器。对于可以迭代多次的序列，例如使用

sequenceOf

创建的序列，

iterator

为您提供一个全新的迭代器，从序列的开头开始。对于无法多次迭代的序列，第二次调用

iterator

将会 抛出异常。

因此，

while

条件永远不会为假，最终会创建一个无限序列。

您应该跟踪每个序列的迭代器：

fun <T> zipAll(vararg seq: Sequence<T>): Sequence<List<T>> {
    return sequence {
        val iterators = seq.map { it.iterator() }
        while (iterators.all { it.hasNext() })
            yield(iterators.map { it.next() })
    }
}