与正常序列相比，不同的序列需要更少的时间来迭代

Question

我一直在阅读有关 Kotlin 序列的文章，发现 distinct 方法是一个 stateful intermediate 操作。我猜它是 stateful 因为显然它需要跟踪它刚刚看到的元素才能删除重复项；还有一些代码实际上在做重复检查吗？

当我在不使用 Sequence.distinct 的情况下检查我的代码所花费的时间时，它执行了 50920 ms。但是使用 distinct 操作花费的时间更少，32548 ms。这对我来说没有意义，因为应该有额外的代码来检查重复项。这里的权衡是什么，我错过了什么？

这是我用来测试的代码，我只是多次组成一个字母序列然后调用 distinct:

val alphabet = sequenceOf( "", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9")

fun iterate(digits: Int): Sequence<String> {
    var sequence = alphabet.asSequence()
    for (i in 1 until digits)
        sequence = iterate(sequence)
    return sequence.distinct()    // <--- this is where i add or remove the distinct
}

fun iterate(sequence: Sequence<String>) = sequence {
    sequence.forEach { c1 ->
        alphabet.forEach { c2 ->
            yield("$c1$c2")
        }
    }
}

我一直在做测试:

iterate(7).forEach(::println)

所以 println 是否可能比重复检查花费更多时间，因为 I/O 总是很重？我完全没有头绪和愚蠢，所以任何解释将不胜感激。

编辑：

根据 cactustictacs 的回答，我重新运行生成 7 位数单词的代码，因此生成的单词总数为 11^7 == 19'487'171 （我尝试了 8 位数单词，但我不断得到每次我使用 distinct 时都会出现 OutOfMemoryError，可能是因为它会跟踪它找到的元素，所以我无法真正与更多元素进行比较。

这是结果（以毫秒为单位）：

Run #	With distinct	Without distinct
1	34015	47687
2	32454	48232
3	32842	47384
4	31037	47084
5	32224	48030
6	31660	47129
7	31678	48407
8	32123	51186
9	35136	48671
10	32245	47698

Answer 1

所以是相同的代码，只是最后多了一个 distinct() 操作？是的，这应该会使它花费更长的时间，因为您正在做额外的工作并不能使它更有效率。

但实际执行时间取决于系统资源，而循环是运行ning - 如果系统繁忙，您会看到更长的时间。如果你想对这些东西进行基准测试，你需要运行多次，然后选择最一致的数字 - 也许是中位数结果（所以你忽略了任何异常值）

您可能需要更大的最终序列才能看到运行宁 distinct 与 distinct 之间任何显着的一致差异！

编辑 - 我错过了您打印序列中的每个项目的一些非常大的数字，在这种情况下，是的，您是对的，这可能会成为瓶颈！调用 distinct() 会显着减少这里的工作，因为生成序列的方式会产生很多重复项，尤其是当迭代次数变大时：

fun main() {
    for (i in 1..5) {
        val results = iterate(i)
        val total = results.count()
        val distinct = results.distinct().count()
        println("$i) total: $total - difference: ${total - distinct}")
    }
}

1) total: 11 - difference: 0
2) total: 121 - difference: 10
3) total: 1331 - difference: 220
4) total: 14641 - difference: 3530
5) total: 161051 - difference: 49940

通过 5 次迭代，您将去除几乎三分之一的结果！那种工作一般很快，打印到输出没那么多。尝试对每个阶段（处理和打印）进行基准测试并查看它们的平均值 - 因为它是一个序列，所以您需要使用它来单独执行“处理”步骤，运行ning count() 是一种轻量级的方法。然后你可以将它与“处理+打印”版本进行比较，看看打印增加了多少开销

仅供参考（如果您没有将此作为压力测试），您可以通过在每次迭代中产生每个数字来避免 distinct 调用：

// you don't really gain anything by having this as a sequence (it's slower too),
// but I'm keeping it the same for comparison's sake
val alphabet = (0..9).map(Int::toString).asSequence()

fun iterate(sequence: Sequence<String>) = sequence {
    // combo each item with each element in the sequence (if any)
    // this produces items at least two-digits long
    sequence.forEach { c1 ->
        alphabet.forEach { c2 ->
            yield("$c1$c2")
        }
    }
    // also yield all the single digits
    alphabet.forEach( { yield(it) })
}

这样一来，第一次迭代只会产生个位数的项目。接下来扩展其中的每一个以创建所有两位数的组合，并且也添加一位数的项目。第三次迭代扩展了其中的每一个，创建了所有的 3 位和 2 位组合，并将个位数的组合添加回...

你永远不会产生重复，因为每一轮实际上只是添加当前序列的所有可能扩展。像您一样使用空白字符会使事情变得复杂，因为每一轮都会添加每个项目的扩展版本，但也会添加所有内容的非扩展副本。直接把所有 x-length 项目变成所有可能的 x+1-length 项目，然后扔掉所有个位数的项目更容易返回（因为前面序列中的那些扩展到两位数）

我希望这不会太混乱，我觉得这是一个过于复杂的解释。此外，这种方式不会产生一个空字符串作为序列的一部分（"" + "" + ""... 的组合）——如果你需要，你可以做 return sequence.plus("") 或某事

我在 5 次迭代中获得了 2-3 倍的速度提升 - 这不仅仅是 distinct 调用，你首先避免了重复工作，并且随着更多的迭代，低效率确实可以加起来！特别是sequences，内存效率高，可以让你早点停下来，但是运行比iterables慢很多

与正常序列相比，不同的序列需要更少的时间来迭代

Distinct sequence takes less time to iterate compared to normal sequence

sequence

execution-time

kotlin