Wo finde ich die zeitliche und räumliche Komplexität der in Python integrierten Sequenztypen?

Question

Ich konnte keine Quelle für diese Informationen finden, es sei denn, ich habe selbst den Python-Quellcode durchgesehen, um festzustellen, wie die Objekte funktionieren.Weiß jemand, wo ich das online finden könnte?

Answer 1

Besuche die Zeitkomplexität Seite im py dot org Wiki.Es deckt set/dicts/lists/usw. ab, zumindest was die zeitliche Komplexität betrifft.

Answer 2

Raymond D.Hettinger tut es ein ausgezeichneter Vortrag (Folien) über Pythons integrierte Sammlungen mit dem Namen „Core Python Containers – Under the Hood“.Die Version, die ich gesehen habe, konzentrierte sich hauptsächlich auf set Und dict, Aber list war auch abgedeckt.

Es gibt auch einige Fotos der dazugehörigen Folien von EuroPython in ein Blog.

Hier ist eine Zusammenfassung meiner Notizen zu list:

• Speichert Elemente als Array von Zeigern.Der Index kostet O(1) Zeit.Kosten anhängen, amortisiert O(1) Zeit.Das Einfügen kostet O(n) Zeit.
• Versucht zu vermeiden memcpy beim Wachstum durch Überzuteilung.Viele kleine Listen verschwenden viel Platz, aber große Listen verschwenden nie mehr als etwa 12,5 % durch Überbelegung.
• Einige Vorgänge sind vorab dimensioniert.Angeführte Beispiele waren range(n), map(), list(), [None] * n, und schneiden.
• Beim Verkleinern ist das Array reallocWird nur dann verwendet, wenn 50 % des Speicherplatzes verschwendet werden. pop ist günstig.

Answer 3

Wenn Sie fragen, was ich zu fragen denke, können Sie sie finden Hier...Seite 476 und weiter.

Es handelt von Optimierungstechniken für Python.Es handelt sich hauptsächlich um eine Big-O-Notation der Zeiteffizienz, nicht um viel Speicher.