Java和Python实现的速度

Question

因此，我已经在python和java中解决了一个问题。问题是，对于一个包含8000*8000元素的乘法表，可以找到所有唯一的数字：

Python：

table = 8000
unique_prods = []
start = 1

for i in range(table*table + 1):
    unique_prods.append(0)

for x in range(1, table + 1):
    for y in range(start, table + 1):
        # print '{:4}'.format(x * y),
        if not unique_prods[x * y] == x * y:
            unique_prods[x * y] = x * y
    start += 1
    # print

# print unique_prods
print len(unique_prods)

爪哇：

public class Test {
    public static void main(String[] args) {
        int table = 8000;
        int [] myArray = new int[table*table + 1];
        int count = 1;

        for (int i = 0; i < table*table + 1; i++) {
            myArray[i] = 0;
        }

        for (int x = 1; x < table + 1; x++) {
            for (int y = count; y < table + 1; y++) {
                if (! (myArray[x * y] == x * y)) {
                    myArray[x * y] = x * y;
                }
            }
            count += 1;
//            System.out.println(count);
        }

        count = 0;
        for (int i = 0; i < table*table + 1; i++) {
            if(myArray[i] != 0) {
                count += 1;
            }
        }

        System.out.println(count);
    }
}

我感到惊讶的是，Java实现花了一秒钟时间，Python版本花了一分钟时间。有没有一种方法可以提高python的性能，使其更接近Java实现的速度？

Answer 1

Python代码不是最优的，您不会像在Java中那样以同样的方式解决这个问题：

table = 8000
unique_prods = set()

for x in range(1, table + 1):
    for y in range(x, table + 1):
        unique_prods.add(x * y)
print len(unique_prods)

在我的电脑上使用14s。但是很明显，python只需要更长的时间来解决数学问题，因为Python没有集成的JIT。对于计算，有一个名为numpy的包，它极大地加快了事情的速度：

import numpy
x = numpy.arange(1,8001)
unique_prods = numpy.zeros(8000*8000+1,dtype='b')
for k in x:
    unique_prods[k*x[k-1:]]=1
print unique_prods.sum()

你的成绩是0.8分。与C版本相反，C版本只需要0.6s。

Answer 2

Python可能要慢一些，但请考虑以下两个片段，它们都是pythonic的：

import time 
starttime = time.time()
table = 8000
unique_prods = [0] * (table*table + 1)
for x in range(1, table+1):
    for y in range(1, table+1):
        unique_prods[x*y] = 1

elapsed = time.time() - starttime
print((elapsed, sum(unique_prods)))

最简单，但不一定是最快的：

starttime = time.time()
table = 8000
unique = set(x*y for x in range(1, table+1) for y in range(1,table+1))
elapsed = time.time() - starttime
print((elapsed, len(unique)))

Python的设计并不是最快的。python的优点是您可以编写

unique = set(x*y for x in range(1, table+1) for y in range(1,table+1))
print(len(unique))

从根本上说，这是一条解决基本数学问题的单线线，即定义一个集合并打印它的基数。

Answer 3

问题似乎在于如何在python中创建数组。

请考虑以下几点：

array = []

for i in range(8000*8000 + 1):
  array.append(0)

这需要很长时间才能运行(对我来说是14次)，因为我们首先创建一个空数组，然后对其进行总计64000001次的调整。与其这样做，不如创建一个大小正确的数组，以便只需要一个内存分配：

array = [0] * (8000*8000 + 1) // Creates an array filled with zeros of size (8000*8000 + 1)

这段代码几乎立刻就为我运行了。