窥视迭代器

Peeking into an iterator

提问人：k314159 提问时间：9/26/2023 最后编辑：k314159 更新时间：9/26/2023 访问量：117

问：

在 Kotlin 中，有没有办法在不推进迭代器的情况下“窥视”迭代器的下一个元素？对于示例用例，请考虑以下函数来合并两个预排序序列：

fun merge(seq1: Sequence<Int>, seq2: Sequence<Int>) = sequence<Int> {
    val it1 = seq1.iterator()
    var current1 = if (it1.hasNext()) it1.next() else null
    val it2 = seq2.iterator()
    var current2 = if (it2.hasNext()) it2.next() else null

    while (current1 != null && current2 != null) {
        if (current1 <= current2) {
            yield(current1)
            current1 = if (it1.hasNext()) it1.next() else null
        } else {
            yield(current2)
            current2 = if (it2.hasNext()) it2.next() else null
        }
    }
    while (current1 != null) {
        yield(current1)
        current1 = if (it1.hasNext()) it1.next() else null
    }
    while (current2 != null) {
        yield(current2)
        current2 = if (it2.hasNext()) it2.next() else null
    }
}

这个函数必须跳过箍，因为接口没有办法在不推进它的情况下请求下一个元素。换句话说，它不遵循命令-查询分离原则。Iterator

如果我使用 Guava 的 PeekingIterator，我可以使这个函数更加简洁和可读：

fun merge(seq1: Sequence<Int>, seq2: Sequence<Int>) = sequence<Int> {
    val it1: PeekingIterator<Int> = Iterators.peekingIterator(seq1.iterator())
    val it2: PeekingIterator<Int> = Iterators.peekingIterator(seq2.iterator())

    while (it1.hasNext() && it2.hasNext())
        yield((if (it1.peek() <= it2.peek()) it1 else it2).next())
    yieldAll(it1)
    yieldAll(it2)
}

相同的功能从 24 行减少到 9 行！但是，在 Kotlin 项目中使用 Guava 让我感到不舒服。Guava 的创建是为了解决 Java API 的一些限制。Kotlin 标准库要丰富得多，我们不需要使用第三方 Java 库。有没有办法在不使用 Guava 的情况下使第一个代码示例更加简洁和可读？

附录

下面是上述函数的示例单元测试，它应该让你了解它应该如何表现：

import io.kotest.core.spec.style.FreeSpec
import io.kotest.matchers.shouldBe

