[Python-de] Primzahlenberechnung, Effiziente Speicherung

Diez B. Roggisch deets at web.de
Mo Jan 26 12:35:15 UTC 2009


> zu speichern. Die Vorteile der Listen dynamischer Länge, die es in
> Python gibt liegen auf der Hand, jedoch sind sie in Ihrer Anwendung
> leider sehr langsam, da das Programm, wenn auf das n'te Element der
> Liste zugegriffen werden soll, zuerst alle Elemente von 0 bis n-1
> durchlaufen muss, um zum Element n zu gelangen. Bei einer Liste der
> Länge 10.000 bedeutet dies einen großen Zeitaufwand. Das Programm, das
> vorher 2-3 Sekunden benötigte brauch nun, in der mathematisch
> optimierten Form, fast 20 Sekunden. Gibt es eine Möglichkeit Listen in

<snip/>

Woher kommst du auf diese Idee? Python's listen sind mitnichten als verkettete 
Listen implemnetiert, sondern stattdessen als dynamisch wachsende Arrays mit 
O(1) fuer lesen und schreiben.

Wie anhaengen genau implementiert ist, kann ich nicht sagen - ich weiss, das 
irgendwo (koennen aber auch dicts sein) der speicherbedarf bis zu einer 
bestimmten Grenze verdoppelt wird, und danach nur noch proportional waechst. 
Aber das sollte alles fuer dein Problem ueberhaupt keine Rolle spielen - da 
geht dir eher die Lust & Zeit aus, als das die Performance der Listen 
degradiert.

Diez



Mehr Informationen über die Mailingliste python-de