python - 如果预先分配到固定长度，二进制堆会运行得更快吗？

Question

我想用python解决一个非常大的迷宫。我使用 A* 算法和二进制堆作为优先级队列...但是它太慢了...如果我将堆预分配为固定大小，例如计算迷宫中的所有位置并将此长度的列表用作堆，它会运行得更快吗?

谢谢！

Answer 1

我们可以通过比较构建列表的时间来估算分配列表的成本：

from timeit import Timer

>>> Timer('a = [0]*1000000').timeit(100)
0.587
>>> Timer('for i in xrange(1000000): a[i] = i', 'a = [0] * 1000000').timeit(100)
4.464
>>> Timer('for i in xrange(1000000): a.append(i)', 'a = []').timeit(100)
12.360

这表明构建一个百万项目列表比预先分配它需要大约 75 毫秒。