javascript - Python 与 Javascript 执行时间

Question

我尝试使用 Javascript(Node.js) 和 Python 以及强力算法来求解最大子数组。这是我的代码:

使用 python :

from datetime import datetime
from random import randint

arr = [randint(-1000,1000) for i in range(1000)]

def bruteForce(a):
  l = len(a)
  max = 0
  for i in range(l):
    sum = 0
    for j in range(i, l):
      sum += a[j]
      if(sum > max):
        max = sum
  return max

start = datetime.now()
bruteForce(arr)
end = datetime.now()

print(format(end-start))

和 Javascript:

function randInt(start, end) {
    return Math.floor(Math.random() * (end - start + 1))
}

var arr = Array(1000).fill(randInt(-1000, 1000))

function bruteForce(arr) {
    var max = 0
    for (let i = 0; i < arr.length; i++) {
        var sum = 0
        for (let j = i; j < arr.length; j++) {
            sum += arr[j]
            max = Math.max(max, sum)
        }
    }
    return max
}

var start = performance.now()
bruteForce(arr)
var end = performance.now()
console.log(end - start)

Javascript 得到了大约 0.187 秒的结果，而 python 得到了 4.75 秒——慢了大约 25 倍。是我的代码没有优化，还是 python 真的比 javascript 慢？

Answer 1

Python 本身并不比 Javascript 慢，这取决于实现。这里比较节点和 PyPy 的结果也使用 JIT :

> /pypy39/python brute.py
109.8594 ms N= 10000 result= 73682
> node brute.js
167.4442000091076 ms N= 10000 result= 67495

所以我们甚至可以说“python 有点快”......如果我们使用 Cython ，通过一些类型提示，它会再次快得多——实际的全 C 速度:

> cythonize -a -i brutec.pyx
> python -c "import brutec"
69.28919999999998 ms N= 10000 result= 52040

---

为了使比较合理，我修复了您脚本中的一些问题:

• 修复:js 脚本用来自单个随机数的所有相同值填充数组
• 在 Python 中执行相同的基本类型的循环——而不是使用范围迭代器(否则它会慢一点)
• 使用相同的时间格式并将数组长度增加到 10000 - 否则时间对于分辨率和线程切换抖动而言太小

Python代码:

from time import perf_counter as clock
from random import randint

N = 10000
arr = [randint(-1000,1000) for i in range(N)]

def bruteForce(a):
  l = len(a)
  max = 0
  i = 0
  while i < l:
    sum = 0
    j = i
    while j < l:
      sum += a[j]
      if sum > max:
        max = sum
      j += 1
    i += 1
  return max

start = clock()
r = bruteForce(arr)
end = clock()
print((end - start) * 1000, 'ms', 'N=', N, 'result=', r)
##print(arr[:10])

JS代码:

var start = -1000, end = 1000, N=10000
var arr = Array.from({length: N}, 
    () => Math.floor(Math.random() * (end - start + 1) + start))

function bruteForce(arr) {
    var max = 0
    for (let i = 0; i < arr.length; i++) {
        var sum = 0
        for (let j = i; j < arr.length; j++) {
            sum += arr[j];
            max = Math.max(max, sum)
            //~ if (sum > max) max = sum;
        }
    }
    return max
}

var start = performance.now()
r = bruteForce(arr)
var end = performance.now()
console.log(end - start, 'ms', 'N=', N, 'result=', r)
//~ console.log(arr.slice(0, 10))

Cython(或 Python)的代码，增加了一些类型提示:

import cython
from time import perf_counter as clock
from random import randint

N = 10000
arr = [randint(-1000,1000) for i in range(N)]

def bruteForce(arr):
  l: cython.int = len(arr)
  assert l <= 10000
  a: cython.int[10000] = arr  # copies mem from Python array
  max: cython.int = 0
  i: cython.int = 0
  while i < l:
    sum: cython.int = 0
    j: cython.int = i
    while j < l:
      sum += a[j]
      if sum > max:
        max = sum
      j += 1
    i += 1
  return max

start = clock()
r = bruteForce(arr)
end = clock()
print((end - start) * 1000, 'ms', 'N=', N, 'result=', r)
##print(arr[:10])

---

(在慢速笔记本上完成)