Java与Python特定的代码片段性能改进

Question

我有一个关于Java和Python中特定代码片段性能的问题.

算法:
我生成随机的N维点,然后对于彼此在一定距离阈值之下的所有点我做一些处理.处理本身并不重要,因为它不会影响总执行时间.在两种情况下生成点也需要几分之一秒,因此我只对进行比较的部分感兴趣.

执行时间:
对于3000点和2维的固定输入,Java在2到4秒内执行此操作,而Python需要15到200秒之间的任何时间.

我对Python的执行时间有点怀疑.这个Python代码中有什么我想念的吗？是否有任何算法改进建议(例如预分配/重用内存,降低Big-Oh复杂性的方法等)？

---

Java的

double random_points[][] = new double[number_of_points][dimensions];
for(i = 0; i < number_of_points; i++)
  for(d = 0; d < dimensions; d++)
    random_points[i][d] = Math.random();

double p1[], p2[];
for(i = 0; i < number_of_points; i++)
{
  p1 = random_points[i];
  for(j = i + 1; j < number_of_points; j++)
  {
    p2 = random_points[j];

    double sum_of_squares = 0;
    for(d = 0; d < DIM_; d++)
      sum_of_squares += (p2[d] - p1[d]) * (p2[d] - p1[d]);

    double distance = Math.sqrt(ss);
    if(distance > SOME_THRESHOLD) continue;

    //...else do something with p1 and p2

  }
}

Python 3.2

random_points = [[random.random() for _d in range(0,dimensions)] for _n in range(0,number_of_points)]

for i, p1 in enumerate(random_points):
  for j, p2 in enumerate(random_points[i+1:]):
    distance = math.sqrt(sum([(p1[d]-p2[d])**2 for d in range(0,dimensions)]))
    if distance > SOME_THRESHOLD: continue

    #...else do something with p1 and p2

Answer 1

你可能想考虑使用numpy.

我刚试过以下内容:

import numpy
from scipy.spatial.distance import pdist
D=2
N=3000
p=numpy.random.uniform(size=(N,D))
dist=pdist(p, 'euclidean')

最后一行计算距离矩阵(这相当于distance在代码中为每对点计算).在我的电脑上大约需要0.07秒.

该方法的主要缺点是它需要O(n^2)距离矩阵的存储器.如果这是一个问题,以下可能是一个更好的选择:

for i in xrange(1, N):
  v = p[:N-i] - p[i:]
  dist = numpy.sqrt(numpy.sum(numpy.square(v), axis=1))
  for j in numpy.nonzero(dist > 1.4)[0]:
    print j, i+j

对于N = 3000,我的计算机需要大约0.33秒.