快速排序。为什么 Python 和 Javascript 中的类似实现有如此显着的不同？

Question

在 javascript 中使用 10 000 000 个随机元素实施快速排序后：

function swap(arr, i1, i2) {
    const temp = arr[i1];
    arr[i1] = arr[i2]
    arr[i2] = temp;
}

function pivot(arr, l, r) {
    let pvt = arr[r];
    let i = l - 1;
    
    for (let j = l; j <= r - 1; j++) {
        if (arr[j] < pvt) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i+1, r);
    return i+1;
}

function quick_sort(arr, l, r) {
    if (l < r) {
        let pvt = pivot(arr, l, r);
        quick_sort(arr, l, pvt - 1);
        quick_sort(arr, pvt + 1, r);
    }
    
}
let arr = Array.from(Array(10000000)).map((_) => Math.random());
console.time("quick_sort");
quick_sort(arr, 0, arr.length - 1);
console.timeEnd("quick_sort");

排序一个数组需要≈1.5s

当我在 python:

中测试同一个

import time
import random
from numpy import random

def quicksort(arr):
    qs(arr, 0, len(arr) - 1)

def qs(arr, l, r):
    if l >= r:
        return
    p = partition(arr, l, r)

    qs(arr, l, p - 1)
    qs(arr, p + 1, r)

def partition(arr, l, r):
    pivot = arr[r]
    i = l - 1
    for j in range(l, r):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1

array = random.rand(10000000)
start = time.time()
quicksort(array)

print("Seconds: ", time.time() - start)

如果使用random.rand(10000000)
，对数组进行排序需要≈131s ≈ 60s，如果使用 array = [random.random() for _ in range(10000000)] 代替

这种差异从何而来？

Answer 1

这取决于您使用的 python 解释器。

我假设您使用的是 cpython 3，我相信它没有 JIT。您拥有解释型语言的所有开销，并且没有加快速度的技巧。

大多数现代 JS 引擎都有 JIT，因此热代码路径得到了优化。

有点相关，numpy 更快，因为 internal code is either C or Fortran，它通过绑定调用。

software engineering stackexchange 上有一篇更长的 post，它更多地探讨了为什么原生 python 不如 JS 快。

快速排序。为什么 Python 和 Javascript 中的类似实现有如此显着的不同？

Quick Sort. Why does the similar implementation in Python and Javascript differs so sagnificantly?

javascript

python

sorting

quicksort