class MyTest : FreeSpec({
    "merge test" {
        merge(emptySequence(), emptySequence()).toList() shouldBe emptyList()
        merge(emptySequence(), sequenceOf(1)).toList() shouldBe listOf(1)
        merge(emptySequence(), sequenceOf(1, 3)).toList() shouldBe listOf(1, 3)
        merge(sequenceOf(1), emptySequence()).toList() shouldBe listOf(1)
        merge(sequenceOf(1, 3), emptySequence()).toList() shouldBe listOf(1, 3)
        merge(sequenceOf(0, 3, 4), sequenceOf(1, 4, 7)).toList() shouldBe listOf(0, 1, 3, 4, 4, 7)
    }
)
Kotlin 迭代器 序列 石榴

评论

0赞 Christian Bongiorno 9/26/2023
你有一个显示你要做什么的函数是件好事，但是我们能得到一个带有馈线输入的主函数吗？我有一个想法，但在我给出答案之前，我想确保我重现你的确切情况
0赞 k314159 9/26/2023
@ChristianBongiorno 我编写了一个单元测试，它应该向您展示函数的预期行为方式。

答：

5赞 broot 9/26/2023 #1

我不认为 Kotlin stdlib 提供了这个，但我们可以自己实现它：

fun main() {
    val iter = listOf(1, 2, 3).iterator().peeking()

    println(iter.next()) // 1
    println(iter.peek()) // 2
    println(iter.peek()) // 2
    println(iter.next()) // 2
    println(iter.peek()) // 3
    println(iter.next()) // 3
    println(iter.peek()) // NoSuchElementException
}

fun <T> Iterator<T>.peeking() = object : PeekingIterator<T> {
    private var hasPeeked = false
    private var peeked: T? = null

    override fun hasNext(): Boolean = hasPeeked || [email protected]()

    override fun next(): T  {
        return if (hasPeeked) {
            hasPeeked = false
            @Suppress("UNCHECKED_CAST")
            peeked as T
        } else {
            [email protected]()
        }
    }

    override fun peek(): T {
        if (!hasPeeked) {
            peeked = [email protected]()
            hasPeeked = true
        }
        @Suppress("UNCHECKED_CAST")
        return peeked as T
    }
}

interface PeekingIterator<T> : Iterator<T> {
    fun peek(): T
}

评论

0赞 k314159 9/26/2023
我喜欢你使用 使结果不可为空，而不是使用它会在字节码中添加不必要的检查。如果可以通过 Contracts 说“hasPeeked == true 意味着 peeked ！= null”，那就太好了，这样就可以使强制转换（和警告抑制）变得不必要了。as T!!
1赞 broot 9/26/2023
@k314159我相信使用实际上是不正确的。如果为 nullable，则 null 是有效值，我们应该返回它 ：-）我们主要使用 然后强制转换为 以支持不可为 null 的情况，但我们最初仍然必须存储 null。还有其他解决方案可能在处理 .!!TTT?TTT
0赞 k314159 9/26/2023
你是对的，我们不能使用.为了避免重复抑制，我将通用代码拉到吸气器中，而不是在我的新答案中。!!TT?
1赞 k314159 9/26/2023
刚刚发现了一个小问题：如果迭代器已经过了所有元素，并且你调用并捕获了预期的元素，如果你随后调用它，它应该返回的时候返回。您可以通过将该行移动到下一行之后来解决此问题。peek()NoSuchElementExceptionhasNext()truefalsehasPeeked = true
0赞 broot 9/26/2023
@k314159 好渔获！
0赞 k314159 9/26/2023 #2

最后，我编写并使用了更简洁的 broot 代码版本：

interface PeekingIterator<T> : Iterator<T> {
    fun peek(): T
}

fun <T> Iterator<T>.peeking(): PeekingIterator<T> =
    if (this is PeekingIterator)
        this
    else
        object : PeekingIterator<T> {
            private var cached = false

            @Suppress("UNCHECKED_CAST")
            private var element: T = null as T
                get() {
                    if (!cached)
                        field = [email protected]()
                    return field
                }

            override fun hasNext(): Boolean = cached || [email protected]()

            override fun next(): T = element.also { cached = false }

            override fun peek(): T = element.also { cached = true }
        }

评论

2赞 broot 9/26/2023
如果你已经采用了这种方法，那么我认为你的几乎是......速看操作。基本上是偷看+重置布尔值。您可以将属性代码移动到 ，然后 add there，然后 。我喜欢这个部分 - 这比制作物业更好。element get()next()peek()cached = truenext() = peek().also { cached = false }null as TT?
0赞 Tenfour04 9/26/2023
codegolf.stackexchange.com:)
1赞 Tenfour04 9/26/2023
您可以通过使用 to 表示无值来消除已删除答案中的属性。pl.kotl.in/mjTRHr1ND虽然我认为理论上它可能会破坏 if is Any 并且原始迭代器是一个 MutableIterator，用于向 itelf 添加自己的 peeking 包装器。:/isPeekedthisT
2赞 broot 9/26/2023
@Tenfour04 与 ;-） 相比，最好使用 / ;特别是，因为我们在这里调用未知。===!==thisequals()
0赞 broot 9/26/2023
我喜欢讨论！很多好主意：-）

上一个：将 [样本、时间步长、特征] 转换为 2D 输入形状

下一个：在 matlab 中绘制一系列函数