为什么标准迭代器比 Kotlin 中的序列快？

Question

我是序列的新手，所以我可能做了一些（或多或少）非常错误的事情，但我有一个问题：

我写了两个函数：

fun isPrimeNumber1(number: Int): Boolean {
    if (number <= 1) return false
    for (divider in 2 .. number / 2) {
        if ( number % divider == 0 ) return false
    }
    return true
}

和

fun isPrimeNumber2(number: Int): Boolean {
    if (number <= 1) return false
    return !(2 .. number / 2).asSequence().map { it }.any { number % it == 0 }
}

现在我是运行一个用 kotest 编写的测试，其中两个函数都将 Int.MAX_VALUE 接收为 number。

class MyTestPrime : FunSpec({
    context("Prime numbers") {
        test("Should return true if number is prime (1st fun)") {
            isPrimeNumber1(Int.MAX_VALUE) shouldBe true
        }
        test("Should return true if number is prime (2nd fun)") {
            isPrimeNumber2(Int.MAX_VALUE) shouldBe true
        }
    }
})

isPrimeNumber1() 函数的执行时间约为 3.5 秒，第二个函数 isPrimeNumber2() - 约为 8.5 秒。

为什么会这样？我是否缺少有关序列的内容？或者也许我的代码以正确但非常不理想的方式实现其目的？

Answer 1

符合预期。带有序列的变体创建一个 Iterator 对象，并为每个元素调用 .hasNext() 和 .next() 函数。

由于 Iterator 使用对象而不是基元，因此您的所有 int 都通过 Integer::valueOf 调用进行装箱。（注意：.map { it }步骤是多余的）。

我运行这两个函数都通过 Java IntelliJ Idea 中的 Flight Recorder 运行，我们可以看到与其他变体相比，序列变体导致更多的函数调用。

isPrimeNumber1:

isPrimeNumber2:

如您所见，isPrimeNumber2 变体会导致在后台调用更多函数，因此会受到它们开销的影响。

另一种检查方法是将两个函数的字节码反编译为 Java。它可以让您更好地了解引擎盖下发生的事情。这是反编译的两个函数（再次使用 IntelliJ）：

private static final boolean isPrimeNumber1(int number) {
  if (number <= 1) {
    return false;
  } else {
    int divider = 2;
    int var2 = number / 2;
    if (divider <= var2) {
      while (true) {
        if (number % divider == 0) {
          return false;
        }

        if (divider == var2) {
          break;
        }

        ++divider;
      }
    }

    return true;
  }
}

private static final boolean isPrimeNumber2(int number) {
  if (number <= 1) {
    return false;
  } else {
    byte var1 = 2;
    Sequence $this$any$iv =
        SequencesKt.map(
            CollectionsKt.asSequence((Iterable) (new IntRange(var1, number / 2))),
            (Function1) null.INSTANCE);
    int $i$f$any = false;
    Iterator var3 = $this$any$iv.iterator();

    boolean var10000;
    while (true) {
      if (var3.hasNext()) {
        Object element$iv = var3.next();
        int it = ((Number) element$iv).intValue();
        int var6 = false;
        if (number % it != 0) {
          continue;
        }

        var10000 = true;
        break;
      }

      var10000 = false;
      break;
    }

    return !var10000;
  } 
}

最后说明： 正如其他人提到的，要获得有意义的性能测量，您需要使用像 jmh 这样的工具。然而，根据经验，更简单的语言结构，例如对序列的常规 for/while 循环，由于它们提供的抽象级别较低，往往开销较小。

Answer 2

Utku 的回答涵盖了原因（是的，sequence 代码在这里不太理想）但一般来说 - Sequences 是对 Iterables 的补充。它们使用相同的功能，您可以将它们链接到处理管道中。

不同之处在于序列延迟执行，每个项目在处理下一个项目之前通过完整的管道，而项目仅在需要时才处理。

例如，检查 this extremely good and plausible code:

import kotlin.system.measureTimeMillis

fun isMagicNumber(num: Double) = num == 10000.0

fun main(args: Array<String>) {
    val numberStrings = (1..25000).map(Int::toString)

    val itertime = measureTimeMillis {
        numberStrings
            .map(String::toInt).map { it * 2.0 }.first(::isMagicNumber)
    }
    println("Iterable version: $itertime ms")
    
    val seqtime = measureTimeMillis {
        numberStrings.asSequence()
            .map(String::toInt).map { it * 2.0 }.first(::isMagicNumber)
    }
    print("Sequence version: $seqtime ms")
}

从 25,000 个数字列表开始，作为字符串，管道是

映射到 Int
加倍（转换为 Double）
得到第一个满足条件的（等于10,000，在本例中）

Iterable 版本对整个列表执行每个步骤，然后再进行下一步：

List<String> -> List<Int> -> List<Double> -> find element

它每次都创建一个新列表（占用内存），它甚至不会开始检查元素，直到它制作了三个列表并且可以开始遍历最后一个 - 这是它最早可以做到的 return一个结果。

序列这样做：

String -> Int -> Double -> check

每一项。一旦命中符合检查条件的物品，就完成了。那一定要快得多吧！！！

Iterable version: 41 ms
Sequence version: 111 ms

啊！出色地。尽管如此，

事实证明序列有开销（这就是为什么一个真正基本的 for 循环会消除它们，如果你能写的话），而且计算机非常擅长迭代事物 - 有很多优化在引擎盖下，创建新数组并迭代它们可能比使用链表等更快。这就是为什么你真的需要分析你在做什么，如果你想要效率的话。

如果源列表（因此 Iterable 版本创建的所有附加列表）更大 10x，250,000 项？

Iterable version: 260 ms
Sequence version: 155 ms

哦，你好，现在我们到了某个地方。事实证明，所有开销在一段时间后开始堆积，能够提前退出变得很重要，并且序列开始变得更有效率。

这只是测量时间 - 您还需要查看内存使用情况。构建巨大的列表会很快占用大量内存，甚至变得无法运行（如果你正在做项目 Euler-levels 的“让这个工作 为 bajiliion kazillion 项目").序列及其 one-thing-at-a-time 方法可以使整个事情可行，并在宇宙热寂之前完成

序列也可以是无限的！哪些限制可以使用它们，或者某些操作的效率如何（last() 需要运行通过整个序列），但它也可以用于 fixed-size 集合获胜的情况没用。

所以，是的，使用正确的工具来完成工作，并确保如果效率很重要，那么您实际上使用的是能够提供最佳结果的版本。但有时可读性和可组合性更重要，能够将操作链接起来做一件事比平均和精益 for 循环

为什么标准迭代器比 Kotlin 中的序列快？

Why is a standard iterator faster than sequence in Kotlin?

optimization

sequence

kotlin

kotest