Python-Mengen und -Dictionaries können quadratische Laufzeit haben
Python sets and dictionaries can have quadratic-time performance
Daniel Lemire zeigt, dass die verbreitete Annahme, dict und set in Python seien O(1), nicht der Realität entspricht. Mit geschickt gewählten Schlüsseln explodiert die Laufzeit: Bei 16.000 Elementen dauert das Erzeugen einer Menge über eine Sekunde – viermal so lang wie bei der Hälfte. Auch bei reinen Lookups wächst die Zeit pro Zugriff von 22 ns auf 202 ns, wenn die Map eine Million Einträge umfasst. Der Grund: Speicherhierarchie und Cache-Misses, nicht der Algorithmus. Die fastconstmap-Bibliothek bleibt dank kompakter Speicherung deutlich schneller.
Die Zeit vervierfacht sich ungefähr, jedes Mal wenn sich n verdoppelt. Das ist quadratische Zeit, nicht lineare Zeit.