Pypy与Python中计数算法性能优化（Numpy与列表）

Question

我原本以为pypy会比python快很多，但结果显示pypy实际上比我预期的要慢。

我有两个问题：

为什么pypy在处理numpy时明显更慢？
有没有什么办法可以优化我的算法，让pypy（或python）运行得更快？

结果时间：

Python 2.7.5

点数：16,777,216 (8 ** 3 * 32 ** 3)
Xrange时间：1487.15毫秒
Xrange Numpy时间：2553.98毫秒
点生成时间：6162.23毫秒
Numpy生成时间：13894.73毫秒

Pypy 2.2.1

点数：16,777,216 (8 ** 3 * 32 ** 3)
Xrange时间：129.48毫秒
Xrange Numpy时间：4644.12毫秒
点生成时间：4643.82毫秒
Numpy生成时间：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__调用稍快（也就是说，dictionary[lookup]比dictionary.get(lookup)快）。

时间记录...

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是将数据转换为该类型（例如，tuple(data)、list(data)等）。

算法优化数据结构性能列表与字典读取速度内存使用效率 pypy性能 numpy效率体素引擎

Pypy与Python中计数算法性能优化（Numpy与列表）

1 个回答

撰写回答