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

これは、100万アイテムのリストを作成するには、事前に割り当てるよりも約75ミリ秒長くかかることを示しています。