Das deutsche Python-Forum

veers hat geschrieben:

Hobbes Hobson hat geschrieben:Wie wäre es mit dem Sieb des Eratosthenes?

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Hast du meinen Code gelesen?

Da war der die Hand mal wieder schneller als der Kopf mit seinen Erinnerungen.

Sorry.

@Nikolas: Listen sind als dynamische Arrays implementiert und Dictionaries als Hash-Tabellen. Benötigt also beides beim Zugriff auf Elemente O(1) Zeit.

Wie sieht denn die Speicherverwaltung für ein dynamisches Array mit Aktionen in konstanter Zeit aus? Wenn ich zusätzliche Objekte hinzufüge, muss doch entweder das komplette Array umkopiert werden, oder an einer zweiten Stelle zusätzlicher Platz bezogen werden.
Warum kann dann ein Array aber unterschiedliche Objekttypen aufnehmen? Besteht das Array dann aus einer Liste von Speicheradressen (array of Pointer), oder wie muss ich mir das vorstellen?

Ganz grob ist es ein Array mit einer Grösse und einem "Füllstand". Immer wenn der Platz beim Anhängen nicht mehr ausreicht, wird ein neues grösseres Array angefordert und das alte dorthin kopiert. Die Grösse des neuen Arrays richtet sich nach dem alten, je grösser das ist, um so mehr wird im neuen "überbelegt". So läuft die `append()`-Operation, wenn man sie unendlich oft durchführen würde in amortisiert O(1) Zeit pro Anfügen.

Und ja, Arrays enthalten Referenzen auf Objekte.