Python - 辞書のリストを並べ替える

Question

私は検索アルゴリズムを試していますが、問題を解決するためにA *アルゴリズムを使用しようとしています。

私は、内部ノード構造を維持するために辞書のリストを使用しています。 各ノードは、特定の状態と関連コストによって特徴付けられます。 選択関数は、最もコストの低いノードを返さなければなりません。 これを行うには、毎回リストをフィルタリングしています。 問題が非常に小さい場合、これは非常に高速ですが、 ですが、リストが非常に大きい場合、この関数はアルゴリズムの合計時間の84％を使用します。

私の質問は、これを行うより効率的な方法があるかどうかです。

def select(self, frontier): 
    frontier.sort(key = lambda x: x['f_cost']) 
    #select the node with the lowest f_cost 
    return frontier.pop(0) 

Answer 1

ええ、最初から.popを入力しないでください。それは線形時間です。端から.popは一定であり、これだけの操作を行います。

def select(self, frontier): 
    frontier.sort(key = lambda x: x['f_cost'], reverse=True) 
    #select the node with the lowest f_cost 
    return frontier.pop() 

あなたはソート順序を維持しようとしている場合、代替データ構造を検討する必要があります。あなたは標準ライブラリの一部であるheapqを見ることができますが、それはかなり素朴です。また、sortedcontainersライブラリは、おそらくと非常によく似ています。です。

Answer 2

ラムダ関数ではなくキーとしてattrgetterまたはitemgetterのような関数を使うべきです。

ドキュメント：詳細については https://docs.python.org/3/howto/sorting.html

は、この答えを見ています。 operator.itemgetter or lambda