Warum funktioniert max() auf Listen mit Strings nicht ?

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.
Mad-Marty

Warum funktioniert max() auf Listen mit Strings nicht ?

Beitragvon Mad-Marty » Mittwoch 18. Januar 2006, 13:52

Hi,

kann mir jemand verraten, warum max() einfach nicht mit strings richtig funktioniert ?
Betrachtet max die strings von ihrem ASCII Zahlenwert ?

Bei dem unten gezeigten Beispiel sollte eigentlich 'xxxxxxxxx' als längster string angezeigt werden ....

Beispiel :

>>> liste =["havefun", "dfdfdf", "weissschh", 'xxxxxxxxxxx', 'zzzzzz', "blah blubber"]
>>> max (liste)
'zzzzzz'
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 14:18

Das was max() zurückliefert ist schon richtig, denn im Endeffekt ist "z">"x" nach lexikographischer Sortierung im ASCII-Zeichensatz, und so sind die Vergleiche auf Strings auch implementiert.

Was Du machen kannst um nach länge das Maximum zu kriegen:

Code: Alles auswählen

max([(len(x),x) for x in liste])[1]


Das funktioniert aber nur wenn in liste auch was drin ist.

Das ist eine typische Anwendung des Decorate-Sort-Undecorate Patterns.

--- Heiko.
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Beitragvon mawe » Mittwoch 18. Januar 2006, 14:45

Hi!

Seit Python 2.4 geht auch so etwas:

Code: Alles auswählen

string_max = sorted(liste, key=len)[-1]
string_min = sorted(liste, key=len)[0]


Gruß, mawe
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 14:53

Das hat aber im Gegensatz zu meiner Lösung Laufzeit O(n*log n) und nicht O(n)... ;-)

--- Heiko.
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Beitragvon mawe » Mittwoch 18. Januar 2006, 14:58

Tja, darüber hab ich mir keine Gedanken gemacht. Ich glaub Dir das mal ;) Nein doch nicht ... wie findet man das raus?
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 15:14

Du guckst von innen nach außen welche Laufzeit was hat.

Mein Beispiel:

Code: Alles auswählen

max([(len(x),x) for x in liste])[1]


1. In der List-Comprehension haben wir zuerst die Tupelerstellung O(1) = fixe Zeit, weil tupelerstellung fixe Zeit und len(x) auch fixe Zeit, da jedes String-Objekt die Länge als Feld hat. (nicht wie bei C-Strings, strlen(s) braucht O(slen), da es den Terminator suchen muß!*) Das ganze wird dann n-mal ausgeführt durch die Listcomprehension: n*O(1) = O(n) = Zeit direkt abhängig von n.

2. max läuft die Liste schrittweise ab und behält einfach einen Zeiger auf das Maximum. Der Vergleich kostet auch maximal fixe Zeit, also O(1), und wieder n*O(1) = O(n)

3. Der Zugriff auf das erste Element eines Tupels ist wieder O(1)

Wir brauchen als für das innere O(n) Zeit, für das äußere O(n) Zeit, für das undekorieren O(1), O(n) + O(n) + O(1) = O(n) , also O(n) Zeit für das ganze. Die Zeit die es braucht wächst also linear mit der Anzahl von Elementen in der Liste.

Dein Beispiel:

Code: Alles auswählen

string_max = sorted(liste, key=len)[-1]


1. Das Dekorieren mit dem Key spar ich mir jetzt mal, das ist genauso wie oben O(n) wo ich explizit dekoriert hab, weil sorted intern genau das macht: dekorieren.

2. Dann das sortieren, das braucht O(n*log^1.<irgendwas> n), abgekürzt von _mir_ (nicht ganz korrekt) immer geschrieben als O(n*log n), wächst also schneller als linear.

3. Das holen des letzten Elements braucht wieder O(1).

Wir haben also: O(n) + O(n*log n) + O(1) = O(n*log n), weil asymptotisch die Laufzeit sich an C*n*log n annähert weil es der Term ist der am schnellsten wächst (wobei C eine beliebige nach oben beschränkte Konstante ist).

Damit skaliert Deine Methode nicht so gut wie direkt max zu benutzen mit dekorierten Werten, weil es eben schneller als linear wächst.

