Virtueller Speicher Überlauf

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Bernd Jonsson
User
Beiträge: 9
Registriert: Sonntag 22. Oktober 2006, 21:05

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
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

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.
http://www.cs.unm.edu/~dlchao/flake/doom/
Bernd Jonsson
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
BlackJack

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
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.
Wo hast Du den denn zufällig entdeckt? Wie sieht Dein Programm aus und wie hast Du es gestartet?
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.
Wieso Flop? Er tut das was er soll.
Meine Frage ist, sollte der Python-Interpreter diesen Fehler nicht entdecken und melden, statt sich stillschweigend in eine Dauerschleife zu begeben?
Sollte nicht nur, er tut es auch.
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

@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.
http://www.cs.unm.edu/~dlchao/flake/doom/
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

@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
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

ok
http://www.cs.unm.edu/~dlchao/flake/doom/
BlackJack

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!?
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

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...
http://www.cs.unm.edu/~dlchao/flake/doom/
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

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.
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).
Außerdem: Wo gibt es hier bitte eine Endlosschleife, jedenfalls nicht in den beiden Recipies.

Gruß,
Christian
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

dass könnte man sehr wohl mitverfolgen, ob die schleife sinnvoll ist.
Sofern man definiert, was man für sinnvoll hält, könnte, je nach definition, da etwas überlegt werden.
Allerdings bezweifele ich das, da das ziemlich in Richtung Halteproblem geht.
BlackJack

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.
Nein hier geht es nicht um eine Endlosschleife sondern um eine einfache Speicheranforderung bei der Erstellung einer Liste mit `range()`.

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.
Bernd Jonsson
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
BlackJack

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.
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. ;-)
c) Wieso Flop? Weil das Programm schon bei relativ kleinen Zahlen
etwa bei 10**15 aussteigt.
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. :-)
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.
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.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Bernd 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?
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 ist :)
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Bernd Jonsson
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) :

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
#
Edit (Leonidas): Code in Python-Tags gesetzt.
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

benutze am besten die code-tags.
findest du im editor neben dem quote und bei den anderen buttons,,,
http://www.cs.unm.edu/~dlchao/flake/doom/
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Leonidas hat geschrieben:
Bernd 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?
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 ist :)
....und pygments nutzt :D
TUFKAB – the user formerly known as blackbird
BlackJack

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!
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.

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*!
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.
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.
Ich kopiere mal mein Programm, um es zur Diskussion zu stellen, [...]
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:

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
In der zweiten Schleife könnte man die Erzeugung der Zahlen die nicht durch 2, 3, 5 und 7 teilbar sind, in eine Generatorfunktion auslagern und dann über die Elemente iterieren:

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
Beim letzteren muss man in diesem speziellen Fall aber wohl abwägen ob die "hässlichere" Variante nicht die schnellere ist.
Bernd Jonsson
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
Antworten