Hilfe bei Umsetzung

[Sid]

Hallo Leute!

Also ich bräuchte eure Hilfe bei einem Programm, das eigentlich relativ simpel ist, ich selber finde aber nicht die Zeit, es umzusetzen.

Die Aufgabenstellung ist:

Die Zahl Pi soll mit 10 Millionen Nachkommastellen angegeben werden.

Dazu soll man hier die Leerstellen mithilfe von Python entfernen. (Muss nicht das pdf sein, konnte nur kein anderes Dokument mit 10 Millionen Nachkommstellen finden).

Weiters soll man mithilfe des Programmes herausfinden können, an welcher Nachkommastelle das eigene Geburtsdatum das erste Mal vorkommt. (also zum Beispiel der 1. Dezember 1964 in der Form 011264).

Und als letztes soll man noch rausfinden, welches Geburtsdatum sich nicht finden lässt (es gibt nur ein einziges).

Wäre echt nett von euch, wenn ihr mir da helfen könntet, ist ziemlich dringend.

Ich zähl auf euch Pythonspezialisten , für euch ist das sicher kein großes Problem.

Danke schonmal im Voraus,
Sid

Edit (Leonidas): Verschoben nach "Allgemeine Fragen"

[mr.hide]

Hausaufgaben ist etwas was man selber erledigen sollte

Entwickle doch einfach einen eigenen Lösungsansatz vielleicht gibts dann ja ein par Tips.

Oder bezahl mich

[Joghurt]

(Muss nicht das pdf sein, konnte nur kein anderes Dokument mit 10 Millionen Nachkommstellen finden).

Schade, für 1 Million Stellen gibt es die "gut" merkbare

http://3.141592653589793238462643383279 ... 44592.com/

Für 10 Millionen schaust du hier: http://www.solidz.com/pi/

(Python kann bz2-Komprimierte Dateien auch direkt lesen)

[Leonidas]

Also ich bräuchte eure Hilfe bei einem Programm, das eigentlich relativ simpel ist, ich selber finde aber nicht die Zeit, es umzusetzen.

Warum sollten wir dann? Weil wir den ganzen lieben langen Tag und dann noch die Nacht gerne Hausaufgabern zu lösen?

Dazu soll man hier die Leerstellen mithilfe von Python entfernen. (Muss nicht das pdf sein, konnte nur kein anderes Dokument mit 10 Millionen Nachkommstellen finden).

Habe gerade keine Lust das PDF runterzuladen, weil es großer als 100kb ist Was steht da drin? 10 Millionen Nachkommastellen von Pi?

Weiters soll man mithilfe des Programmes herausfinden können, an welcher Nachkommastelle das eigene Geburtsdatum das erste Mal vorkommt. (also zum Beispiel der 1. Dezember 1964 in der Form 011264).

Dazu konvertiert man die Zahl in einen String und sucht danach. Wo ist das Problem?

Und als letztes soll man noch rausfinden, welches Geburtsdatum sich nicht finden lässt (es gibt nur ein einziges).

Etwas schwieriger, aber dennoch nicht unlösbar. Schlimmstenfalls kann man es per Brute-Force herausfinden. Hier könnte ich mir vorstellen dass man einen Generator für Geburtsdaten schreibt und diese dann prüft. Nicht schön, aber einfach.

Wäre echt nett von euch, wenn ihr mir da helfen könntet, ist ziemlich dringend.

Warum? Weil du zu spät angefangen hast?

Ich zähl auf euch Pythonspezialisten , für euch ist das sicher kein großes Problem.

Nein, warscheinlich nicht. Für dich aber auch nicht, da das ja insgesammt kein großes Problem ist.

[Sid]

Okay danke...

Also Lösungsansätze...

begonnen hat das glaub ich mit "import os"...weiß jetzt aber nicht inwieweit das mir weiterhilft...

und um die leerstellen zu entfernen gibts auch einen befehl glaub ich...

Aber wie genau das weitergeht weiß ich eben nicht, deswegen hab ich mich hier angemeldet

[Joghurt]

