Seite 2 von 2
Verfasst: Sonntag 2. November 2008, 19:48
von numerix
Das ist ja genau das, was ich schon in meinem ersten Posting (allerdings ohne Code) gesagt hatte: In Python 2.6 schnell erledigt. Hat mich die ganze Zeit gewundert, warum so lange daran herumgebastelt wurde ...

Verfasst: Sonntag 2. November 2008, 20:13
von yipyip
In Python 5000 werden wir dann endlich haben:
Code: Alles auswählen
from all_problems import my_problem
my_problem.solve()
yipyip
Verfasst: Sonntag 2. November 2008, 20:52
von DasIch
yipyip hat geschrieben:In Python 5000 werden wir dann endlich haben[...]
Ach was, hab ich jetzt schon:
Code: Alles auswählen
In [11]: import sys
In [12]: from types import ModuleType
In [13]: sys.modules['all_problems'] = ModuleType('all_problems')
In [14]: class my_problem(object):
....: @staticmethod
....: def solve():
....: return 42
....:
In [15]: sys.modules['all_problems'].my_problem = my_problem
In [16]: from all_problems import my_problem
In [17]: my_problem.solve()
Out[17]: 42
Verfasst: Sonntag 2. November 2008, 21:09
von numerix
yipyip hat geschrieben:In Python 5000 werden wir dann endlich haben:
Code: Alles auswählen
from all_problems import my_problem
my_problem.solve()
yipyip
Dann wird's aber langweilig

Verfasst: Sonntag 2. November 2008, 21:26
von yipyip
@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann.
@numerix:
Nicht traurig sein, in diesem Forum
wird es auch weiterhin genug zu tun geben.
yipyip
Verfasst: Sonntag 2. November 2008, 21:44
von DasIch
yipyip hat geschrieben:@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann.

Wenn du daran interessiert bist schau dir mal
Zine an, dort wird das Produktiv genutzt um ein Datenbank Modul zu erzeugen, ziemlich coole Sache.
Verfasst: Samstag 8. November 2008, 10:55
von roschi
MERCI!
der C-code, den abgdf gepostet hat, funktioniert wunderbar schnell. leider kenne ich mich mit C so gut wie gar nicht aus. koennte mir vielleicht jemand sagen, wie man den code so erweitern koennte, dass er auch teilstrings erzeugt, und nicht nur alle kombinationen (das sind ja jetzt wirklich kombinationen

)?
außerdem habe ich mir mal python 2.6 zusaetzlich installiert, und das hier ausprobiert:
Code: Alles auswählen
def perm(s):
for i in xrange(len(s) + 1):
for combination in combinations(s, i):
for permutation in permutations(combination):
if permutation:
print "".join(permutation)
perm("eis")
klappt auch wunderbar, ist nur - was ja auch logisch ist - deutlich langsamer als die methode in C, die ich eben bevorzugen wuerde.
lg
roschi
Verfasst: Samstag 8. November 2008, 12:55
von Mad-Marty
Wie wärs denn wenn du diesen unsinnigen ansatz mit liste generieren komplett verwirfst?
Soll bestimmt ein Passwortcracker per Bruteforce werden oder?
Auf einem normalen Rechner wirst du wohl mit einem generator arbeiten müssen, dann brauchst du auch nicht soviel RAM.
Alles andere halte ich für ausserhalb deiner hardwaremöglichkeiten ...
Verfasst: Samstag 8. November 2008, 18:50
von roschi
hallo!
@Mad Marty:
die liste habe ich jetzt rausgenommen. ist ja klar, das es damit bei so großen nicht klappen kann. ich gebe jetzt alles nach stdout aus und leite es in eine datei um.
nein, es soll kein bruteforce passwort cracker werden. ich moechte am ende jedes ergebnis auf presens in einem woerterbuch pruefen, um alle sinnvollen woerter aus dem ursprungs-string zu erhalten.
lg
roschi
PS: ich habe von etwa um 11:00 uhr bis jetzt 81 GB an daten mit der python-methode erzeugt.
Verfasst: Samstag 8. November 2008, 18:53
von DasIch
Wie wäre es mit
Kölner Phonetik oder
Soundex?
Verfasst: Samstag 8. November 2008, 19:07
von roschi
ich glaube, wir reden aneinander vorbei. ich will keine aenlich klingenden woerter haben, sondern welche, die man aus einigen oder allen buchstaben des ursprungswortes bilden kann - egal in welcher reihenfolge die buchstaben verwendet werden.
lg
roschi
Verfasst: Samstag 8. November 2008, 19:34
von BlackJack
@roschi: Argh! Bist Du wahnsinnig!? Ums mal vorsichtig auszudrücken.
Da geht man besser den umgekehrten Weg und testet jedes Wort im Wörterbuch ob man es mit den vorhandenen Buchstaben bilden kann. Das durfte *deutlich* schneller sein als 81 GiB an Daten zu erzeugen von denen man im Vorfeld schon weiss, dass 99% davon nicht im Wörterbuch vorkommen werden.
Simpelste Methode zum finden von Anagrammen ist das sortieren der Buchstaben im Suchwort und allen Worten die untersucht werden. Wenn die dann gleich sind, hat man einen Treffer.
PS: Beispiel:
Code: Alles auswählen
In [301]: sorted('schaeuble')
Out[301]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
In [302]: sorted('belausche')
Out[302]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
Auf die Art kannst Du auch das komplette Wörterbuch mal vorverarbeiten und schauen welche Anagramme da enthalten sind.
Verfasst: Samstag 8. November 2008, 20:40
von roschi
@BlackJack:
es gibt eben doch noch leute, die mehr nachdenken als ich.

