Das deutsche Python-Forum

Wie wäre es mit dem Sieb des Eratosthenes?

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

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?

@Hobbes:
Du hast den Thread nicht gelesen, oder?

@Veers:
> sieve = [True]*limit
Das ist doch eine verkette Liste, oder? (wahrscheinlich doppelt, damit man sie schnell umdrehen kann).
Wenn man das noch in eine Array (wie in Pascal, C++, Java) umwandelt, dürfte das nochmal ein bischen schneller werden.

> Ich frage mich jedoch ernsthaft weshalb man für derart Performance kritische Programme Python verwenden sollte
Ist doch mal ganz interessant. Einen wirklichen Nutzen hat das Programm sowieso nicht, daher steht der Lerneffekt im Vordergrund.

Nikolas hat geschrieben: @Veers:
> sieve = [True]*limit
Das ist doch eine verkette Liste, oder? (wahrscheinlich doppelt, damit man sie schnell umdrehen kann).
Wenn man das noch in eine Array (wie in Pascal, C++, Java) umwandelt, dürfte das nochmal ein bischen schneller werden.

Dachte ich auch. Ist aber ähnlich wie ein C++ Vektor.

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

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.