本当に大きな迷路をpythonで解きたいです。プライオリティ キューとして A* アルゴリズムとバイナリ ヒープを使用しています...しかし、遅すぎます...ヒープを固定サイズに事前に割り当てた場合、高速に実行されますか。たとえば、迷路内のすべての場所をカウントし、この長さのリストをヒープとして使用します。 ?
ありがとうございました!
本当に大きな迷路をpythonで解きたいです。プライオリティ キューとして A* アルゴリズムとバイナリ ヒープを使用しています...しかし、遅すぎます...ヒープを固定サイズに事前に割り当てた場合、高速に実行されますか。たとえば、迷路内のすべての場所をカウントし、この長さのリストをヒープとして使用します。 ?
ありがとうございました!
リストを作成する時間を比較することで、リストを割り当てるコストを見積もることができます。
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ミリ秒長くかかることを示しています。