In Python ist es schneller zu a) Erstellen Sie ein Set aus einer Liste von n Elementen b) Fügen Sie n Elemente in ein Set ein?
Ich habe diese Seite gefunden (http://wiki.python.org/moin/TimeComplexity), aber es gab nicht genug Informationen, um zu entscheiden, welches schneller war.
Es scheint, dass das Einfügen von Items einzeln im schlimmsten Fall O (n * n) Zeit (wenn es Dicts verwendet) und O (n * 1) im durchschnittlichen Fall dauert. Bietet das Initialisieren eines Sets mit einer Liste eine Leistungsverbesserung?
In O() complexity - es ist definitiv das gleiche, weil beide Ansätze genau das gleiche tun - fügen Sie n items in eine Menge ein.
Der Unterschied kommt von der Implementierung: Ein klarer Vorteil der Initialisierung von einem iterablen ist, dass Sie viele Funktionsaufrufe auf Python-Ebene speichern - die Initialisierung von einem iterierbaren erfolgt vollständig auf der C-Ebene (**).
Tatsächlich zeigen einige Tests auf einer Liste von 5.000.000 zufälligen ganzen Zahlen, dass das Hinzufügen von eins nach dem anderen langsamer ist:
%Vor% (**) Wenn Sie in den Code der Mengen ( Objects/setobject.c ) schauen, läuft die Artikeleinfügung schließlich auf einen Aufruf von set_add_key hinaus. Bei der Initialisierung von einem iterablen wird diese Funktion in einer engen C-Schleife aufgerufen:
Auf der anderen Seite ruft jeder Aufruf von set.add die Attributsuche auf, die in die C set_add -Funktion aufgelöst wird, die wiederum set_add_key aufruft. Da die Elementhinzufügung selbst relativ schnell ist (die Hashtabellenimplementierung von Python ist sehr effizient), werden diese zusätzlichen Aufrufe alle aufgebaut.
Tags und Links python set time-complexity