Dann poste doch, was du bis jetzt geschrieben hast, und was genau nicht funktioniert.

Denn eine Hausaufgabe, die man nur vorgekaut bekommt, ist vollkommene Zeitverschwendung; sie bringt dir nichts, da du (fast) nichts bei lernst, und uns auch nichts.

[mr.hide]

Okay danke...

Also Lösungsansätze...

begonnen hat das glaub ich mit "import os"...weiß jetzt aber nicht inwieweit das mir weiterhilft...

und um die leerstellen zu entfernen gibts auch einen befehl glaub ich...

Aber wie genau das weitergeht weiß ich eben nicht, deswegen hab ich mich hier angemeldet

So als einstieg:

Code: Alles auswählen

einstring = "ich habe leerstellen"
print einstring.replace( " ","")

[Joghurt]

Code: Alles auswählen

string = "1234567"
try:
  print "34 ist an Position",string.index("34")
except ValueError:
  print "34 nicht gefunden"

tag,monat,jahr = 1,2,1921
gebstring = "%02i%02i%04i" % (tag,monat,jahr)

Das sollte nun aber reichen

[BlackJack]

Und als letztes soll man noch rausfinden, welches Geburtsdatum sich nicht finden lässt (es gibt nur ein einziges).

Etwas schwieriger, aber dennoch nicht unlösbar. Schlimmstenfalls kann man es per Brute-Force herausfinden. Hier könnte ich mir vorstellen dass man einen Generator für Geburtsdaten schreibt und diese dann prüft. Nicht schön, aber einfach.

Ein Lösungsansatz wäre es die Menge aller Geburtstagsdaten (max. 37200) zu erzeugen und dann einmal die Nachkommastellen durchzugehen und die Geburtstage nach und nach aus der Menge zu entfernen. Dann bleibt am Ende ein Geburtstag übrig. Dürfte schneller sein, als die Geburtstage alle in den ganzen Nachkommastellen zu suchen weil man dann mit jedem Geburtstag wieder von vorne anfängt.

So als Lösungsansatz für Sid.

[BlackJack]

Habe gerade nachvollzogen, dass tatsächlich ein Datum nicht enthalten ist.

Das Programm braucht auf einem 1 Ghz Athlon ca. 2 Minuten. Mit `psyco` ist's eine halbe Minute schneller und wenn ich den Schritt mit dem entfernen aller Teilzeichenketten der Länge 6 der Nachkommastellen von `pi` aus der Menge der möglichen Geburtstage in ein Pyrex-Modul auslagere, dann ist das nur unwesentlich langsamer als die `psyco` Beschleunigung.

[gerold]

Mit `psyco` ist's eine halbe Minute schneller

Hi BlackJack!

Dann bringt "psyco" also doch etwas. Bei all meinen Tests, die ich, bzw. ein Mitarbeiter von mir, durchgeführt haben, hat psyco nichts gebracht. Das waren wohl nicht die richtigen Algorithmen die wir beschleunigen wollten.

lg
Gerold

[modelnine]

Also, mit folgender Pi-Datei:

http://www.solidz.com/pi/pi-10m.txt.bz2

und meinem kleinen Script (was ich hier noch nicht poste, außer jemand will Herangehensweise vergleichen und postet zuerst, wir sind ja nicht der Hausaufgabenkanal ) hab ich folgendes Timing auf 'nem Turion-64 MT-32 unter 1800 Mhz

modelnine@phoenix ~/pi $ time python test.py
Remaining: set(['120154'])

real 1m11.272s
user 1m2.449s
sys 0m1.123s
modelnine@phoenix ~/pi $

Das ganze ist nicht Psyco beschleunigt weil der Turion im 64-bit Modus ist (und dementsprechend Psyco nicht zu haben). Wäre mal interessant zu sehen wie andere das machen und was sie rauskriegen.

--- Heiko.

[modelnine]

Lustig. Es macht einen massiven Unterschied ob man einfach wahllos Datums zurückgibt oder aber vorher guckt ob das Datum syntaktisch korrekt ist (wie im folgenden):