Das sagt natürlich nichts darüber aus welche Methode auf der Länge die der OP will schneller ist, es ist nur ein Verhalten was die jeweilige Methode hat wenn n immer größer wird. Sprich: wenn man die Laufzeit in Relation zu n graphisch aufträgt und Deine Methode am Anfang schneller ist gibt es auf jeden Fall irgendwo einen Punkt wo der Graph den Graphen meiner Funktion schneidet, da dieser langsamer wächst. Wo dieser Punkt ist, darüber sagt das ganze was ich da gemacht hab gar nichts aus.

Der Punkt kann zum Beispiel auch bei n=1**10 sein, das würde bedeuten dass Deine Methode für alle praktischen Belange vorzuziehen ist, obwohl sie schlechteres Laufzeitverhalten hat. Das ist aber hier sicherlich nicht der Fall, und meine "gut-intuition" (wie übersetzt man das auf Deutsch?) sagt mir dass meine Methode immer die schnellere ist.

Hoffe das hilft.

--- Heiko.

* wobei man hier anmerken muß dass das wieder eine Frage ist ob es eine feste obere Grenze für die Stringlänge gibt (die es ja im Endeffekt immer gibt, da der Speicher des Computers nach oben limitiert ist). Wenn wir zum Beispiel annehmen dass die Strings alle der Länge nach kleiner als 1000 sind, ist auch die Laufzeit hierfür immer <= 1000, also wieder Laufzeit = O(1) <=> Laufzeit <= C*1 für C=1000. Wenn wir das nicht annehmen (also dass die Strings auch unendlich lang sein können), müßten wir das ganze etwas komplizierter werden lassen, wo ich jetzt keinen Bock drauf hab. ;-)
Mad-Marty

Beitragvon Mad-Marty » Mittwoch 18. Januar 2006, 19:16

modelnine hat geschrieben:Das was max() zurückliefert ist schon richtig, denn im Endeffekt ist "z">"x" nach lexikographischer Sortierung im ASCII-Zeichensatz, und so sind die Vergleiche auf Strings auch implementiert.

Was Du machen kannst um nach länge das Maximum zu kriegen:

Code: Alles auswählen

max([(len(x),x) for x in liste])[1]


Das funktioniert aber nur wenn in liste auch was drin ist.

Das ist eine typische Anwendung des Decorate-Sort-Undecorate Patterns.

--- Heiko.



Danke für die Hilfe an euch ...

Was ist das Decorate-Sort-Undecorate Pattern ? hör ich das erste mal.

Gibts eigentlich irgendwo eine darstellung von den wichtigen Patterns in Python , wie z.b. GoF ?
Ich weiss das nicht jedes Pattern sinn macht weil Python nicht statisch ist.

Meine Lösung war übrigens da da, funktioniert komischerweise aber nur in IDLE .. PythonWin ist der meinung das int uncallable ist ... ?!?!

Code: Alles auswählen

liste = [ "text", "someother", "evenmoretest", "end"]
buffer = []
for item in liste:
    buffer.append(len(item))
max = liste[buffer.index(max(buffer))]
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 19:32

Also... Deine Lösung ist so lala, auf jeden Fall alles andere als schnell, hat aber auch Laufzeit O(n) (so nebenbei als Information für mawe). ;-)

Aber jetzt zu Patterns. Ja, es gibt in Python eine ganze Menge Patterns, die aber bis auf DSU (decorate-sort-undecorate) eher informell sind.

Ein extrem gutes Buch um gute Patterns zu sehen (die eben nicht so strikt und religiös fest sind wie bei Java) ist das "Python Cookbook" von O'Reilly. Das sind kommentierte und erweiterte Rezepte von http://aspn.activestate.com/ASPN/Cookbook/Python. Ich hab eins umsonst zugeschickt bekommen weil ein Rezept von mir drin ist, für den Normalsterblichen ist es aber auch sehr erschwinglich. 500 Seiten wahre Python-Kunst, auch für 2.4.

Kann ich absolut nur empfehlen wenn Du Dich in die Python-Programmierung reinfinden willst.

