Python - Eine Liste von Wörterbüchern sortieren

Question

Ich experimentiere mit einem Suchalgorithmus, und ich versuche, einen A * -Algorithmus zu verwenden, um das Problem zu lösen.

Ich verwende eine Liste von Wörterbüchern, um die interne Knotenstruktur zu erhalten. Jeder Knoten ist durch einen bestimmten Zustand und die damit verbundenen Kosten gekennzeichnet. Die Auswahlfunktion sollte den Knoten mit den niedrigsten Kosten zurückgeben. Um dies zu tun, filtere ich die Liste jedes Mal. Ich fand das ist sehr schnell, wenn das Problem sehr klein ist, aber in dem Fall, dass die Liste sehr groß ist, verwendet diese Funktion 84% der Gesamtzeit des Algorithmus.

Meine Frage ist, ob es eine effizientere Möglichkeit gibt, dies zu tun.

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

Ja, nicht .pop von Anfang an! Das ist lineare Zeit. .pop vom Ende konstant ist, so einfach tun:

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() 

Vielleicht möchten Sie alternative Datenstrukturen berücksichtigen, wenn Sie eine sortierte Folge zu halten versuchen. Sie können heapq betrachten, die Teil der Standard-Bibliothek ist, obwohl es ziemlich nackt ist. Sie könnten auch die sortedcontainers-Bibliothek betrachten, die offensichtlich ist sehr performant.

Answer 2

Sie sollten Funktionen wie attrgetter oder itemgetter für Ihren Schlüssel anstelle der Lambda-Funktion verwenden, da dies als schneller gilt.

Docs: https://docs.python.org/3/howto/sorting.html

Einzelheiten haben einen Blick auf diese Antwort. operator.itemgetter or lambda