java - 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)

Java:

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)

在我的电脑上需要 14 秒。 但很明显，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 版本只需 0.6 秒。