--- Heiko.
Mad-Marty
User
Beiträge: 317
Registriert: Mittwoch 18. Januar 2006, 19:46

Beitragvon Mad-Marty » Mittwoch 18. Januar 2006, 20:02

Das habe ich schon, die 2005er Version

:D

Einzigstes problem was ich mit deiner Lösung habe :
Es nutzt List Comprehension. Die funktioniert leider mit Pyrex nicht.

(die sache mit dem längsten string finden ist teil einer Factory implementation, das ganze soll mittels pyrex zu einer .dll / .so compiliert werden)

Deins sieht auf alle fälle schöner aus.
Nur bin ich mir nicht im klaren warum meine Lösung langsamer sein soll ?

Du baust ein Tuple mit länge, Text
Dann lässt du dir das Tuple mit der grössen zahl per max geben.
dann greifst du auf index 1 zu.

Ich gehe jedes element meiner liste durch und notiere die länge im buffer.
Das len() wendest du auch auf jedes element an.

Evtl greifen da irgendwelche List-Comprehension internen optimierungen ?
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 20:07

Das buffer.index() ist extrem langsam und vor allen Dingen das einzige was unsere Lösungen unterscheidet, da es die Liste von Anfang an durchsuchen muß um das Element zu finden, also noch mal ein zusätzliches O(n) reinbringt.

Sonst: list-comprehensions sind marginal schneller als direkte loops, aber das macht eigentlich nix aus.

Du solltest wenn Du die List-Comprehension oben mit einer variable ausschreibst meine Lösung aber verbatim übernehmen können.

Ist nur die Frage ob Du das wirklich mit Pyrex machen willst; ein eigenes kleines C-Modul was dann wirklich Performance rausholt ist alles andere als schwer zu machen. Aber egal. ;-)

--- Heiko.
Mad-Marty
User
Beiträge: 317
Registriert: Mittwoch 18. Januar 2006, 19:46

Beitragvon Mad-Marty » Mittwoch 18. Januar 2006, 20:36

modelnine hat geschrieben:Das buffer.index() ist extrem langsam und vor allen Dingen das einzige was unsere Lösungen unterscheidet, da es die Liste von Anfang an durchsuchen muß um das Element zu finden, also noch mal ein zusätzliches O(n) reinbringt.

Sonst: list-comprehensions sind marginal schneller als direkte loops, aber das macht eigentlich nix aus.

Du solltest wenn Du die List-Comprehension oben mit einer variable ausschreibst meine Lösung aber verbatim übernehmen können.

Ist nur die Frage ob Du das wirklich mit Pyrex machen willst; ein eigenes kleines C-Modul was dann wirklich Performance rausholt ist alles andere als schwer zu machen. Aber egal. ;-)

--- Heiko.


Hi,

ja funktioniert! :)

Code: Alles auswählen

liste = ["some", "textstring", "evenmoretext", "muchmoretexthere", "shorttext"]
buffer = []
for item in liste:
    buffer.append((len(item), item))
max (buffer)[1]



Warum berücksichticht max () eigentlich nur die erste ebene (in dem fall die zahl) ?


Zum Thema Pyrex, es ist nicht wesentlich langsamer als C teilweise finde ich.
Nutzen möchte ich es weil ich Python liebe ... 8) ... und das ganze ist ja wesentlich mehr, das war nur ein kleines problem in der registry-based factory, die laut profiling bei 0,010 s rechenzeit liegt ...

Auserdem kann man eine erweiterung viel besser verteilen als 30 kleine py files ... und es kann niemand mehr was verfrickeln.

EDIT:
Und ich möchte C Schnittstellen für die armen leute anbieten die nicht Python nehmen wollen ;-)
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 21:07

Es vergleicht nicht nur das erste Element des Tupels.

Sondern, es wird genau wie bei Strings eine Art "lexikographischer" Vergleich der Tupel vorgenommen:

1. wenn a[0] > b[0] => a > b, a[0] < b[0] => a < b
2. a[0] = b[0], also wenn a[1] > b[1] => a > b, a[1] < b[1] => a < b
3. a[0,1] = b[0,1], also wenn a[2] > b[2] => a > b, a[2] < b[2] => a < b
4. a[0..2] = b[0..2], also wenn a[3] > b[3] => a > b, a[3] < b[3] => a < b
...

