Pypy与Python的计数算法性能优化(Numpy vs List)

Question

我的期望是pypy可能比python快一个数量级,但结果表明pypy实际上比预期慢.

我有两个问题:

1. numpy为什么pypy明显变慢？
2. 有什么我可以做的来优化我的算法以使pypy(或python)更快？

结果时间:

Python 2.7.5

• #points:16,777,216(8**3*32**3)
• Xrange时间:1487.15毫秒
• Xrange Numpy时间:2553.98毫秒
• 点发生时间:6162.23毫秒
• Numpy Gen时间:13894.73毫秒

Pypy 2.2.1

• #points:16,777,216(8**3*32**3)
• Xrange时间:129.48毫秒
• Xrange Numpy时间:4644.12毫秒
• Point Gen Time:4643.82 ms
• Numpy Gen时间:44168.98毫秒

算法:

我正在使用一个简单的算法生成一个空间点列表,我正在尝试优化算法.

def generate(size=32, point=(0, 0, 0), width=32):
    """
    generate points in space around a center point with a specific width and
      number of divisions (size)
    """
    X, Y, Z = point
    half = width * 0.5
    delta = width
    scale = width / size
    offset = scale * 0.5
    X = X + offset - half
    Y = Y + offset - half
    Z = Z + offset - half
    for x in xrange(size):
        x = (x * scale) + X
        for y in xrange(size):
            y = (y * scale) + Y
            for z in xrange(size):
                z = (z * scale) + Z
                yield (x, y, z)

在优化方面,我开始考虑使用pypy而不是python.在比较两者时,我想出了几个不同的场景:

• 使用xrange计数

  rsize = 8    # size of region
  csize = 32   # size of chunk
  number_of_points = rsize ** 3 * csize ** 3
  [x for x in xrange(number_of_points)]
  

• 使用xrange与numpy计数

  rsize = 8    # size of region
  csize = 32   # size of chunk
  number_of_points = rsize ** 3 * csize ** 3
  np.array([x for x in xrange(number_of_points)])
  

• 运行上面的算法

  rsize = 8    # size of region
  csize = 32   # size of chunk
  [p
   for rp in generate(size=rsize, width=rsize*csize)
   for p in generate(size=csize, width=csize, point=rp)]
  

• 用numpy运行上面的算法

  rsize = 8    # size of region
  csize = 32   # size of chunk
  np.array([p
   for rp in generate(size=rsize, width=rsize*csize)
   for p in generate(size=csize, width=csize, point=rp)])
  

背景:

我正在尝试创建一个体素引擎,我想优化我的算法,将生成时间降低到可管理的水平.虽然我显然不会接近Java/C++,但我想尽可能地推送python(或pypy).

我注意到列表查找比一些早期时间的字典要快得多.并且列表也比元组(意外)更快,尽管元组生成更快.Numpy的读取时间比非numpy更快.但是,numpy创建时间可能会慢几个数量级.

因此,如果阅读是最重要的,那么使用numpy有明显的优势.但是,如果阅读和创作同等重要,那么直接列表可能是最好的.也就是说,我没有一种干净的方式来查看内存使用情况,但我怀疑列表的内存效率远低于元组或numpy.此外,虽然这是一个很小的差异,但我发现字典上的.get比使用__ getitem __调用(即字典[lookup]与dicitonary.get(查找))稍快一些

时间......

Python 2.7.5

读

 - Option 1: tuple access... 2045.51 ms
 - Option 2: tuple access (again)... 2081.97 ms    # sampling effect of cache
 - Option 3: list access... 2072.09 ms
 - Option 4: dict access... 3436.53 ms
 - Option 5: iterable creation... N/A
 - Option 6: numpy array... 1752.44 ms

创建

 - Option 1: tuple creation... 690.36 ms
 - Option 2: tuple creation (again)... 716.49 ms    # sampling effect of cache
 - Option 3: list creation... 684.28 ms
 - Option 4: dict creation... 1498.94 ms
 - Option 5: iterable creation...  0.01 ms
 - Option 6: numpy creation... 3514.25 ms

Pypy 2.2.1

读

 - Option 1: tuple access... 243.34 ms
 - Option 2: tuple access (again)... 246.51 ms    # sampling effect of cache
 - Option 3: list access... 139.65 ms
 - Option 4: dict access... 454.65 ms
 - Option 5: iterable creation... N/A
 - Option 6: numpy array... 21.60 ms

创建

 - Option 1: tuple creation... 1016.27 ms
 - Option 2: tuple creation (again)... 1063.50 ms    # sampling effect of cache
 - Option 3: list creation... 365.98 ms
 - Option 4: dict creation... 2258.44 ms
 - Option 5: iterable creation...  0.00 ms
 - Option 6: numpy creation... 12514.20 ms

在所有示例中,为随机数据生成随机查找.

dsize = 10 ** 7   # or 10 million data points
data = [(i, random.random()*dsize)
         for i in range(dsize)]
lookup = tuple(int(random.random()*dsize) for i in range(dsize))

循环非常简单:

for x in lookup:
    data_of_specific_type[x]

和data_of_specific_type是转换数据的成型(例如元组(数据),列表(数据)等等)

Answer 1

问题的一部分是：

np.array([p
    for rp in generate(size=rsize, width=rsize*csize)
    for p in generate(size=csize, width=csize, point=rp)])

完成创建list 并将其转换为np.array.

更快的方法是：

arr = np.empty(size)
i = 0
for rp in generate(size=rsize, width=rsize*csize):
    for p in generate(size=csize, width=csize, point=rp):
        arr[i] = p
        i += 1