1

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

我写了两个函数：

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 秒。

为什么呢？我错过了关于序列的东西吗？或者也许我的代码以正确但非常不理想的方式实现其目的？

4

2 回答 2

6

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

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

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

是素数1：

isPrimeNumber1

是素数2：

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 循环，由于它们提供的抽象级别较低，因此往往具有较少的开销。

于 2020-10-18T13:41:09.230 回答
3

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

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

例如，检查这个非常好的和合理的代码：

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
  • 加倍（转换为 a Double）
  • 获取第一个满足条件的（在这种情况下等于 10,000）

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

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

它每次都会创建一个新列表（占用内存），它甚至不会开始检查元素，直到它创建了三个列表并且可以开始检查最后一个列表——这是它最早可以返回结果的时间。

序列这样做：

String -> Int -> Double -> check

对于每个项目。只要碰到符合检查条件的物品，就完成了。应该是更快了吧！！！

Iterable version: 41 ms
Sequence version: 111 ms

啊! 好。尽管如此，

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

如果源列表（以及因此Iterable版本创建的所有附加列表）大10 倍，250,000个项目怎么办？

Iterable version: 260 ms
Sequence version: 155 ms

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

这只是测量时间 - 您还需要查看内存使用情况。构建巨大的列表会很快使用大量内存，甚至变得无法运行（如果您正在执行 Project Euler 级别的“使这项工作适用于 bajiliion kazillion items ”）。序列及其一次一件事情的方法可以使整个事情在宇宙热寂之前保持可操作性和可完成性

序列也可以是无限的！哪些限制了您可以使用它们的位置，或者某些操作的效率（last()需要运行整个序列），但它也可以用于固定大小的集合不起作用的情况。

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

于 2020-10-18T17:55:06.203 回答