Das ist eine Eigenschaft von Tupeln die sich eben sehr schön für DSU eignet.

Ich dekoriere meinen Wert (mache ein Tupel draus mit einem neuen Wert am Anfang) mit der Eigenschaft die ich testen will, und dann sortiere ich die Liste, und lösche die Dekoratoren (??) wieder. Dadurch dass Tupel die oben genannte Logik beim Vergleich haben kriege ich automatisch eine Sortierung der Werte nach meinem Key, aber auch in zweiter Instanz nach dem Wert selbst.

Wenn ich mehr Keys zur Sortierung haben will dekoriere ich einfach mit allen von ihnen.

Das ist der DSU-Pattern.

Warum ich sag dass das ganze in C noch mal 'ne Stufe schneller werden könnte:

Im Prinzip verbringst Du "verschenkte" Zeit des Algorithmus damit die Werte zu dekorieren. Da es im Endeffekt nur darum geht Strings der Länge nach das Maximum zu finden braucht man eigentlich keine Dekoration wenn man das direkt in C implementiert (weil ich wenn ich ein String-Objekt habe als member der Objektstruktur die Länge kriegen kann), und hat somit nur einen Pass über den Iterator (und nicht zwei) und kann direkt die String-Compare-Funktion aufrufen, ohne dass man die allgemeineren Compare-Funktionen die dann die typspezifischen aufrufen bedienen müßte.

Das bedeutet aber dass man vorher wissen muß dass es um eine Liste von strings geht in der man der Länge nach das Maximum finden kann. Aber genau diese Applikation hast Du ja im Endeffekt jetzt auch.

Mich würde wundern wenn der Pyrex-Code viel schneller wäre als der selbe direkt in Python geschrieben, da er im Endeffekt genau die selbe "Allgemeinheit" zur Verfügung stellen muß wie das Python auch macht. Und eben auch dekoriert, genau die selbe Zeit die auch in Python "verschenkt" wird.

Also: wenn's wirklich um Geschwindigkeit geht: nicht in Pyrex, und nicht so.

--- Heiko.
Mad-Marty
User
Beiträge: 317
Registriert: Mittwoch 18. Januar 2006, 19:46

Beitragvon Mad-Marty » Mittwoch 18. Januar 2006, 21:27

Ok, super erklärung, danke.

Naja zumindest werden integer sachen ernorm schnell mit pyrex (schneller als mit psyco um faktor 5), dafür deklariert man diese aber auch entsprechend.


Nein, geht bei der factory absolut nicht um speed beim ident finden.
Da verbraucht das programm unter 0,01 % seiner rechenzeit bzw nur wenige bruchteile von einer sekunde.

Ist also völlig unerheblich da das auch nur einmal aufgerufen wird.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Beitragvon modelnine » Mittwoch 18. Januar 2006, 21:35

Ist also völlig unerheblich da das auch nur einmal aufgerufen wird.


Nur versteh ich dann nicht warum Du das ganze überhaupt mittels Pyrex implementierst... Pyrex ist nicht dafür gedacht "performanceunkritische" Dinge vor dem Benutzer zu verstecken, sondern um wichtige und vor allen Dingen performancekritische Dinge in einer Art C zu implementieren...

Aber, egal. :-)

--- Heiko.
BlackJack

Beitragvon BlackJack » Mittwoch 18. Januar 2006, 22:49

Mad-Marty hat geschrieben:Meine Lösung war übrigens da da, funktioniert komischerweise aber nur in IDLE .. PythonWin ist der meinung das int uncallable ist ... ?!?!

Code: Alles auswählen

liste = [ "text", "someother", "evenmoretest", "end"]
buffer = []
for item in liste:
    buffer.append(len(item))
max = liste[buffer.index(max(buffer))]


Kann es sein, dass Du bei PythonWin diesen Quelltext zweimal hintereinander ausprobiert hast und das die Namen jeweils erhalten bleiben? Am Ende bindest Du `max` nämlich an eine ganze Zahl und verdeckst damit die `max()` Funktion.

Wer ist online?

Mitglieder in diesem Forum: martinjo