Seite 2 von 2
Re: Maximum recursion depth
Verfasst: Freitag 25. Mai 2012, 14:55
von MarcelF6
Danke für die weiteren Vorschläge.
Zum ersten Vorschlag habe ich eine Frage: So wie er hier steht gibt er am Schluss ja dann einfach die Wörter aus, oder?
Die eigentliche "Arbeit" für den Computer wäre dann ja trotzdem die Gleiche, weil er alle Buchstaben finden muss, die bei allen eingegeben Strings vorkommen...
Edit: Missverständnis korrigiert
Re: Maximum recursion depth
Verfasst: Freitag 25. Mai 2012, 15:01
von jerch
Wer ist er?
@Arbeit:
Das Ergebnis sagt doch nichts über den Weg, über den Du das erreicht hast, aus.
Re: Maximum recursion depth
Verfasst: Freitag 25. Mai 2012, 15:09
von MarcelF6
Naja, das stimmt schon. Aber falls ich den Algorithmus mit der Vorlage des ersten Vorschlags wieder gleich (d.h. analog) implementieren würde, wäre der PC trotzdem nicht schneller. (bzw. der Code an sich immernoch ungünstig).
Re: Maximum recursion depth
Verfasst: Samstag 26. Mai 2012, 14:57
von jerch
Überleg Dir einfach mal, wie oft Dein Algorithmus die Stringelemente durchlaufen muss (das ist irgendwas exponentielles, O(3^(3*n)) worst case). Meine Version schafft es in O(n^3) für 3 Strings a n Elemente. Keine Frage, dass man das weiter verbessern kann, bleibt man allerdings beim Datentyp Liste, ist es kaum besser zu schaffen, da hier die Suche nunmal O(n) ist. Das Problem adressiert u.a. die Wörterbuchversion, wo man mit einer modifizierten Version es bis auf O(4*n) reduzieren könnte (unter der Annahme, dass der Zugriff O(1) average und die Alphabetlänge gleich der Stringlänge n ist).
Edit:
Falls Du nicht weisst, wovon ich hier rede, probier es einfach mal es mit unterschiedlicher Stringanzahl und Stringlängen.
Zum Schluss noch die vereinfachte Wörterbuchversion mit ein paar Erklärungen:
Code: Alles auswählen
def seq(*args, **kwargs):
hits = kwargs.get('hits')
if not hits:
hits = len(args)
temp = {}
for s in args: # m Strings
for c in s: # der Länge n (Vereinfachung): O(m*n)
temp.setdefault(c, 0) # O(1)
temp[c] += 1 # O(1)
# return: temp enthält k Einträge : O(m*n+k)
# obere Abschätzung: k kann maximal n sein : O((m+1)*n)
# Subaufrufe sind alle O(1) - keine Abhängigkeit zu m, n oder k
return [k for k,v in temp.iteritems() if v==hits]
Mit der Counterklasse aus collections ginge der Quellcode noch weiter zu vereinfachen, allerdings sieht man dann die Einzelschritte für die Komplexitätsabschätzung nicht mehr.
Edit2: Unsinnige enumerates rausgenommen.