Sagen wir, ich habe ein Diagramm und möchte sehen, ob b in N[a]
. Welche ist die schnellere Umsetzung und warum?
a, b = range(2)
N = [set([b]), set([a,b])]
ODER
N= [[b],[a,b]]
Dies ist natürlich stark vereinfacht, aber stellen Sie sich vor, dass der graph wird dichter.
Mitgliedschaft Tests in einem set ist deutlich schneller, besonders für große Mengen. Das ist, weil das set verwendet eine hash-Funktion für die Zuordnung zu einem Eimer. Da Python-Implementierungen automatisch die Größe, die hash-Tabelle, die Geschwindigkeit kann konstant sein (
O(1)
) unabhängig von der Größe des Satzes (vorausgesetzt, die hash-Funktion ist ausreichend gut).Im Gegensatz, zu bewerten, ob ein Objekt ein Element einer Liste, Python vergleichen, jedes einzelne Mitglied für die Gleichstellung, d.h. der test ist
O(n)
.b in N[a]
) von der Liste der Container, dieN
, also Nein, es ist nicht O(n) so oder so.O(1)
(+Noten), ist eine bessere Beschreibung alsO(log n)
(-Noten).O(1)
ist die richtige Beschreibung hier. Behoben.Es hängt alles davon ab, was Sie versuchen zu erreichen. Mit Ihrem Beispiel wörtlich, dass es schneller zu Listen verwenden, als Sie nicht haben zu gehen durch den overhead für das erzeugen der Sätze:
Produziert:
Jedoch aus Gründen, die hier bereits erwähnt, profitieren Sie von der Verwendung von sets, wenn Sie Suche großen Mengen. Es ist unmöglich zu sagen, durch euer Beispiel, wo das Wendepunkt für Sie ist und ob oder nicht Sie werden sehen, der nutzen.
Ich schlage vor, Sie testen es beide Wege, und gehen mit dem, was ist schneller für Ihren spezifischen Anwendungsfall.
Eingestellt ( ich meine, ein hash-basierter set wie HashSet) ist viel schneller als Liste zum nachschlagen für einen Wert. Liste hat zu gehen nacheinander, um herauszufinden, ob der Wert vorhanden ist. HashSet können direkt und suchen Sie den Eimer und nachschlagen für einen Wert, der fast in konstanter Zeit.