Schnellste Möglichkeit, String-Lookups durchzuführen?
Angenommen wir haben eine bestimmte Anzahl von möglichen Strings:
%Vor%und erhalten neue Zeichenfolgen, von denen bekannt ist, dass sie einer davon sind. Wir möchten jeder neuen Zeichenkette eine Ganzzahl zuweisen, zum Beispiel
%Vor%Was ist der schnellste Weg, dies in Python 3.6 zu tun? Ich habe es auf verschiedene Arten versucht und die Verwendung eines Wörterbuchs ist das bisher schnellste:
%Vor%Allerdings bin ich mehr oder weniger ein Python-Neuling und ich bin interessiert, ob es andere und schnellere Lösungen gibt. Hast du Vorschläge?
Mein vollständiger Testcode:
%Vor%1 Antwort
Die Wörterbuchsuche ist die schnellste Möglichkeit, diese Suche durchzuführen. Bei einer solchen Analyse würden Sie normalerweise die Zeitkomplexität jedes Prozesses vergleichen.
Für die Wörterbuchsuche ist die Zeitkomplexität "konstante Zeit" oder O (1). Während dies bedeuten kann, dass es im Allgemeinen ein ganzzahliger Wert von Schritten ist, den der Algorithmus annehmen kann, ist er in diesem Fall buchstäblich eins.
Die anderen Methoden erfordern eine Iteration (oder im Fall der if elses traversal - was im Wesentlichen ein ähnlicher Ansatz ist). Diese reichen von der Notwendigkeit, alle Werte O (n) zu betrachten, bis hin zu einigen Werten O (log n).
Da n die Größe des Untersuchungssatzes ist und die Menge größer wird, wird auch die Varianz in den Ergebnissen größer, wobei das Wörterbuch die anderen gezeigten Optionen durchweg übertrifft.
Es gibt keinen Weg, schneller zu sein als O (1). Der einzige Nachteil des Ansatzes, den Sie gezeigt haben, ist, dass es mehr Speicherplatz benötigt, wenn das Set wächst, dies wird als räumliche Komplexität des Algorithmus bezeichnet. In diesem Fall ist jedoch, da wir nur einen Wert pro Element in der Menge benötigen, die räumliche Komplexität O (n), was vernachlässigbar ist.
Im allgemeinen Sinne von Optimierungen ist es wichtig zu überlegen, wie viel Komplexität in einer aktuellen Lösung vorhanden ist und wie viel Sinn es macht, diese Komplexität zu verbessern. Wenn Verbesserungen vorgenommen werden sollen, sollten sie darauf abzielen, zu verschiedenen Leistungsstufen zu gelangen, zum Beispiel von O (n) nach O (log n) oder O (log n) nach O (1) zu kommen.
Bild mit freundlicher Genehmigung: Ссылка
Mikrooptimierungen sind in der Regel der Fall, wenn eine Optimierung von und zur selben Komplexitätsstufe durchgeführt wird, und diese sind oft an sich nicht konstruktiv.
Tags und Links python string optimization python-3.x