Betrifft: Virtueller Speicher Überlauf
Aus dem Python Cookbook ASPN entnahm ich den Algorithmus 410662 zur Primzahlbestimmung.
Ich wollte (fast aus Langeweile) die Zeitersparnis gegenüber dem üblichen Verfahren feststellen.
Dabei blieb das Programm bei sehr großen Zahlen 'hängen'. Mehr durch Zufall entdeckte ich einen Fehler-Hinweis: Mangel an virtuellem Speicher.
Ursache ist der immense Speicherbedarf in der Routine primes (Algorithmus 366178) im Statement "s=range(3,n+1,2)"
Damit entpuppte sich Algorithmus 410662 als Flop.
Meine Frage ist, sollte der Python-Interpreter diesen Fehler nicht entdecken und melden, statt sich stillschweigend in eine Dauerschleife zu begeben?
Gruß Bernd
Virtueller Speicher Überlauf
der pythoninterpreter macht das, was da steht.
der meldet keine fehler wie ein c/c++ compiler, er beachtet gar nicht,
was er macht. er weiß es auch gar nicht.
der meldet keine fehler wie ein c/c++ compiler, er beachtet gar nicht,
was er macht. er weiß es auch gar nicht.
http://www.cs.unm.edu/~dlchao/flake/doom/
-
- User
- Beiträge: 9
- Registriert: Sonntag 22. Oktober 2006, 21:05
Danke Murph,
ich dachte schon, einen Fehler im Interpreter gefunden zu haben.
Dafür ist der Interpreter wenigstens schnell.
Gruß Bernd
ich dachte schon, einen Fehler im Interpreter gefunden zu haben.
Dafür ist der Interpreter wenigstens schnell.
Gruß Bernd
Argh! Murph schreibt mal wieder Müll. Er weiss nicht was er tut, der Pythoninterpretierer schon. Wenn der Speicher ausgeht, dann wird das Programm mit einer `MemoryError` Ausnahme abgebrochen:
Code: Alles auswählen
$ python forum.py
Traceback (most recent call last):
File "forum.py", line 42, in ?
main()
File "forum.py", line 38, in main
print isprime(999999999999999999)
File "forum.py", line 11, in isprime
klist = primes(int(math.sqrt(aNumber+1)))
File "forum.py", line 20, in primes
s=range(3,n+1,2)
MemoryError
Wo hast Du den denn zufällig entdeckt? Wie sieht Dein Programm aus und wie hast Du es gestartet?Bernd Jonsson hat geschrieben:Dabei blieb das Programm bei sehr großen Zahlen 'hängen'. Mehr durch Zufall entdeckte ich einen Fehler-Hinweis: Mangel an virtuellem Speicher.
Wieso Flop? Er tut das was er soll.Ursache ist der immense Speicherbedarf in der Routine primes (Algorithmus 366178) im Statement "s=range(3,n+1,2)"
Damit entpuppte sich Algorithmus 410662 als Flop.
Sollte nicht nur, er tut es auch.Meine Frage ist, sollte der Python-Interpreter diesen Fehler nicht entdecken und melden, statt sich stillschweigend in eine Dauerschleife zu begeben?
@blackjack:
das habe ich so direkt gelesen!
der schaut beim compilieren des byte-codes nicht nach, was gemacht wird,
das passiert erst, wenn der code ausgeführt wird.
das stand in einem artikel im internet, den ich sehr aufmerksam gelesen habe.
falls du daran zweifel haben solltest, kann ich den vllt nochmal raussuchen.
kann auch sein, dass der autor falsch lag.
das habe ich so direkt gelesen!
der schaut beim compilieren des byte-codes nicht nach, was gemacht wird,
das passiert erst, wenn der code ausgeführt wird.
das stand in einem artikel im internet, den ich sehr aufmerksam gelesen habe.
falls du daran zweifel haben solltest, kann ich den vllt nochmal raussuchen.
kann auch sein, dass der autor falsch lag.
http://www.cs.unm.edu/~dlchao/flake/doom/
@murph: Das stimmt zwar, ist aber nicht relevant: Der Interpreter, soll und wird, wenn das Problem so auftritt wie beschrieben, die entsprechende Fehlermeldung abgeben.
Gruß,
Christian
Gruß,
Christian
ok
http://www.cs.unm.edu/~dlchao/flake/doom/
Und das ist auch bei C/C++ nicht anders, auch die Erkennen beim Übersetzen nicht, ob das Programm während der Laufzeit irgendwann einmal zuviel Speicher verbrauchen könnte. Wie sollte das auch gehen!?
indem man mitzählt...^^ *scherz*
aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
hatte nur noch im hinterkopf, dass C-compiler ganz komische sachen manchmal machen...
aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
hatte nur noch im hinterkopf, dass C-compiler ganz komische sachen manchmal machen...
http://www.cs.unm.edu/~dlchao/flake/doom/
Ist aber reichlich theoretisch: Jeder Interpreter / Compiler müsste für alle (auch zukünfigen) Maschinen wissen, wie groß Speicherplätze für bestimmte Typen sind (was bei dynamischen Sprachen nochmal so witzig sein dürfte wie für statische ). Und dann müßte der Interpreter / Compiler für jedes Nesting Level die Logik überprüfen. Das ist hier noch vergleichsweise einfach, aber grundsätzlich nicht ohne, wenn nicht gar unmöglich (vielleicht wisse da "echte" Informatiker mehr).murph hat geschrieben: aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Außerdem: Wo gibt es hier bitte eine Endlosschleife, jedenfalls nicht in den beiden Recipies.
Gruß,
Christian
Sofern man definiert, was man für sinnvoll hält, könnte, je nach definition, da etwas überlegt werden.dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Allerdings bezweifele ich das, da das ziemlich in Richtung Halteproblem geht.
Nein hier geht es nicht um eine Endlosschleife sondern um eine einfache Speicheranforderung bei der Erstellung einer Liste mit `range()`.murph hat geschrieben:aber hier geht es um eine endlosschleife, die den speicher auffrisst,
dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Und ob eine Schleife sinvoll ist bestimmt der Programmierer weil der den Sinn kennt. Solange Computer nicht denken können, können sie auch solche Sinnfragen nicht beantworten.
-
- User
- Beiträge: 9
- Registriert: Sonntag 22. Oktober 2006, 21:05
Hallo BlackJack,
a) Wie ich auf die Meldung 'virtueller Speichermangel' gestoßen bin,
wusste ich nicht - Panikstimmung.
Ich arbeite mit Python unter Windows XP, das Internet nutze ich unter Linux.
Das ist natürlich für diese Diskussion umständlich.
Inzwischen habe ich das Programm erneut gestartet und dann mittels AltGr/F4
abgebrochen.
Unten rechts erschien die Meldung: Windows - nicht genügend virtueller Speicher.
... Die Auslagerungsdatei wird vergrößert. Speicheranforderungen können
während dieses Vorgangs abgelehnt werden. ...
Das Ganze scheint wohl ein Fehler von Windows XP zu sein und nicht vom Python-
Interpreter! Sch....önes Windows!
b) Dass Dein Programm ordnungsgemäß mit Fehlermeldung abbrach, wunderte mich
zunächst, aber Du arbeitest vermutlich mit Linux? Erst wollte ich Dir meinen
Quelltext zusenden, aber das erübrigt sich jetzt wohl, denn unsere
Progmme sind im Kern ja identisch.
c) Wieso Flop? Weil das Programm schon bei relativ kleinen Zahlen
etwa bei 10**15 aussteigt. Bis dahin ist der Zeitgewinn noch relativ klein,
wenn als Divisor nur die zuvor ermittelten Primzahlen benutzt werden.
Die Idee von gian paolo ciceri ist zwar gut, bringt aber letztlich nichts.
Habe das Programm jetzt abgeändert, ohne Speicherplatz für das
Eratosthenes-Sieb, komme dadurch auf Primzahlen wie (10**20 + 17)
bei ca. 90 Minuten Rechenzeit.
Klar, ist alles nur Spielerei, selbst auf Superrechnern dürfte mit
diesem Algorithmus spätestens nach zehn weiteren Dezimalen Schluss
sein.
Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
Gruß Bernd
a) Wie ich auf die Meldung 'virtueller Speichermangel' gestoßen bin,
wusste ich nicht - Panikstimmung.
Ich arbeite mit Python unter Windows XP, das Internet nutze ich unter Linux.
Das ist natürlich für diese Diskussion umständlich.
Inzwischen habe ich das Programm erneut gestartet und dann mittels AltGr/F4
abgebrochen.
Unten rechts erschien die Meldung: Windows - nicht genügend virtueller Speicher.
... Die Auslagerungsdatei wird vergrößert. Speicheranforderungen können
während dieses Vorgangs abgelehnt werden. ...
Das Ganze scheint wohl ein Fehler von Windows XP zu sein und nicht vom Python-
Interpreter! Sch....önes Windows!
b) Dass Dein Programm ordnungsgemäß mit Fehlermeldung abbrach, wunderte mich
zunächst, aber Du arbeitest vermutlich mit Linux? Erst wollte ich Dir meinen
Quelltext zusenden, aber das erübrigt sich jetzt wohl, denn unsere
Progmme sind im Kern ja identisch.
c) Wieso Flop? Weil das Programm schon bei relativ kleinen Zahlen
etwa bei 10**15 aussteigt. Bis dahin ist der Zeitgewinn noch relativ klein,
wenn als Divisor nur die zuvor ermittelten Primzahlen benutzt werden.
Die Idee von gian paolo ciceri ist zwar gut, bringt aber letztlich nichts.
Habe das Programm jetzt abgeändert, ohne Speicherplatz für das
Eratosthenes-Sieb, komme dadurch auf Primzahlen wie (10**20 + 17)
bei ca. 90 Minuten Rechenzeit.
Klar, ist alles nur Spielerei, selbst auf Superrechnern dürfte mit
diesem Algorithmus spätestens nach zehn weiteren Dezimalen Schluss
sein.
Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
Gruß Bernd
Ich habe mein Windows, das ich ab und zu leider noch brauche, in einen VMWare Server gesperrt. Ist mittlerweile kostenlos. Also der VMWare Server, nicht Windows.Bernd Jonsson hat geschrieben: a) Wie ich auf die Meldung 'virtueller Speichermangel' gestoßen bin,
wusste ich nicht - Panikstimmung.
Ich arbeite mit Python unter Windows XP, das Internet nutze ich unter Linux.
Das ist natürlich für diese Diskussion umständlich.
Eher schon bei 2**31-1, das ist zumindest bei 32-Bit Systemen die maximale Anzahl an Elementen in einer Liste. Bei 64-Bit Systemen und Python 2.5 geht dann mehr.c) Wieso Flop? Weil das Programm schon bei relativ kleinen Zahlen
etwa bei 10**15 aussteigt.
Und für praktische Anwendungen nimmt man dann doch lieber in Kauf ein kleines Restrisiko einer Nicht-Primzahl zu haben und benutzt Miller-Rabin zum Testen. Ist wesentlich schneller.Habe das Programm jetzt abgeändert, ohne Speicherplatz für das
Eratosthenes-Sieb, komme dadurch auf Primzahlen wie (10**20 + 17)
bei ca. 90 Minuten Rechenzeit.
Klar, ist alles nur Spielerei, selbst auf Superrechnern dürfte mit
diesem Algorithmus spätestens nach zehn weiteren Dezimalen Schluss
sein.
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Du kannst es entweder, wenn es nicht zu lang ist direkt hier rein stellen oder anderfalls einen Paste-Service verwenden. Mein Lieblingspaste ist inzwischen paste.e-scribe.com geworden, weil es mit Python gemacht istBernd Jonsson hat geschrieben: Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
-
- User
- Beiträge: 9
- Registriert: Sonntag 22. Oktober 2006, 21:05
Hi BlackJack,
Zu Deinem 2. Punkt: Wieso Flop
Das verstehe ich nicht ganz. Bei Dir ist der Rechner doch auch schon bei etwa 10**18 (999999999999999999) mit Fehlermeldung ausgestiegen!
Der letzte Punkt ist klar, aber mit Rabin-Miller werden Primzahlen konstruiert, er eignet sich aber nicht zum Primzahltest, sonst wären alle Verschlüsselungsverfahren unsicher.
Ich kopiere mal mein Programm, um es zur Diskussion zu stellen,
(Danke Leonidas, für Deinen Hinweis) :
Edit (Leonidas): Code in Python-Tags gesetzt.
Zu Deinem 2. Punkt: Wieso Flop
Das verstehe ich nicht ganz. Bei Dir ist der Rechner doch auch schon bei etwa 10**18 (999999999999999999) mit Fehlermeldung ausgestiegen!
Der letzte Punkt ist klar, aber mit Rabin-Miller werden Primzahlen konstruiert, er eignet sich aber nicht zum Primzahltest, sonst wären alle Verschlüsselungsverfahren unsicher.
Ich kopiere mal mein Programm, um es zur Diskussion zu stellen,
(Danke Leonidas, für Deinen Hinweis) :
Code: Alles auswählen
def isprime(aNumber):
'''return True if the number is prime, false otherwise'''
if aNumber < 2 : return False
for k in (2,3,5,7) :
if ((aNumber%k) == 0) : return False
#
k = 11
list = (2,4,2,4,6,2,6,4,2,4,6)
i = 0
while i < len(list) :
if ((aNumber%k) == 0) : return False
k += list[i]
i += 1
#
# Im folgenden Programmstück werden für die Modulo-Operation
# nur Divisorenbenutzt, die keine Vielfachen von 2, 3, 5, 7 sind.
kmax = int(aNumber**0.5)
list = (6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,
4,2,4,6,2,6,4,2,4,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6)
lenlist = len(list)
while True :
i = 0
while i < lenlist :
if ((aNumber%k) == 0) : return False
k += list[i]
i += 1
#
if k > kmax : break
#
return True
#
benutze am besten die code-tags.
findest du im editor neben dem quote und bei den anderen buttons,,,
findest du im editor neben dem quote und bei den anderen buttons,,,
http://www.cs.unm.edu/~dlchao/flake/doom/
-
- User
- Beiträge: 1790
- Registriert: Donnerstag 28. Oktober 2004, 16:33
- Wohnort: Graz, Steiermark - Österreich
- Kontaktdaten:
....und pygments nutztLeonidas hat geschrieben:Du kannst es entweder, wenn es nicht zu lang ist direkt hier rein stellen oder anderfalls einen Paste-Service verwenden. Mein Lieblingspaste ist inzwischen paste.e-scribe.com geworden, weil es mit Python gemacht istBernd Jonsson hat geschrieben: Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
TUFKAB – the user formerly known as blackbird
Wenn ich mit einem Grafikprogramm kein Bild bearbeiten kann das die Grösse eines Fussballfeldes bei 4000dpi besitzt, dann heisst das nicht, dass das Grafikprogramm ein Flop ist. Es ist einfach nur das falsche Werkzeug für so eine Datenmenge.Bernd Jonsson hat geschrieben:Zu Deinem 2. Punkt: Wieso Flop
Das verstehe ich nicht ganz. Bei Dir ist der Rechner doch auch schon bei etwa 10**18 (999999999999999999) mit Fehlermeldung ausgestiegen!
Und "schon" bei 10**18? Es müsste eine Liste mit so vielen Elementen angelegt werden. Eine Liste enthält intern Zeiger auf ihre Elemente; so ein Zeiger ist auf 32-Bit-Plattformen 4 Bytes gross; der Speicherbedarf wäre also *mindestens* 4000 *Petabytes*!
Mit dem Miller-Rabin, den ich meine, werden Zahlen auf "ist (wahrscheinlich) Prim" getestet. Und das macht keine Verschlüsselungsverfahren unsicher. Der Knackpunkt dort ist eine sehr grosse Zahl in ihre Primfaktoren zu zerlegen, was etwas anderes als ein Primzahltest ist.Der letzte Punkt ist klar, aber mit Rabin-Miller werden Primzahlen konstruiert, er eignet sich aber nicht zum Primzahltest, sonst wären alle Verschlüsselungsverfahren unsicher.
Indexvariablen die man dann auch noch selbst in ``while``-Schleifen "verwaltet" sind in "unpythonisch" weil man direkt über die Elemente von Listen und andere Containerobjekten iterieren kann. Die erste ``while``-Schleife kann man z.B. ganz einfach durch eine kürzere ``for``-Schleife ersetzen:Ich kopiere mal mein Programm, um es zur Diskussion zu stellen, [...]
Code: Alles auswählen
k = 11
for i in (2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6):
if aNumber % k == 0:
return False
k += i
Code: Alles auswählen
from itertools import cycle
# ...
def divisors(start_k):
k = start_k
for step in cycle((6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4,
6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,
10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6)):
yield k
k += step
# ...
kmax = int(aNumber**0.5)
for k in divisors(k):
if aNumber % k == 0:
return False
if k > kmax:
break
-
- User
- Beiträge: 9
- Registriert: Sonntag 22. Oktober 2006, 21:05
Hi BlackJack,
wieder etwas gelernt, danke für die Programmiertips. Bin halt noch ein Python-Newby.
Auch Dank für die Verschönerung meines Scripts!
Zu Punkt 1) sind wir uns im Grunde doch einig, denn der Algorithmus 410662 von gian paolo ciceri sollte eine Beschleunigung für Algorithmus 366178 sein, versagt aber wegen des range-Befehls und beim späteren Listenaufbau vorzeitig. Nur in einem engen Zahlenbereich ist er gegenüber dem Hauruckverfahren schneller. Und auch meine Lösung oben steigt nicht mit Fehler aus, einzige Hürde ist die Rechenzeit bei sehr großen Zahlen.
Zu Punkt 2) sind wir wir auch einer Meinung. Mein Primzahltest(und andere) versucht ja auch eine Zerlegung und endet beim ersten Erfolg, meldet den Faktor jedoch nicht. Die nachfolgende Faktorisierung ist dann ein Kinderspiel.
Nun muss ich doch noch einmal auf das ursprüngliche Problem:
"Virtueller Speichermangel Hängenbleiben in Dauerschleife"
zurückkommen
Habe den Algorithmus 366178/410662 aus Versehen noch einmal mit einer sehr großen Zahl n = 10**11 laufen lassen und bekam wie Du ordnungsgemäß den MemoryError beim Befehl "s = range(3,n+1, 2)".
Das heißt, bei mittelgroßen Zahlen wie n = 10**8 funktioniert der range-Befehl noch fehlerfrei, aber beim Aufbau der Liste im return-Befehl
"return [2] + [x for x in s if x]"
erfolgt der virtuelle Speichermangel ohne jede Fehlermeldung.
Frage: Ist das dann doch nicht ein Fehler des Python-Interpreters?
Gruß Bernd
wieder etwas gelernt, danke für die Programmiertips. Bin halt noch ein Python-Newby.
Auch Dank für die Verschönerung meines Scripts!
Zu Punkt 1) sind wir uns im Grunde doch einig, denn der Algorithmus 410662 von gian paolo ciceri sollte eine Beschleunigung für Algorithmus 366178 sein, versagt aber wegen des range-Befehls und beim späteren Listenaufbau vorzeitig. Nur in einem engen Zahlenbereich ist er gegenüber dem Hauruckverfahren schneller. Und auch meine Lösung oben steigt nicht mit Fehler aus, einzige Hürde ist die Rechenzeit bei sehr großen Zahlen.
Zu Punkt 2) sind wir wir auch einer Meinung. Mein Primzahltest(und andere) versucht ja auch eine Zerlegung und endet beim ersten Erfolg, meldet den Faktor jedoch nicht. Die nachfolgende Faktorisierung ist dann ein Kinderspiel.
Nun muss ich doch noch einmal auf das ursprüngliche Problem:
"Virtueller Speichermangel Hängenbleiben in Dauerschleife"
zurückkommen
Habe den Algorithmus 366178/410662 aus Versehen noch einmal mit einer sehr großen Zahl n = 10**11 laufen lassen und bekam wie Du ordnungsgemäß den MemoryError beim Befehl "s = range(3,n+1, 2)".
Das heißt, bei mittelgroßen Zahlen wie n = 10**8 funktioniert der range-Befehl noch fehlerfrei, aber beim Aufbau der Liste im return-Befehl
"return [2] + [x for x in s if x]"
erfolgt der virtuelle Speichermangel ohne jede Fehlermeldung.
Frage: Ist das dann doch nicht ein Fehler des Python-Interpreters?
Gruß Bernd