ich haette wohl gleich sagen sollen, was ich vorhabe.
vielen, vielen, lieben dank an alle, die versucht haben, mir zu helfen!
lg
roschi
Verfasst: Sonntag 9. November 2008, 00:54
von Leonidas
BlackJack hat geschrieben:Code: Alles auswählen
In [301]: sorted('schaeuble')
Out[301]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
In [302]: sorted('belausche')
Out[302]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
Ich sehe, auch hier gibt es Leser von Fefes Blog

Verfasst: Sonntag 9. November 2008, 01:40
von abgdf
'belausche' ist ein Anagramm von 'schaeuble' ? Wie geil ist das denn

?
Es könnte sein, daß es schon genügt, nur die Anzahl der einzelnen Buchstaben zu vergleichen. "string.count()" ist da sehr hilfreich.
Gruß
Verfasst: Sonntag 9. November 2008, 10:08
von roschi
so, falls es nun jemanden interessieren sollte:
Code: Alles auswählen
# -*- coding: iso-8859-15 -*-
import sys
def main(inputstring, dictfile="dict.txt"):
fi = file(dictfile, "r")
entries = fi.read().split()
fi.close()
inputstring = inputstring.lower()
raw_chars = {}
for char in inputstring:
raw_chars[char] = inputstring.count(char)
data = []
for entrie in entries:
entrie_show = entrie
entrie = entrie.lower()
chars_copy = {}
for item in raw_chars:
chars_copy[item] = raw_chars[item]
is_okay = True
for char in entrie:
if char in chars_copy and chars_copy[char] > 0:
chars_copy[char] -= 1
else:
is_okay = False
if is_okay:
data.append(entrie_show)
fo = file("out.txt", "w")
fo.write("\n".join(data + [""]))
fo.close()
main(sys.argv[1])
das funktioniert einwandfrei und natuerlich bedeutend schneller

ich hab ein 3,4 MB großes woerterbuch, werde mir aber bald ein deutlich groeßeres besorgen. naja, jedenfalls muss ich keine 81 GB daten erzeugen
ein riesengroßes dankeschoen nochmal !
lg
roschi
Verfasst: Sonntag 9. November 2008, 11:04
von BlackJack
Ist von der Laufzeit natürlich besser, aber immer noch fürchterlich kompliziert und verbrät immer noch eine Menge unnötiger Rechenzeit.
Die Berechnung von `raw_chars` hat quadratische Laufzeit, weil `count()` für jedes Zeichen jedes mal wieder `inputstring` von vorne bis hinten durchläuft.
Ein Dictionary kann man einfacher kopieren, in dem man das alte `dict()` als Argument gibt, also Zeile 20-22 wird zu ``chars_copy = dict(raw_chars)``.
Wenn `is_okay` auf `False` gesetzt wird, macht es keinen Sinn die Schleife noch weiter abzuarbeien. Wenn man den Test in eine Funktion auslagert, kann man sich `is_okay` komplett sparen und an der Stelle gleich ein ``return False`` schreiben.
Wobei ich mir nicht sicher bin, ob das Programm wirklich das macht, was es soll, weil auch Einträge in `data` kommen, die nicht alle Buchstaben des Eingabewortes verwenden. Ist das gewollt?
Man könnte ganz am Anfang auch noch eine Bedingung setzen, die die Längen überprüft. Wenn das Wort aus dem Wörterbuch länger als die Eingabe ist, kann man sich den restlichen Test sparen.
Ansonsten würde ich den Code so schreiben, dass das Wörterbuch nicht komplett auf einmal in den Speicher gelesen wird. Auch wenn ein paar Megabyte für heutige Rechner kein Problem mehr darstellen.
Die Funktion würde bei mir die Eingabe und ein "iterable" erhalten und selbst einen Iterator/Generator zurück geben. So ist sie am flexiblesten von der konkreten Ein- und Ausgabe getrennt.
PS: Kleines Beispiel wie ich einen Anagramm-Finder schreiben würde:
Code: Alles auswählen
import codecs
import sys
def normalize(word):
return sorted(word.lower())
def iter_anagrams(word, words, normalize=normalize):
key = normalize(word)
return (w for w in words if len(key) == len(w) and normalize(w) == key)
def main():
word_file = codecs.open('/usr/share/dict/ngerman', 'r', 'iso-8859-1')
word = sys.argv[1].decode('utf-8')
anagrams = iter_anagrams(word, (w.strip() for w in word_file))
sys.stdout.writelines(a.encode('utf-8') + '\n' for a in anagrams)
word_file.close()
Verfasst: Freitag 14. November 2008, 21:06
von roschi
hallo!
@BlackJack:
ja, es ist gewollt, das auch woerter gefunden werden, die nicht alle zeichen des inputstrings verwenden. vielen dank fuer die verbesserungsvorschlaege! es ist wirklich schneller - vor allem durch das pruefen der laenge am anfang. ich moechte ja nicht unbedingt anagramme finden, sondern, wie schon gesagt, auch woerter, die nicht alles aus dem inputstring nutzen.
ein riesengroßes dankeschoen und einen schoenen abend noch!
lg
roschi