Scala List sort vs Python list sort执行时间比较

Scala List sort vs Python list sort执行时间比较。
我现在正在学习Scala。我对Scala的列表排序和Python的列表排序比较感兴趣。令我惊讶的是，在Python中对1_000_000整数列表进行排序的速度比在Scala中快5倍。据我所知，Scala比Python更快。谁能解释一下为什么Python比Scala有这么大的优势？
Scala代码：

import scala.util.Random

@main
def Main(args: String*): Unit =
  def cmillis = System.currentTimeMillis()
  val n = 1_000_000

  val xs = List.fill(n)(Random.nextInt(n))

  var currentMillis = cmillis
  xs.sorted
  println("Sorted in " + (cmillis - currentMillis) + "ms")

Python代码：

from time import time
from random import randint

n = 1_000_000

xs = [randint(0, n) for _ in range(n)]

start = time()
sorted(xs)
print(f"Sorted in {(time() - start)* 1000} ms")

Python是世界上最快的语言，如果你调用C代码。;-）
撇开玩笑不谈，这里的差异可以通过在Scala中使用List来解释，这是一个单链表。虽然它是一个非常简单的数据结构，但它的局部性很差（列表的节点可以在堆上的任何地方，导致频繁的缓存未命中），更重要的是，它的结构使得需要索引（包括排序）的操作非常低效。
您可以在Scala标准库here中看到数据结构的比较。
为了进行公平的比较，您应该选择具有类似后台结构的数据结构，并使用同样具有可比性的排序方法。如果Python列表是由可变数组支持的，那么与不可变链表进行比较总是可变数组获胜。如果是这样的话，你可以在Scala中使用ArraySeq，而不是sorted（创建一个新结构），你可以使用sortInPlace。
关于你的基准测试还有几点注意事项：

不应该使用System.currentTimeMillis()，因为它不能保证是单调的，对于基准测试，System.nanoTime()确保您正在测量经过的时间
您应该多次运行一个基准测试，以确保获得一些统计相关的结果。在JVM上，您可以使用JMH来执行微基准测试，这些微基准测试会考虑到这一点，并且还允许您进行一些运行来“预热”JVM（这可以动态地将字节码中的热点编译为本机代码，以加快执行速度）。我不确定Python生态系统中是否有类似的工具，但我确信有一个。

请注意，根据sorted在Python中的具体实现，您可能仍然会看到它优于Scala（回到我最初的笑话，如果它调用C代码，很难击败它）。我通常认为Scala在执行时间方面比Python代码更有优势，但这当然取决于您正在测试的内容。

编辑1

一位评论者正确地指出，如果Seq s上的排序确实是使用索引的天真方法完成的，那么5x因子似乎 * 太快了 *。我看了一下代码，Seq s（包括List s）似乎是通过将自己复制到Array中并对其（代码）进行排序来执行排序的，这可以解释为什么这很慢，但没有通过索引和交换对不可变链表进行简单排序那么慢。

编辑2

纯粹出于好奇，我尝试在本地运行这个简单的基准测试。你的Scala代码在我的笔记本电脑上运行了大约650 ms，而Python代码花了大约250 ms。只需将List更改为ArraySeq，将sorted更改为sortInPlace，Scala版本就可以在大约200 ms内运行。虽然这在统计上并不相关，但这表明这些变化似乎产生了预期的影响。您可能希望使用更科学的方法执行进一步的基准测试，以获得更好的结果。

Scala List sort vs Python list sort执行时间比较

1条答案

编辑1

编辑2

相关问题

热门标签

最新问答