Ich habe den folgenden Code in Python:
%Vor% Dieser Code ist furchtbar ineffizient, insbesondere da ich erwarte, dass points wächst, um ein paar Millionen Elemente zu enthalten.
Wenn der Punkt nicht in der Liste ist, durchlaufe ich die Liste dreimal:
Wenn in der Liste ist, durchlaufe ich es zweimal: 1. Suche danach und entscheide, dass es da ist 2. Geh fast bis zum Ende der Liste, bis ich den Index finde
Gibt es dafür einen effizienteren Weg? Zum Beispiel weiß ich das:
Wenn ich also die Linie haben könnte:
%Vor%Suche die Liste vom Ende bis zum Anfang, es würde die Leistung verbessern, wenn der Punkt bereits in der Liste ist.
Allerdings möchte ich nicht tun:
%Vor% weil ich mir vorstelle, dass reversed(points) selbst sehr teuer ist.
Ich möchte auch keine neuen Punkte am Anfang der Liste hinzufügen (vorausgesetzt, ich wusste, wie man das in Python macht), weil das die Indizes verändern würde, die für den Algorithmus konstant bleiben müssen.
Die einzige Verbesserung, die ich mir vorstellen kann, ist die Implementierung der Funktion mit nur einem Durchlauf, wenn möglich vom Ende bis zum Anfang. Die untere Zeile ist:
Bearbeiten: Ich habe Vorschläge für die Implementierung mit nur einem Durchlauf erhalten. Gibt es eine Möglichkeit, dass index() vom Ende zum Anfang geht?
Bearbeiten: Die Leute haben gefragt, warum der Index kritisch ist. Ich versuche, eine 3D-Oberfläche mit dem OFF-Dateiformat zu beschreiben. Dieses Format beschreibt eine Oberfläche mit ihren Eckpunkten und Flächen. Zuerst werden die Vertices aufgelistet, und die Faces werden anhand einer Liste von Indizes von Vertices beschrieben. Deshalb, sobald ich einen Wirbel zur Liste hinzufüge, darf sich sein Index nicht ändern.
Bearbeiten: Es gibt einige Vorschläge (z. B. igor ), um ein Diktat zu verwenden. Dies ist eine gute Lösung zum Scannen der Liste. Wenn ich fertig bin, muss ich die Liste in der gleichen Reihenfolge ausdrucken, in der sie erstellt wurde. Wenn ich ein Diktat verwende, muss ich die Schlüssel nach Wert sortiert ausdrucken. Gibt es einen guten Weg, das zu tun?
Bearbeiten: Ich habe www.brool.com implementiert a href="https://stackoverflow.com/questions/1319254/what-is-the-most-efficient-way-to-add-an-ement-to-a-list-only-if-ist-there- Ihr / 1321039 # 1321039 "> Vorschlag . Dies war die einfachste und schnellste. Es ist im Wesentlichen ein geordneter Dict, aber ohne den Overhead. Die Leistung ist großartig!
Sie möchten festlegen :
%Vor%Ein Satz enthält nur eine Instanz eines von Ihnen hinzugefügten Elements und ist wesentlich effizienter als eine manuelle Iteration einer Liste.
Diese Wikibooks-Seite sieht wie eine gute Grundierung aus, wenn Sie zuvor keine Sets in Python verwendet haben.
Dies wird höchstens einmal durchlaufen:
%Vor% Sie können diese Version auch ausprobieren, die berücksichtigt, dass Übereinstimmungen wahrscheinlich am Ende der Liste liegen. Beachten Sie, dass reversed() selbst bei sehr großen Listen fast keine Kosten verursacht - es erstellt keine Kopie und durchläuft die Liste nicht mehr als einmal.
Sie können auch eine parallele dict oder set von Punkten in Betracht ziehen, um nach einer Mitgliedschaft zu suchen, da beide Typen Mitgliedschafts-Tests in O (1) durchführen können. Es würde natürlich eine erhebliche Speicherkosten geben.
Wenn die Punkte irgendwie geordnet würden, hätten Sie natürlich viele andere Möglichkeiten, diesen Code zu beschleunigen, vor allem mit einer binären Suche nach Mitgliedschaftstests.
Wie bereits erwähnt, sollten Sie set oder dict verwenden. Sie erklären nicht, warum Sie die Indizes benötigen. Wenn sie nur benötigt werden, um den Punkten eindeutige IDs zuzuweisen (und ich kann nicht leicht einen anderen Grund finden, sie zu verwenden), dann wird dict in der Tat viel besser funktionieren, z. B.
%Vor%Tags und Links python optimization list