modelnine@phoenix ~/pi $ time python test.py
Remaining: set(['120154'])

real 0m30.722s
user 0m28.720s
sys 0m0.773s
modelnine@phoenix ~/pi $

--- Heiko.

[modelnine]

Vorher zu prüfen ob ein Datum im set noch drin ist bevor man es rausnimmt (um eine exception zu vermeiden) bringt dann nicht mehr viel:

modelnine@phoenix ~/pi $ time python test.py
Remaining: set(['120154'])

real 0m29.515s
user 0m27.275s
sys 0m0.695s
modelnine@phoenix ~/pi $

--- Heiko.

[modelnine]

Das ganze noch mal mit komplettem Einlesen der Strings aus dem BZ2-File, nicht zeilenweise (braucht natürlich massiv Speicher):

modelnine@phoenix ~/pi $ time python test.py
Remaining: set(['120154'])

real 0m27.403s
user 0m25.113s
sys 0m0.294s
modelnine@phoenix ~/pi $

python -O bringt ganz davon abgesehen so gut wie gar nix, was ja auch nicht anders zu erwarten war.

--- Heiko.

[Leonidas]

python -O bringt ganz davon abgesehen so gut wie gar nix, was ja auch nicht anders zu erwarten war.

Bringt ja auch nur was wenn es Module gibt die als -O .pyc oder -OO .pyo importiert werden. Das eigentliche Script welches direkt aufgerufen wird, wird vom Interpreter (CPython natürlich nur, IronPython regelt das wohl etwas anders) nur on-the-fly in Bytecode verwandelt, somit muss es bei jedem Aufruf neu erstellt werden. Das ist aber ja meist nicht sonderlich problematisch, ich nutze -O oder -OO sowieso fast nie.

[modelnine]

Dass es keine .pyo-s gibt hat absolut nichts damit zu tun dass -O wenig bringt.

-O ist nicht dafür gedacht irgendwelche optimierten Module zu laden, sondern während des Compilierschritts einige Optimierungen bei der Erstellung des Byte-Codes vorzunehmen. Das sind momentan kaum welche (zum Beispiel nur das assert und if __debug__ "vergessen" wird), und dementsprechend ist der entstandene Bytecode kaum schneller.

Wenn irgendwann mal optimierter Bytecode für die Python VM erzeugt werden kann, dann wird -O auch was bringen.

--- Heiko.

[BlackJack]

Wollte nur sagen das ich das gleiche Datum herausbekommen habe. Und das ich die gleiche "Pi-Datei" benutzt habe.

@modelnine: Was meintest Du denn mit zeilenweise einlesen? Fängst Du beim Einlesen schon an die Daten aus dem `set` zu löschen? Das war mir zu aufwändig.

Du könntest statt Psyco ja auch Teile mit Pyrex übersetzen. Das sollte doch auch auf 64-Bit Architekturen funktionieren, oder?

[modelnine]

Zeilenweise einlesen bedeutet dass man ja im Prinzip nur einen Iterator braucht der eine Zeile nach der anderen bekommt und direkt wenn er einen Teilstring ausgewertet hat diesen aus dem Set probiert zu löschen.

Diese Art des Iterators hab ich beibehalten, nur braucht der Iterator auch aus der Eingabedatei die Daten nur zeilenweise. Man kann also die Daten entweder "vorlesen", oder aber sie einzelnen aus der Datei rausholen. Und das "vorlesen" braucht zwar massig mehr Speicher (ca. 400 MB), aber ist eben schneller als über die Zeilen zu iterieren und immer nur eine im Speicher zu haben...

--- Heiko.

[mr.hide]

hmmm,

habs aus zeitmangel nicht probiert, aber ist das "löschen" nicht fehlerhaft


z.b:

210719811111944

löschman hier: 21071981 wird nicht mehr der 11. sondern nur noch der 1. gefunden, 1111944 statt 11111944


EDIT: ich glaub jetzt hab ichs kapiert ihr lauft den string durch und löscht aus der liste der Geburtsdaten ... und nicht umgekehrt