Hallo zusammen, ich bin irgendwie nicht zufrieden... Ich würde gerne aus einer Liste: z.b. 1,2,3,5,7,8,9,11 einen String generieren, wobei fortlaufende Reihen zusammengefasst werden. -> "1-3,5,7-9,11" hier mein kläglicher Vesuch... irgendwie habe ich das Gefühl: Das muss einfacher gehen ? Vielleicht hat ja jemand Lust auf diese kleine morgendliche Denksportaufgabe... Vielen Dank Grüße Frank #!/usr/local/bin/python l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() r="" mylist=[] for c in xrange(len(l)-1): mylist.append(l[c]) if l[c]+1 == l[c+1]:continue if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," mylist=[] mylist.append(l[len(l)-1]) if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," print r -- +++ Jetzt WLAN-Router für alle DSL-Einsteiger und Wechsler +++ GMX DSL-Powertarife zudem 3 Monate gratis* http://www.gmx.net/dsl _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Frank Immich schrieb:
Denksportaufgaben sind immer eine Herausforderung ;-) Ob das folgende einfacher ist, weiss ich auch nicht. Aber ich finde es übersichtlicher. (Ausserdem wollte ich schon immer mal Generatoren ausprobieren. Und das scheint mir ein guten Anwendungsfall zu sein. Mit filter,reduce und co. kommt man nicht so richtig weiter, weil man sich den letzten Zustand/Ausgabe irgendwie merken muss.) MfG Rene # fuer Python 2.2 from __future__ import generators def x(data): minus=0 last=data[0] # erstes ausgeben yield data[0] for i in data[1:]: # wenn das ein Nachfolger ist if i-1 == last: # minus ist schon mal ausgegeben? if minus: pass else: # dann eben jetzt erstmal yield '-' minus=1 last = i else: # kein Nachfolger # also x-y abschliessen, y ausgeben if minus: yield last minus =0 # trennkomma ausgeben yield ',' # Neues Element ausgeben yield i last = i # da fehlt der abschluss noch if minus: yield last import string print string.join( # die Zahlen muessen noch Strings werden map(str, x([3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] ) ),"") _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
René Liebscher schrieb:
Da muss ich mich selber korrigieren, man kann ja in reduce auch die bereits gebaute Liste als Zustandsspeicher missbrauchen. Das sieht dann so aus. (Ist sogar noch kuerzer als die andere Variante. Wie das von der Laufzeit bei sehr grossen Eingabelisten aussieht, ist eine andere Sache, weil je für jedes Element eine neue Liste angelegt wird.) def y(list,element): if len(list) == 0: return [element] # Nachfolger von letzem in der liste if list[-1] == element-1: # liste erst angefangen oder irgendwas wie '... , x' drin if len(list)<2 or list[-2]==',': # anhaengen return list+['-',element] else: # letztes Element in Liste austauschen return list[:-1]+[element] else: # neues anhaengen return list+[',',element] print string.join( # die Zahlen muessen noch Strings werden map(str, reduce(y,[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47],[]) ),"") _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, On Fri, 18 Jun 2004 10:54:39 +0200, René Liebscher <R.Liebscher@gmx.de> wrote:
Wie das von der Laufzeit bei sehr grossen Eingabelisten aussieht, ist
habe Deine Laufzeit-Anmerkung mal zum Anlass genommen, einige der geposteten Varianten zu messen. Hier die Messung für 30000 Zahlen: Anzahl 30000 Laufzeit (Frank): 7.6432 sec Laufzeit (kgm): 3.1479 sec Laufzeit (Jan): 6.8867 sec Laufzeit (Rene): 122.2487 sec Jan Lösungen mit der re-Engine (die ich ganz interessant fand, da ich vermutlich nicht auf diese Idee gekommen wäre) hat den Effekt, bei manchen großen Listen mit "recursion limit" rauszufliegen! Hat mich etwas gewundert. Traceback (most recent call last): File "C:\Test\liste-laufzeit.py", line 22, in ? r = re.sub(r"-(\d+-)+","-",r) File "C:\Programme\Python\lib\sre.py", line 143, in sub return _compile(pattern, 0).sub(repl, string, count) RuntimeError: maximum recursion limit exceeded Hier die Source für eigene Tests: #Laufzeit-Test import time, random, re, string anzahl = 10000 #Anzahl der Zahleneintraege in Liste #Zufallsliste ohne Wiederholung random.seed(7) l = range( 2*anzahl ) l = random.sample(xrange(2*anzahl), anzahl) l.sort() print "Anzahl", anzahl #print l #Frank Immich starttime = time.clock() r="" mylist=[] for c in xrange(len(l)-1): mylist.append(l[c]) if l[c]+1 == l[c+1]:continue if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," mylist=[] mylist.append(l[len(l)-1]) if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," #print r print "Laufzeit (Frank): %3.4f sec" % (time.clock() - starttime) # kgm starttime = time.clock() l.append(l[-1]+2); r="" start = l[0] last = start for v in l: if v-last > 1: r += str(start) if last != start: r += "-" + str(last) r += "," start = v last = v del l[-1] #append wieder aufheben r = r[0:-1] #letzte Komma weg #print r print "Laufzeit (kgm): %3.4f sec" % (time.clock() - starttime) # Jan Voges starttime = time.clock() r="" for i in xrange(len(l)-1): if l[i+1] - l[i] == 1: r += str(l[i])+"-" else: r += str(l[i])+"," r += str(l[-1]) #print r r = re.sub(r"-(\d+-)+","-",r) #print r print "Laufzeit (Jan): %3.4f sec" % (time.clock() - starttime) #Rene Liebscher starttime = time.clock() def y(list,element): if len(list) == 0: return [element] # Nachfolger von letzem in der liste if list[-1] == element-1: # liste erst angefangen oder irgendwas wie '... , x' drin if len(list)<2 or list[-2]==',': # anhaengen return list+['-',element] else: # letztes Element in Liste austauschen return list[:-1]+[element] else: # neues anhaengen return list+[',',element] r = string.join( # die Zahlen muessen noch Strings werden map(str, reduce(y,l,[]) ),"") #print r print "Laufzeit (Rene): %3.4f sec" % (time.clock() - starttime) #ende -- Mit freundlichen Grüßen Klaus Meyer :-) _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo! On 18 Jun 2004 at 13:50, kgm wrote:
Oops, auf Performanz hab' ich nun gar nicht achtet. Die String-Concatinations sind natürlich schweineteuer. Deutlich besser: # Jan Voges starttime = time.clock() liste = [] for i in xrange(len(l)-1): liste.append(str(l[i])) if l[i+1] - l[i] == 1: liste.append("-") else: liste.append(",") liste.append(str(l[-1])) r = "".join(liste) #print r r = re.sub(r"-(\d+-)+","-",r) #print r print "Laufzeit (Jan): %3.4f sec" % (time.clock() - starttime) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 18.06.2004 14:07:42 schrieb Jan Voges:
Oops, auf Performanz hab' ich nun gar nicht achtet. Die String-Concatinations sind natürlich schweineteuer.
Huch :) Hab meine Loesung ebenfalls angepasst: zustand = 1 c = 0 res_liste = [] ret_liste.append('%d' % l[c]) for c in range(1,len(l)): if zustand == 1: if l[c] != liste[c-1]+1: res_liste.append(',%d' % l[c]) else: zustand = 2 elif zustand == 2: if l[c] != l[c-1]+1: zustand = 1 res_liste.append('-%d,%d' % (l[c-1], l[c])) result = ''.join(res_liste) und komme auf folgende Ergebnisse: Anzahl 40000 Laufzeit (Frank): 5.0987 sec Laufzeit (kgm): 2.8702 sec Laufzeit (Jan): 5.0814 sec Laufzeit (Jan_opt): 0.1492 sec Laufzeit (Rene): 64.5952 sec Laufzeit (boesi): 2.2832 sec Laufzeit (boesi_opt): 0.1037 sec Die beiden schnellsten nochmal im direkten Vergleich: Anzahl 1000000 Laufzeit (Jan_opt): 4.1980 sec Laufzeit (boesi_opt): 2.8218 sec cu boesi -- <seasons82> was ist rl? #1671 : icq-intern <seasons82> und muss man das wissen? #73628288 : icq-extern ...der moment wo einem klar wird, boesi111 : aim dass man zuviel chattet... i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Versuch mal die Lösung: def _ranges(s): if s: s.append (s[-1] + 2) ### sentinel to avoid cleanup after loop r = [s[0]] for v in s[1:]: d = v - r[-1] if d > 1: if len(r) > 2: yield "%s-%s" % (r[0], r[-1]) else: for u in r: yield str(u) r = [v] elif d == 1: r.append(v) def collapsed_ranges(seq): s = list(seq) s.sort() return list(_ranges(s)) -- Christian Tanzer http://www.c-tanzer.at/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, Alexander 'boesi' Bösecke wrote:
Jezt machst Du noch * '%d' % l[c] -> str(lc[0]) * weg mit den ständigen Index-Zugriffen * for num in l, statt über den range Und du solltest Sieger sein :-)
cu boesi
-- Schönen Gruß - Regards Hartmut Goebel | Hartmut Goebel | IT-Security -- effizient | | h.goebel@goebel-consult.de | www.goebel-consult.de | _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Es läßt einem ja doch keine Ruhe ... Wie man's auch anstellt, die Laufzeit hängt (jedenfalls unter den angenommenen Bedingungen) vor allem von der Anzahl der Hinzufügungen ab, sei es ergebnis+=str(wert) oder ergebnis.append(str(wert)); alle anderen Optimierungen fallen dagegen kaum ins Gewicht. Also versuche ich in dieser Richtung etwas zu "schummeln": l = [3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] # l.sort() res = [] last = None inrange = False comma = "" for i in l: if i - 1 != last: closing = inrange and "-" + str(last) or "" res.extend((closing, comma, str(i))) inrange = False comma = "," else: inrange = True last = i if inrange: res.extend(("-", str(last))) result = "".join(res) Und siehe da, vor allem das extend zahlt sich aus ;-) : $ ./bench.py n = 100000 boesi: 155.6 µs / Durchlauf 3,5-12,22-26,32,34,36,38-41,44-45,47 det: 139.7 µs / Durchlauf 3,5-12,22-26,32,34,36,38-41,44-45,47 $ Mit cStringIO erhielt ich übrigens auch keine besseren Werte. Zwar ist res = cStringIO.StringIO() ... print >>res, "-", last usw. schneller (die Function Calls, z.B. bei res.write(str(...)), sind teuer!), aber das produziert zusätzliche Blanks, die hier unerwünscht wären. Detlef _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 18.06.2004 19:19:09 schrieb Detlef Lannert:
Und siehe da, vor allem das extend zahlt sich aus ;-) :
Dank den Anregungen von Hartmut hab ich meine Lösung nochmal angepasst, sieht jetzt so aus: zustand = 1 last = liste.pop(0) resListe = [str(last)] for element in liste: if zustand == 1: if element != last+1: resListe.extend((',', str(element))) else: zustand = 2 elif zustand == 2: if element != last+1: zustand = 1 resListe.extend(('-', str(last), ',', str(element))) last = element # wenn die letzten Elemente der Liste zusammengefasst werden müssen, # müßen diese noch angehängt werden if liste[-2] == last-1: resListe.extend(('-', str(liste[-1]))) return ''.join(resListe) Die Entfernung der ganzen Indexzugriffe hat am meisten gebracht. Meßergebnisse: Hab mir mal den Spaß gemacht und alle (optimierten) Lösungen verglichen. Die jeweils langsamsten hab ich beim naechsten Durchlauf weggelassen. Anzahl: 10000 Laufzeit (Frank): 0.1927 sec Laufzeit (kgm): 0.0994 sec Laufzeit (Jan): 0.0370 sec Laufzeit (Rene_y2): 0.0323 sec Laufzeit (Rene_x): 0.0249 sec Laufzeit (boesi): 0.0216 sec Laufzeit (Christian): 0.0301 sec Laufzeit (Gregor): 0.0235 sec Laufzeit (Detlef): 0.0228 sec Laufzeit (Thorsten): 15.8565 sec Laufzeit (Jochen): 0.4025 sec Anzahl: 40000 Laufzeit (Frank): 5.7550 sec Laufzeit (kgm): 3.2524 sec Laufzeit (Jan): 0.1623 sec Laufzeit (Rene_y2): 0.1374 sec Laufzeit (Rene_x): 0.1043 sec Laufzeit (boesi): 0.0892 sec Laufzeit (Christian): 0.1227 sec Laufzeit (Gregor): 0.0971 sec Laufzeit (Detlef): 0.0987 sec Laufzeit (Jochen): 13.1420 sec Anzahl: 1000000 Laufzeit (Jan): 4.2928 sec Laufzeit (Rene_y2): 3.6483 sec Laufzeit (Rene_x): 2.7883 sec Laufzeit (boesi): 2.4917 sec Laufzeit (Christian): 3.2152 sec Laufzeit (Gregor): 2.6467 sec Laufzeit (Detlef): 2.5715 sec Mit Anzahl ist übrigens die Listengröße gemeint, der Code zum erzeugen der Zufallsliste wurde von kgm gepostet. Wenn jemand die Messungen selber durchführen oder anpassen will, hab die Datei hierhin gepackt: http://www.stud.tu-ilmenau.de/~boesi/temp/BenchListe.py cu boesi PS: ein Algorithmus mit der Laufzeit O(1) waere nett ;) -- --==SECURITY ALERT==-- #1671 : icq-intern Your Computer Is Currently Broadcasting An #73628288 : icq-extern Internet IP Address. With This Address, boesi111 : aim Someone Can Begin Attacking Your Computer. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, Alexander 'boesi' Bösecke wrote:
Dank den Anregungen von Hartmut hab ich meine Lösung nochmal angepasst,
:-) Und es geht noch schneller: Nachdem es nur die Zustände 1 und 2 gibt, kann man diese elif zustand == 2: ändern in else: Wenn Du dazu noch die Zustände 0 und 1 nimmst, genügt hier if zustand == 1: ein if zustand: Und wieder zwei Bytecode-Instruktionen gespart :-) -- Schönen Gruß - Regards Hartmut Goebel | Hartmut Goebel | IT-Security -- effizient | | h.goebel@goebel-consult.de | www.goebel-consult.de | _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 21.06.2004 12:26:21 schrieb Hartmut Goebel:
Und wieder zwei Bytecode-Instruktionen gespart :-)
Und es geht noch schneller :) Wenn man statt str(element) `element` verwendet. Und interessanterweise ist resListe.append('-' + `last` + ',' + `element`) ebenfalls schneller als resListe.extend(('-', `last`, ',', `element`)) Das letzte ist dann aber fast schon Erbsenzaehlerei. append und extend im Vergleich: Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt (boesi): 2.1438 sec Laufzeit pro Loop im Schnitt (boesi_app): 2.0951 sec Die neue Version der Datei liegt wieder unter der bereits angegebenen URL. cu boesi -- #1671 : icq-intern ...schlafen ist sowieso ungesund... #73628288 : icq-extern .-==Police Academy I==-. boesi111 : aim i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
--On Montag, 21. Juni 2004 13:21 Uhr +0200 Alexander 'boesi' Bösecke <boesi.josi@gmx.net> wrote:
Wer solchen Code (wegen ein bischen Erbsenzählerei) produziert gehört mit drei Perlbüchern gehauen :-) -aj _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 21.06.2004 14:02:30 schrieb Andreas Jung:
Ohje merkt man mir meine schaendliche Perlvergangenheit so schlimm an? *gg* Am "schoensten" ist es sicher, wenn man den Ausgabestring direkt zusammenbaut, aber wir haben ja bereits gelernt, dass Python in diesem Bereich a****lahm ist und man deswegen zB den Umweg ueber eine Liste geht. Und welche Variante man da dann am "schoensten" findet, ist in meinen Augen hauptsaechlich eine Sache der Gewohnheit. -------- Am 21.06.2004 16:31:53 schrieb Christian Tismer:
Aehm noe also eigentlich bin ich ganz spontan davon ausgegangen, dass das Erzeugen eines Tupel schneller geht als das einer Liste. Warum kann ich nicht sagen und auch nicht ob das stimmt, aber... Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 2.0425 sec (resListe.append('-' + `last` + ',' + `element`)) boesi2 : 2.1516 sec (resListe.extend(('-', `last`, ',',`element`))) boesi3 : 2.3793 sec (resListe.append('-%d,%d' % (last, element))) boesi4 : 2.3118 sec (resListe.extend(['-', `last`, ',', `element`])) cu boesi -- #1671 : icq-intern <THammY-> und meine hände ham bisher immer #73628288 : icq-extern nur das gemacht was ich will </THammY> boesi111 : aim i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Das ist allerdings erstaunlich und unerwartet. Ich hatte vermutet, daß das Tupel zunächst in eine Liste gewandelt würde, die dann zum Extend benutzt wird. Aber offensichtlich wird das Sequence-Protokoll direkt benutzt, und in der Tat sind Tupel schneller erstellt, insbesondere, weil sie einen eigenen Objekt-Cache haben und Du in diesem Fall immer wieder daselbbe Objekt bekommst. Die Idee mit repr als "`" geschrieben scheint gut, spart Opcodes. boesi3 : 2.3793 sec (resListe.append('-%d,%d' % (last, element))) Hier kommen wohl die Extra-Kosten für das Formatier-Tupel hinzu. boesi3 : 2.3793 sec (resListe.append('-%d,%d' % (last, element))) Probierbar wäre .append('-%d,%%d' % last % element) wobei ich vermute, es ist nicht viel besser. Das Tupel wird gespart, dafür wird zweimal formatiert. Aaaber eine Sache kannst Du evtl. noch machen. Die erwünschte Schreibweise impliziert doch, daß die Liste keine negativen Zahlen enthalten kann? Also kommt auch kein "bis 0" vor. Dann ist es evtl. billiger, eine positive Zahl negativ zu machen: resListe.append(`-last` + ',' + `element`) Interessant, ciao - chris -- Christian Tismer :^) <mailto:tismer@stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 11:23:38 schrieb Christian Tismer:
Aha. Schoen zu wissen, dass Tupel doch noch Vorteile gegenueber Listen bieten. :)
Die Idee mit repr als "`" geschrieben scheint gut, spart Opcodes.
Ist auch nur von http://www.skymind.com/~ocrow/python_string/ geklaut.
Ist denn auch die langsamste Variante.
Ich war implizit davon ausgegangen, dass negative Zahlen vorkommen koennen, aber eigentlich hast du recht und ein klein wenig bringt auch das noch. Gersons Idee, statt dem append gleich mit Listindices zu arbeiten, bringt auch nochmal rund 10%, so dass nun zwischen der langsamsten und der schnellsten Version runde 70% liegen. Ist doch ganz ordentlich fuer ein bisschen Spielerei :) @Gerson: es ist nicht grad die feine Art, einbuchstabige Variablennamen zu verwenden. Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi1 : 2.4279 sec (resListe.append('-%d,%d' % (last, element))) boesi2 : 2.5484 sec (resListe.append('-%d,%%d' % last % element)) boesi3 : 2.0967 sec (resListe.append('-' + `last` + ',' + `element`)) boesi4 : 2.3170 sec (resListe.extend(['-', `last`, ',', `element`])) boesi5 : 2.1064 sec (resListe.extend(('-', `last`, ',', `element`))) boesi6 : 1.8772 sec (resListe[k] = '-' + `last` + ',' + `element`) boesi7 : 1.7992 sec (resListe[k] = `-last` + ',' + `element`) cu boesi -- #1671 : icq-intern Frueher hattet ihr die Freiheit zu entscheiden #73628288 : icq-extern Heute seid ihr von dieser Entscheidung befreit boesi111 : aim .-==Report der Magd==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Stimmt, und deshalb habe ich meine Variante mit dem Generator auch noch mal angepasst. Das läuft dann mehr als doppelt so schnell, wenn man die map/str Kombination weglässt und die Konversion in Strings schon in der Funktion ausführt. Anzahl 300000 Laufzeit (Rene,y2): 3.0700 sec # mit reduce Laufzeit (Rene,x): 2.6200 sec # mit Generator und map/str Laufzeit (Rene,x2): 1.1600 sec # mit Generator und `` Damit dürfte ich wieder an Peter's Zeiten dran sein ;-) MfG Rene ################################## def x2(data): minus=0 last=data[0] # erstes ausgeben yield `data[0]` for i in data[1:]: # wenn das ein Nachfolger ist if i-1 == last: # minus ist schon mal ausgegeben? if minus: pass else: # dann eben jetzt erstmal yield '-' minus=1 last = i else: # kein Nachfolger # also x-y abschliessen, y ausgeben if minus: yield `last` minus =0 # trennkomma ausgeben yield ',' # Neues Element ausgeben yield `i` last = i # da fehlt der abschluss noch if minus: yield `last` r = string.join(x2(l),"") ################################### _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Stimmt, und deshalb habe ich meine Variante mit dem Generator auch noch mal angepasst.
Mein Gott, was habe ich nur ausgelöst! Kommt jetzt auch noch je eine Version mit C und mit ASM-Einschub? ;-) Freundliche Grüße Klaus _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 21.06.2004 15:13:59 schrieb René Liebscher: Was zum Teufel hat GMX veranlasst deine Mail als Spam anzusehen?
Kann ich leider gar nicht bestaetigen. Anzahl Listenelemente: 10000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.0169 sec (Alexander B÷secke) Peter3 : 0.0130 sec (Peter Otten - schnell optimiert) Rene_x2 : 0.0162 sec (Rene Liebscher mit Generator und ``) Rene_x : 0.0250 sec (Rene Liebscher mit Generator und map/str) Anzahl Listenelemente: 100000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.1750 sec (Alexander B÷secke) Peter3 : 0.1381 sec (Peter Otten - schnell optimiert) Rene_x2 : 0.2196 sec (Rene Liebscher mit Generator und ``) Rene_x : 0.2613 sec (Rene Liebscher mit Generator und map/str) Anzahl Listenelemente: 300000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.5916 sec (Alexander B÷secke) Peter3 : 0.5711 sec (Peter Otten - schnell optimiert) Rene_x2 : 1.5888 sec (Rene Liebscher mit Generator und ``) Rene_x : 0.8867 sec (Rene Liebscher mit Generator und map/str) Also irgendwas laeuft da schief, den Versuch mit n=1000000 musste ich ganz abbrechen. Mit Generatoren hab ich mich leider noch gar nicht beschaeftigt, weswegen mir die Ursache absolut verborgen bleibt. Aber...
Was das soll, musst du mir mal erklaeren, warum machst du nicht einfach: if not minus: yield '-' minus=1 cu boesi -- #1671 : icq-intern Ohne Dich waeren die Gefuehle von heute #73628288 : icq-extern nur die leere Huelle der Gefuehle von damals boesi111 : aim .-==Die fabelhafte Welt der Amelie==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Aber vermutlich hast Du hier unabsichtlich ein Tupel kreiert, was zu einer Liste konvertiert werden muß. Keine Zeit zum testen, aber wie benimmt sich resListe.extend(['-', `last`, ',', `element`]) ? -- chris -- Christian Tismer :^) <mailto:tismer@stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo! On 21 Jun 2004 at 11:32, Alexander 'boesi' Bösecke wrote:
Dank für die Mühe! Also Perl-Geschädigter hätte ich noch einen Einzeiler anzubieten. def Jan2(l): """Jans Einzeiler""" return str(l[0]) + "," + "".join( [str(z)+(",","-")[l[i+2]-z==1] for i,z in enumerate(l[1:-1]) if l[i+2]-l[i]!=2] ) + str(l[-1]) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
On 21 Jun 2004 at 13:25, Jan Voges wrote:
Also Perl-Geschädigter hätte ich noch einen Einzeiler anzubieten.
Funktioniert leider nicht, also nicht beachten. Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
On 21 Jun 2004 at 13:42, Jan Voges wrote:
Funktioniert leider nicht, also nicht beachten. Jan
Jetzt aber ;-) def Jan2(l): """Jan' Einzeiler""" return "".join( [str(z)+(",","-")[l[i+1]-z==1] for i,z in enumerate(l[:-1]) if l[i+1]-l[i-1]!=2] ) + str(l[-1]) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Hab mir mal den Spaß gemacht und alle (optimierten) Lösungen verglichen. Die jeweils langsamsten hab ich beim naechsten Durchlauf weggelassen.
Hier zwei weitere Kandidaten für dein Testskript, Peter_schnell() und Peter_sauber(). Die schnellere Variante enthält den Stringkonvertierungscode "inline", der bei der sauberen Lösung in eine eigene Funktion chunk() ausgelagert ist. Peter_sauber() benötigt itertools.starmap(), funktioniert in dieser Form also erst ab Python 2.3. <BenchListe.py-Fragment> from itertools import starmap def chunk(s, t): if s == t: return "%s" % s else: return "%s-%s" % (s, t) def series(seq): it = iter(seq) first = prev = it.next() for item in it: if item - prev > 1: yield first, prev first = prev = item else: prev = item yield first, prev def Peter_sauber(sample): return ",".join(starmap(chunk, series(sample))) def inlineSeries(seq): it = iter(seq) first = prev = it.next() for item in it: if item - prev > 1: if first == prev: yield "%s" % first else: yield "%s-%s" % (first, prev) first = prev = item else: prev = item if first == prev: yield "%s" % first else: yield "%s-%s" % (first, prev) def Peter_schnell(sample): return ",".join(inlineSeries(sample)) funcListe = [Jan, Rene_y2, Rene_x, boesi, Christian, Gregor, Detlef, Peter_sauber, Peter_schnell] </BenchListe.py-Fragment> Ich habe festgestellt, dass bei der Messung die zuerst getestete Funktion etwas benachteiligt wird - hänge also bitte meine Funktionen ans Ende von funcListe :-) Um das Vertrauen in die präsentierten Algorithmen zu erhöhen, habe ich einen unittest geschrieben - nicht schön, aber leicht erweiterbar. Einige Lösungen bestehen nicht alle Tests. Damit das Testskript funktioniert, muss funcListe aus dem __main__-Block herausgenommen, d. h. in eine globale Variable umgewandelt werden. <test_BenchListe.py> import unittest import BenchListe for f in BenchListe.funcListe: class U(unittest.TestCase): def testEmpty(self, f=f): self.assertEqual(f([]), "") def testSingle(self, f=f): self.assertEqual(f([1]), "1") self.assertEqual(f([1,2]), "1-2") self.assertEqual(f([1,2,3]), "1-3") def testMulti(self, f=f): self.assertEqual(f([1,5,6,7,9]), "1,5-7,9") self.assertEqual(f([1,2,3,6,7,8,10,11,12]), "1-3,6-8,10-12") exec "U.__name__=%r\n%s = U" % (f.__name__, f.__name__) del U if __name__ == "__main__": unittest.main() </test_BenchListe.py> Hier die Zeiten auf meinem Rechner: Anzahl: 400000 Laufzeit (Jan): 1.6000 sec Laufzeit (Rene_y2): 1.4400 sec Laufzeit (Rene_x): 1.0800 sec Laufzeit (boesi): 0.8100 sec Laufzeit (Christian): 1.1500 sec Laufzeit (Gregor): 0.9200 sec Laufzeit (Detlef): 0.8300 sec Laufzeit (Peter_sauber): 0.6100 sec Laufzeit (Peter_schnell): 0.4900 sec Weiter viel Spaß beim Optimieren, Peter _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Das Packet liegt jetzt unter http://www.stud.tu-ilmenau.de/~boesi/temp/Bench.zip Die Algorithmen hab ich in AlgoListe.py ausgelagert, der Test wird mit Bench.py gestartet, die Unittests befinden sich in testBenchListe.py. Die Funktion benchFunc kann zum testen der Laufzeit beliebiger Funktionen genutzt werden. Als Parameter nimmt sie die Anzahl der Runden, die zu testende Funktion und eventuelle Parameter fuer die Funktion. Rueckgabewerte sind die Zeit fuer alle Runden (also kein Durchschnitt) und das Ergebnis der letzten Runde. Am 21.06.2004 13:56:37 schrieb Peter Otten:
Hier zwei weitere Kandidaten für dein Testskript, Peter_schnell() und Peter_sauber().
Sind genau wie die Funktion von Gerson in AlgoListe aufgenommen.
Das sollte sich nun erledigt haben...
Das liegt aber hautpsaechlich an der etwas ungenauen Spezifikation. So hat ein derartiger Algorithmus nur bei n>1 Sinn. Ausserdem ist nicht festgelegt was zB mit der Liste [1,3,4,6] passieren soll, soll 3,4 zusammengefasst werden oder nicht?
Hier die Zeiten auf meinem Rechner:
Bei deinen Algorithmen ist mir aufgefallen, dass sie bei größerem n gegebenueber anderen Algorithmen langsamer werden. Bei kleinem n aber ist besonders die schnelle Variante bisher ungeschlagen :) Anzahl Listenelemente: 100000 Anzahl Loops: 10 Laufzeit pro Loop im Schnitt: Jan : 0.3910 sec (Jan Voges) Jan2 : 0.2944 sec (Jan' Einzeiler) Rene_y2 : 0.3447 sec (Rene Liebscher mit reduce) Rene_x : 0.2541 sec (Rene Liebscher mit Generator) boesi : 0.1942 sec (Alexander B÷secke) Christian : 0.3086 sec (Christian Tanzer) Detlef : 0.2357 sec (Detlef Lannert) Gregor : 0.2474 sec (Gregor Lingl) Peter : 0.1916 sec (Peter Otten - sauber) Peter2 : 0.1570 sec (Peter Otten - schnell) Gerson : 0.1813 sec (Gerson Kurz) Anzahl Listenelemente: 1000000 Anzahl Loops: 10 Laufzeit pro Loop im Schnitt: Jan : 4.0364 sec (Jan Voges) Jan2 : 3.0187 sec (Jan' Einzeiler) Rene_y2 : 3.6156 sec (Rene Liebscher mit reduce) Rene_x : 2.7027 sec (Rene Liebscher mit Generator) boesi : 2.1021 sec (Alexander B÷secke) Christian : 3.2338 sec (Christian Tanzer) Detlef : 2.5933 sec (Detlef Lannert) Gregor : 2.6628 sec (Gregor Lingl) Peter : 3.1593 sec (Peter Otten - sauber) Peter2 : 2.7808 sec (Peter Otten - schnell) Gerson : 1.9040 sec (Gerson Kurz) cu boesi -- #1671 : icq-intern Ohne Dich waeren die Gefuehle von heute #73628288 : icq-extern nur die leere Huelle der Gefuehle von damals boesi111 : aim .-==Die fabelhafte Welt der Amelie==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Stimmt. Deshalb habe ich die "Konkurrenz" auch nicht fehlerhaft genannt, sondern eine neutrale Formulierung gewählt.
hat ein derartiger Algorithmus nur bei n>1 Sinn. Ausserdem ist nicht
Meine Vorlieben ergeben sich aus der sauberen Variante vor der Umwandlung in Strings. Ich halte list(series([])) == [] und list(series([1])) == [(1,1)] hier durchaus für sinnvoll - im Gegensatz zum Beispiel zu max([]). Wer anderer Meinung ist, sollte aber zumindest einen ValueError auslösen (in einem "echten" Programm, für den Benchmark ist das nicht sooo wichtig).
festgelegt was zB mit der Liste [1,3,4,6] passieren soll, soll 3,4 zusammengefasst werden oder nicht?
Ich halte "1,3-4,7" für besser lesbar als "1,3,4,7", weil 3 und 4 so leichter als benachbart erkennbar sind - aber das ist wiederum mehr Meinung als Tatsache oder gar Spezifikation. Fazit: eine Testsuite ist eine feine Sache, um kleinere Zweifelsfälle auszuräumen.
Vielleicht mache ich später noch ein t(N)-Diagramm, zunächst die Zeiten für deine aktuelle Version auf meinem Rechner. Anzahl Listenelemente: 1000000 Anzahl Loops: 10 Laufzeit pro Loop im Schnitt: Jan : 3.9890 sec (Jan Voges) Jan2 : 2.7010 sec (Jan' Einzeiler) Rene_y2 : 3.5420 sec (Rene Liebscher mit reduce) Rene_x : 2.5930 sec (Rene Liebscher mit Generator) boesi : 1.5670 sec (Alexander Bösecke) Christian : 2.9200 sec (Christian Tanzer) Detlef : 2.0510 sec (Detlef Lannert) Gregor : 2.3210 sec (Gregor Lingl) Peter : 1.4610 sec (Peter Otten - sauber) Peter2 : 1.1650 sec (Peter Otten - schnell) Gerson : 1.5090 sec (Gerson Kurz) Eine alternative Messung mit timeit.py $ timeit.py -s"import Bench as b" -s"s=b.erzListe(1000000)" "b.Peter2(s)" 10 loops, best of 3: 1.28e+06 usec per loop $ timeit.py -s"import Bench as b" -s"s=b.erzListe(1000000)" "b.Gerson(s)" 10 loops, best of 3: 1.55e+06 usec per loop bringt auch keine weiteren Erkenntnisse, außer dass der Lüfter nur bei Gerson() anläuft :-) Auf den ersten Blick kann ich nicht erkennen, dass mein Algorithmus schlecht skaliert - was ich auf Grund des Pythoncodes auch nicht erwartet habe. Ein zu kleiner Hauptspeicher scheidet als Ursache für die schlechteren Zeiten auf deinem Rechner wohl aus - ich habe nur 256MB und ausserdem benötigt Gerson() vermutlich mehr Speicher als Peter2(). Peter _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 12:14:45 schrieb Peter Otten:
Fazit: eine Testsuite ist eine feine Sache, um kleinere Zweifelsfälle auszuräumen.
Fazit2: eine TestSuite ist eine feine Sache, wenn die Testfälle streng nach der Spezifikation erstellt werden koennen, ohne das dabei irgendwelche Annahmen gemacht werden muessen
Eine alternative Messung mit timeit.py
Warum sacht mir denn keener, dasses den Scheiss schon gibt? *g*
Hmm und wo liegt dann die Ursache, dass deine Algorithmen auf meinem Rechner relativ stark einbrechen? Auch wenn die Meßergebnisse nur grobe Anhaltspunkte sind, so geben sie doch eine Tendenz an und sind zudem reproduzierbar. Aus deinem Prompt schließe ich, dass du ein unixiodes System verwendest, ich nutze WinXP - sollte hier das Problem liegen? Zuerst dachte ich, dass die Implementierung der Generator-Funktion unter Windows nicht so performant ist wie auf Unix-Systemen. Dem widerspricht aber Rene_x, denn der zeigt dieses Verhalten nicht. Anzahl Listenelemente: 10000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.0165 sec (Alexander B÷secke) Peter : 0.0191 sec (Peter Otten - sauber) Peter2 : 0.0169 sec (Peter Otten - schnell) Rene_x : 0.0279 sec (Rene Liebscher mit Generator) Gerson : 0.0175 sec (Gerson Kurz) Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 1.8552 sec (Alexander B÷secke) Peter : 3.1761 sec (Peter Otten - sauber) Peter2 : 2.8525 sec (Peter Otten - schnell) Rene_x : 2.6861 sec (Rene Liebscher mit Generator) Gerson : 1.9364 sec (Gerson Kurz) cu boesi -- #1671 : icq-intern Ohne Dich waeren die Gefuehle von heute #73628288 : icq-extern nur die leere Huelle der Gefuehle von damals boesi111 : aim .-==Die fabelhafte Welt der Amelie==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Ich habe mir Rene_x() gerade angesehen. Ich habe doch zusätzlichen Speicherbedarf - für das Tupel zur Stringformatierung. Vielleicht kommt Linux damit besser zurecht. Probier doch bitte mal die folgende Variante (ich habe die Tricks von dir und Christian Tismer geklaut) auf deinem Rechner: <code> def expSeries(seq): it = iter(seq) first = prev = it.next() # assert first >= 0 for item in it: if item - prev != 1: if first == prev: yield `first` else: yield `first` + `-prev` first = item prev = item if first == prev: yield `first` else: yield `first` + `-prev` def Peter_exp(sample): return ",".join(expSeries(sample)) </code> Falls Peter_exp() besser skaliert, wäre die Ursache für den Performanceeinbruch wohl geklärt. Peter _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 21:24:09 schrieb Peter Otten:
Hmm war das nicht so, dass Linux so spaet wie moeglich mit auslagern anfaengt, waerhend Windows das staendig tut? Aber ich glaub nicht, dass der Speicher das Problem ist, sofern man genug davon hat. Soweit ich dem Task-Manager vertrauen kann, verbraten alle Algorithmen in Abhaengigkeit von n etwa gleich viel Speicher (bei n=1000000 ca 90MB). Und die Auslagerungsstrategie sollte nur bei der ersten Runde eine Rolle spielen (wobei Linux in diesem Fall eigentlich schlechter abschneiden muesste).
Falls Peter_exp() besser skaliert, wäre die Ursache für den Performanceeinbruch wohl geklärt.
Anzahl Listenelemente: 10000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.0164 sec (Alexander B÷secke) Peter : 0.0187 sec (Peter Otten - sauber) Peter2 : 0.0148 sec (Peter Otten - schnell) Peter3 : 0.0129 sec (Peter Otten - schnell optimiert) Anzahl Listenelemente: 100000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.1796 sec (Alexander B÷secke) Peter : 0.1965 sec (Peter Otten - sauber) Peter2 : 0.1554 sec (Peter Otten - schnell) Peter3 : 0.1356 sec (Peter Otten - schnell optimiert) Bis hier skalieren alle Algorithmen mehr oder weniger gleich gut/schlecht. Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 1.8804 sec (Alexander B÷secke) Peter : 3.2440 sec (Peter Otten - sauber) Peter2 : 2.8126 sec (Peter Otten - schnell) Peter3 : 2.6305 sec (Peter Otten - schnell optimiert) Ab jetzt nur noch 3 Loops, weil ich die Mail ja nicht erst uebermorgen abschicken will. Anzahl Listenelemente: 3000000 Anzahl Loops: 3 Laufzeit pro Loop im Schnitt: boesi : 5.8073 sec (Alexander B÷secke) Peter : 17.1955 sec (Peter Otten - sauber) Peter2 : 16.0502 sec (Peter Otten - schnell) Peter3 : 15.3162 sec (Peter Otten - schnell optimiert) Anzahl Listenelemente: 5000000 Anzahl Loops: 3 Laufzeit pro Loop im Schnitt: boesi : 12.6489 sec (Alexander B÷secke) Peter : 41.3377 sec (Peter Otten - sauber) Peter2 : 39.4509 sec (Peter Otten - schnell) Peter3 : 38.6418 sec (Peter Otten - schnell optimiert) Hier reichen meine 512MB Arbeitsspeicher nicht mehr aus und es wird massiv auf die Platte zugegriffen - so massiv, dass die CPU-Last des Python-Prozesses teilweise gegen 0 geht. Anzahl Listenelemente: 10000000 Anzahl Loops: 1 Laufzeit pro Loop im Schnitt: boesi : 149.6341 sec (Alexander B÷secke) Peter : 173.1672 sec (Peter Otten - sauber) Peter2 : 196.2615 sec (Peter Otten - schnell) Peter3 : 192.8397 sec (Peter Otten - schnell optimiert) Interessanterweise skaliert deine saubere Variante leicht besser als die beiden anderen. cu boesi -- #1671 : icq-intern Frueher hattet ihr die Freiheit zu entscheiden #73628288 : icq-extern Heute seid ihr von dieser Entscheidung befreit boesi111 : aim .-==Report der Magd==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, etwas spät aber immerhin, mein Versuch def gerson(l): r = [None] * len(l) s = l[0] o = s+1 k = 0 for e in l: if e > o: if s != o-1: s = "%s-%s" % (s, o-1) r[k] = str(s) k += 1 s = e o = e+1 if s != o-1: s = "%s-%s" % (s, o-1) r[k] = str(s) k += 1 return ",".join(r[:k]) ergibt mit Alexanders' Skript folgende Zahlen Anzahl: 400000 Laufzeit (Jan): 1.9093 sec Laufzeit (Rene_y2): 1.7564 sec Laufzeit (Rene_x): 1.3950 sec Laufzeit (boesi): 1.1616 sec Laufzeit (Christian): 1.4527 sec Laufzeit (Gregor): 1.2036 sec Laufzeit (Detlef): 1.2071 sec Laufzeit (gerson): 0.9139 sec Ciao, Gerson
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Kannste die bitte nochmal hochladen? habe 'ne Idee. ciao - chris -- Christian Tismer :^) <mailto:tismer@stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 11:30:20 schrieb Christian Tismer:
Oehm warum? Weil die Datei existiert inzwischen bei mir nicht mehr. Aber letzten Endes hab ich nur die Algorithmen ausgelagert und einen Teil des __main__-Blocks in die Funktion benchFunc ausgelagert. Daher ist es trivial wieder die urspruengliche Datei herzustellen aber irgendwie fehlt mir die Intention das zu tun. Und die Datei Bench.zip aktualisier ich mehr oder weniger regelmaessig. cu boesi -- No matter where you are. #1671 : icq-intern Everyone is always connected. #73628288 : icq-extern boesi111 : aim i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Kann man bei den anderen Algos aber auch machen und dann ändert sich an den relativen Verhältnissen nichts. Es ist aber immer wieder überraschend, wie lahm Python bei gewissen String-Operationen ist. Hier sollte Python noch besser werden, den nicht jeder Entwickler denkt immer daran, das Py intern die Strings kopiert (neu anlegt), was die Laufzeit so schlecht macht. Der Weg, über eine Liste zu gehen und diese zu "joinen", gefällt mir aus Gründen der Verständlichkeit nicht so sehr, weil er das geplante Vorhaben eher verschleiert. -- Mit freundlichen Grüßen Klaus Meyer :-) _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo nochmal! On 18 Jun 2004 at 13:50, kgm wrote:
Passiert nicht mehr (so schnell) mit: r = re.sub(r"-\d+(?=-)","",r) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
kgm schrieb:
Kann jemand mit Euren Eingaben nachmessen, wie schnell das ist: l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] # l.sort() r=str(l[0]) seq = False for a,b in zip(l,l[1:]): if b-a==1: if not seq: seq = True r+="-" else: if seq: r += str(a) seq = False r += "," + str(b) if seq: r+="%s"%b print r Interessiert mich wegen des zip Danke, Gregor _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
kgm schrieb:
Also wenn Du schon mal mit Laufzeitmessungen anfängst solltest Du, dann aber auch meinen Hinweis auf die schlechte Laufzeit beachten und die andere Lösung nehmen (die zuerst gepostete mit Generator). Dann kommt ungefähr folgendes raus (Python 2.2 mit einen mehr schlechten als rechten Nachbau von random.sample) Anzahl 30000 Laufzeit (Frank): 7.3800 sec Laufzeit (kgm): 1.8900 sec Laufzeit (Jan): 4.5400 sec Laufzeit (Rene): 62.5200 sec Laufzeit (Rene,y2): 0.2900 sec Laufzeit (Rene,x): 0.2300 sec x ist die Lösung mit Generator. y2 die mit reduce aber mit Veränderung der übergebenen Liste. (Es existiert also nur noch eine Liste und nicht bei jedem Funktionsaufruf eine neue.) ############################################## def y2(list,element): if len(list) == 0: return [element] # Nachfolger von letzem in der liste if list[-1] == element-1: # liste erst angefangen oder irgendwas wie '... , x' drin if len(list)<2 or list[-2]==',': # anhaengen list.append('-') list.append(element) return list else: # letztes Element in Liste austauschen list[-1]=element return list else: # neues anhaengen list.append(',') list.append(element) return list ############################################## So gesehen gefällt mir das Ergebnis viel besser, weil meine erste Lösung dann doch schon die schnellste war ;-) Man müsste das zwar nochmal gegen die anderen Verbesserungen vergleichen, aber die Lösung mit Generator halte ich irgendwie immer noch für die übersichtlichste. Zumal ich da auch jedes Listenelement nur einmal zugreifen muss, könnte der Input selbst wieder ein Iterator/Generator oder irgendeine andere nichtwiederholbare Sequenz sein. (Dann muss natürlich die for-Anweisung ersetzt werden.) Die zweite Sache mit dem nachträglichen Umwandeln in einen String (mit str/join) halte ich eher für einen Vorteil, weil man hinterher noch die einzelnen Elemente da hat, falls man die nochmal braucht. (Sonst ist String parsen angesagt.) MfG Rene PS: Mehr Kommentare im Quelltext bei den anderen Beiträgen wären schon sinnvoll gewesen, gerade wenn man versucht anderen die Funktionsweise der eigenen Lösung nahezubringen. _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 18.06.2004 09:24:32 schrieb Frank Immich:
Also ohne das ich deinen Code auch nur ansatzweise verstanden hab, wuerde ich das mit ner Zustandsmaschine machen: ---snip--- liste=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] liste.sort() status = 0 r = '' for c in range(len(liste)): if status == 0: r += '%d' % liste[c] status = 1 elif status == 1: if liste[c] == liste[c-1]+1: status = 2 r += '-' else: r += ',%d' % liste[c] elif status == 2: if liste[c] != liste[c-1]+1: status = 1 r += '%d,%d' % (liste[c-1], liste[c]) print r ---snap--- Wenn 44,45 nicht als 44-45 dargestellt werden soll, sieht das wie folgt aus: ---snip--- for c in range(len(liste)): if status == 0: r += '%d' % liste[c] status = 1 elif status == 1: if liste[c] == liste[c-1]+1: status = 2 else: r += ',%d' % liste[c] elif status == 2: if liste[c] == liste[c-1]+1: status = 3 r += '-' else: status = 1 r += ',%d,%d' % (liste[c-1], liste[c]) elif status == 3: if liste[c] != liste[c-1]+1: status = 1 r += '%d,%d' % (liste[c-1], liste[c]) ---snap--- hoffe das hilft dir weiter cu boesi -- Wenn de Lüch net waer un dr Neid #1671 : icq-intern gäbs lauter glückliche Leid #73628288 : icq-extern Uhne Lüch un Neid = ganz gewiß boesi111 : aim wär uf dr Ard is Paradies i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Also ich antworte mir mal selbst Hab die Zustandsmaschine noch ein wenig optimiert und ne Funktion draus gemacht: ---snip--- def formatListe(liste, opt=2): """ [1,2,3,5,7,8,9,11] soll als "1-3,5,7-9,11" ausgegeben werden Parameter: liste - zu formatierende Liste opt - 2: [2,4,5,7] wird zu "2,4,5,7" 3: [2,4,5,7] wird zu "2,4-5,7" """ liste.sort() zustand = 1 c = 0 ret = '%d' % liste[c] for c in range(1,len(liste)): if zustand == 1: if liste[c] != liste[c-1]+1: ret += ',%d' % liste[c] else: zustand = opt elif zustand == 2: if liste[c] != liste[c-1]+1: zustand = 1 ret += ',%d,%d' % (liste[c-1], liste[c]) else: zustand = 3 elif zustand == 3: if liste[c] != liste[c-1]+1: zustand = 1 ret += '-%d,%d' % (liste[c-1], liste[c]) return ret ---snap--- Was man nicht alles tut, um nicht fuer Pruefungen lernen zu muessen *grummel* cu boesi -- Wenn de Lüch net waer un dr Neid #1671 : icq-intern gäbs lauter glückliche Leid #73628288 : icq-extern Uhne Lüch un Neid = ganz gewiß boesi111 : aim wär uf dr Ard is Paradies i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Frank! On 18 Jun 2004 at 9:24, Frank Immich wrote:
Von mir noch eine eher 'textuelle', denn algorithmische Lösung, bei der ich alle "-<zahl>-"-Folgen am Schluss lösche: import re l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() r="" for i in xrange(len(l)-1): if l[i+1] - l[i] == 1: r += str(l[i])+"-" else: r += str(l[i])+"," r += str(l[-1]) print r r = re.sub(r"-(\d+-)+","-",r) print r Die Ausgabe wäre: 3,5-6-7-8-9-10-11-12,22-23-24-25-26,32,34,36,38-39-40-41,44-45,47 3,5-12,22-26,32,34,36,38-41,44-45,47 Ich erläutere den Regulären Ausdruck erstmal nicht, da Du damit ja vielleicht vertraut bist. Funktioniert nur für positive Ganzzahlen. Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Frank Immich wrote:
Ob das jetzt einfacher oder eleganter ist, weiß ich nicht, aber es geht mit ein 2 Hilfsfunktionen in einer Zeile :->... def lastNum(s): i = 1 if len(s) == 1: return 2 else: while((len(s) - i > 0) and s[-i].isdigit()): i = i + 1 return i def stripDashes(s): d = s.split("-") if len(d) > 1: return '-'.join((d[0], d[-1])) return s l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l[0] = str(l[0]) [stripDashes(i) for i in reduce(lambda x, y:("%s-%s" % (x, y), "%s,%s" % (x, y))[y != int(x[-lastNum(x) + 1:]) + 1], l).split(",")] Gruss, Jochen _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
* Frank Immich (2004-06-18 09:24 +0100)
Das was mir an deiner Lösung und der der anderen nicht gefällt ist, das alles in eins geschmissen wird: die Generierung der "Intervallenden" und die Ausgabe. So würde ich es machen: numbers = [3, 5, 6, 7, 8, 9, 10, 11, 12, 22, 23, 24, 25, 26, 32, 34, 36, 38, 39, 40, 41, 44, 45, 47] import itertools intervals = [] result = [] while numbers: rangelist = list(itertools.takewhile(lambda x: x[0] == x[1], zip(numbers, range(numbers[0], numbers[0] + len(numbers))))) intervals.append((rangelist[0][0], rangelist[-1][0])) del numbers[:len(rangelist)] for interval in intervals: if interval[0] == interval[1]: result.append(str(interval[0])) else: result.append(''.join([str(interval[0]), '-', str(interval[1])])) print ', '.join(result) Wie schneidet mein Programm in der Laufzeit ab? Thorsten _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Am Freitag, 18. Juni 2004 19:10 schrieb Thorsten Kampe:
Anzahl 40000 Laufzeit (jochen): 0.5900 sec Laufzeit (jan): 0.2200 sec Laufzeit (bösi): 0.1400 sec Laufzeit (gregor): 8.7500 sec Laufzeit (thorsten): 483.7400 sec starttime = time.clock() from copy import copy def z(x, y): if (y - 1 == x[-1]): x.append(y) else: x.append("x");x.append(y) return x ml = copy(l) ml[0] = [ml[0]] # Markieren e = reduce(z, ml) #Auseinanderschneiden m, n = [], [] for i in e: if i == "x": m.append(("%s-%s" % (n[0], n[-1]), "%s" % n[0])[n[0] == n[-1]]);n = [] elif e[-1] == i: n.append(i);m.append(("%s-%s" % (n[0], n[-1]), "%s" % n[0])[n[0] == n[-1]]) else: n.append(i) #Zusammenjoinen r = ', '.join(m) #print r print "Laufzeit (jochen): %3.4f sec" % (time.clock() - starttime) Der reduce-Teil gefällt mir ganz gut, der ist auch schön schnell. Das Auseinanderschneiden ist sehr langsam, das geht bestimmt irgendwie besser. Gruss, Jochen _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Jochen! Ich fürchte, das ist jetzt für die Liste vielleicht nicht mehr so interessant, doch ... Jochen Wersdörfer schrieb:
Am Freitag, 18. Juni 2004 19:10 schrieb Thorsten Kampe:
Anzahl 40000
Was bedeutet hier die 40000? Etwa 40000 Durchläufe, oder wird eine Liste mit 40000 Elementen generiert. Wann dies, dann welche, wie? (Damit ich selber zum Vergleich messen kann). Das mit dem zip hat sich nicht so recht bewährt :-[ Hab aus dem Thread - hoff' ich - ein bisschen gelernt und bin jetzt bei folgendem angelangt: l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() a = l.pop(0) r = [str(a)] seq = False for b in l: if b-a==1: if not seq: seq = True r.append("-") else: if seq: r.append(str(a)) seq = False r.append(","+str(b)) a = b if seq: r.append(str(b)) r = ''.join(r) print r Sollte doch erheblich schneller sein. Schöne Grüße Gregor P.S.: Wie man an an den unmöglichen Zeiten, wo ich poste erkennen kann, bin ich offenbar nicht Profi- sondern Freizeitprogrammierer. (Wenn man bei Lehrern von Freizeit sprechen kann ... ;-)
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo, ich habe gerade die ganzen mails gesehen die ich hiermit noch ausgelöst habe :-) Vielen Dank für die ganzen Antworten. Da kann ich eine Menge lernen (und wohl nicht nur ich) Grüße Frank --- Weitergeleitete Nachricht / Forwarded Message --- Date: Fri, 18 Jun 2004 09:24:32 +0200 (MEST) From: "Frank Immich" <frankimmich@gmx.de> To: python-de@python.net Subject: 1,2,3,5,7,8,9 -> "1-3,5,7-9" Hallo zusammen, ich bin irgendwie nicht zufrieden... Ich würde gerne aus einer Liste: z.b. 1,2,3,5,7,8,9,11 einen String generieren, wobei fortlaufende Reihen zusammengefasst werden. -> "1-3,5,7-9,11" hier mein kläglicher Vesuch... irgendwie habe ich das Gefühl: Das muss einfacher gehen ? Vielleicht hat ja jemand Lust auf diese kleine morgendliche Denksportaufgabe... Vielen Dank Grüße Frank #!/usr/local/bin/python l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() r="" mylist=[] for c in xrange(len(l)-1): mylist.append(l[c]) if l[c]+1 == l[c+1]:continue if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," mylist=[] mylist.append(l[len(l)-1]) if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," print r -- NEU: WLAN-Router für 0,- EUR* - auch für DSL-Wechsler! GMX DSL = supergünstig & kabellos http://www.gmx.net/de/go/dsl _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Frank Immich schrieb:
Denksportaufgaben sind immer eine Herausforderung ;-) Ob das folgende einfacher ist, weiss ich auch nicht. Aber ich finde es übersichtlicher. (Ausserdem wollte ich schon immer mal Generatoren ausprobieren. Und das scheint mir ein guten Anwendungsfall zu sein. Mit filter,reduce und co. kommt man nicht so richtig weiter, weil man sich den letzten Zustand/Ausgabe irgendwie merken muss.) MfG Rene # fuer Python 2.2 from __future__ import generators def x(data): minus=0 last=data[0] # erstes ausgeben yield data[0] for i in data[1:]: # wenn das ein Nachfolger ist if i-1 == last: # minus ist schon mal ausgegeben? if minus: pass else: # dann eben jetzt erstmal yield '-' minus=1 last = i else: # kein Nachfolger # also x-y abschliessen, y ausgeben if minus: yield last minus =0 # trennkomma ausgeben yield ',' # Neues Element ausgeben yield i last = i # da fehlt der abschluss noch if minus: yield last import string print string.join( # die Zahlen muessen noch Strings werden map(str, x([3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] ) ),"") _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
René Liebscher schrieb:
Da muss ich mich selber korrigieren, man kann ja in reduce auch die bereits gebaute Liste als Zustandsspeicher missbrauchen. Das sieht dann so aus. (Ist sogar noch kuerzer als die andere Variante. Wie das von der Laufzeit bei sehr grossen Eingabelisten aussieht, ist eine andere Sache, weil je für jedes Element eine neue Liste angelegt wird.) def y(list,element): if len(list) == 0: return [element] # Nachfolger von letzem in der liste if list[-1] == element-1: # liste erst angefangen oder irgendwas wie '... , x' drin if len(list)<2 or list[-2]==',': # anhaengen return list+['-',element] else: # letztes Element in Liste austauschen return list[:-1]+[element] else: # neues anhaengen return list+[',',element] print string.join( # die Zahlen muessen noch Strings werden map(str, reduce(y,[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47],[]) ),"") _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, On Fri, 18 Jun 2004 10:54:39 +0200, René Liebscher <R.Liebscher@gmx.de> wrote:
Wie das von der Laufzeit bei sehr grossen Eingabelisten aussieht, ist
habe Deine Laufzeit-Anmerkung mal zum Anlass genommen, einige der geposteten Varianten zu messen. Hier die Messung für 30000 Zahlen: Anzahl 30000 Laufzeit (Frank): 7.6432 sec Laufzeit (kgm): 3.1479 sec Laufzeit (Jan): 6.8867 sec Laufzeit (Rene): 122.2487 sec Jan Lösungen mit der re-Engine (die ich ganz interessant fand, da ich vermutlich nicht auf diese Idee gekommen wäre) hat den Effekt, bei manchen großen Listen mit "recursion limit" rauszufliegen! Hat mich etwas gewundert. Traceback (most recent call last): File "C:\Test\liste-laufzeit.py", line 22, in ? r = re.sub(r"-(\d+-)+","-",r) File "C:\Programme\Python\lib\sre.py", line 143, in sub return _compile(pattern, 0).sub(repl, string, count) RuntimeError: maximum recursion limit exceeded Hier die Source für eigene Tests: #Laufzeit-Test import time, random, re, string anzahl = 10000 #Anzahl der Zahleneintraege in Liste #Zufallsliste ohne Wiederholung random.seed(7) l = range( 2*anzahl ) l = random.sample(xrange(2*anzahl), anzahl) l.sort() print "Anzahl", anzahl #print l #Frank Immich starttime = time.clock() r="" mylist=[] for c in xrange(len(l)-1): mylist.append(l[c]) if l[c]+1 == l[c+1]:continue if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," mylist=[] mylist.append(l[len(l)-1]) if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," #print r print "Laufzeit (Frank): %3.4f sec" % (time.clock() - starttime) # kgm starttime = time.clock() l.append(l[-1]+2); r="" start = l[0] last = start for v in l: if v-last > 1: r += str(start) if last != start: r += "-" + str(last) r += "," start = v last = v del l[-1] #append wieder aufheben r = r[0:-1] #letzte Komma weg #print r print "Laufzeit (kgm): %3.4f sec" % (time.clock() - starttime) # Jan Voges starttime = time.clock() r="" for i in xrange(len(l)-1): if l[i+1] - l[i] == 1: r += str(l[i])+"-" else: r += str(l[i])+"," r += str(l[-1]) #print r r = re.sub(r"-(\d+-)+","-",r) #print r print "Laufzeit (Jan): %3.4f sec" % (time.clock() - starttime) #Rene Liebscher starttime = time.clock() def y(list,element): if len(list) == 0: return [element] # Nachfolger von letzem in der liste if list[-1] == element-1: # liste erst angefangen oder irgendwas wie '... , x' drin if len(list)<2 or list[-2]==',': # anhaengen return list+['-',element] else: # letztes Element in Liste austauschen return list[:-1]+[element] else: # neues anhaengen return list+[',',element] r = string.join( # die Zahlen muessen noch Strings werden map(str, reduce(y,l,[]) ),"") #print r print "Laufzeit (Rene): %3.4f sec" % (time.clock() - starttime) #ende -- Mit freundlichen Grüßen Klaus Meyer :-) _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo! On 18 Jun 2004 at 13:50, kgm wrote:
Oops, auf Performanz hab' ich nun gar nicht achtet. Die String-Concatinations sind natürlich schweineteuer. Deutlich besser: # Jan Voges starttime = time.clock() liste = [] for i in xrange(len(l)-1): liste.append(str(l[i])) if l[i+1] - l[i] == 1: liste.append("-") else: liste.append(",") liste.append(str(l[-1])) r = "".join(liste) #print r r = re.sub(r"-(\d+-)+","-",r) #print r print "Laufzeit (Jan): %3.4f sec" % (time.clock() - starttime) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 18.06.2004 14:07:42 schrieb Jan Voges:
Oops, auf Performanz hab' ich nun gar nicht achtet. Die String-Concatinations sind natürlich schweineteuer.
Huch :) Hab meine Loesung ebenfalls angepasst: zustand = 1 c = 0 res_liste = [] ret_liste.append('%d' % l[c]) for c in range(1,len(l)): if zustand == 1: if l[c] != liste[c-1]+1: res_liste.append(',%d' % l[c]) else: zustand = 2 elif zustand == 2: if l[c] != l[c-1]+1: zustand = 1 res_liste.append('-%d,%d' % (l[c-1], l[c])) result = ''.join(res_liste) und komme auf folgende Ergebnisse: Anzahl 40000 Laufzeit (Frank): 5.0987 sec Laufzeit (kgm): 2.8702 sec Laufzeit (Jan): 5.0814 sec Laufzeit (Jan_opt): 0.1492 sec Laufzeit (Rene): 64.5952 sec Laufzeit (boesi): 2.2832 sec Laufzeit (boesi_opt): 0.1037 sec Die beiden schnellsten nochmal im direkten Vergleich: Anzahl 1000000 Laufzeit (Jan_opt): 4.1980 sec Laufzeit (boesi_opt): 2.8218 sec cu boesi -- <seasons82> was ist rl? #1671 : icq-intern <seasons82> und muss man das wissen? #73628288 : icq-extern ...der moment wo einem klar wird, boesi111 : aim dass man zuviel chattet... i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Versuch mal die Lösung: def _ranges(s): if s: s.append (s[-1] + 2) ### sentinel to avoid cleanup after loop r = [s[0]] for v in s[1:]: d = v - r[-1] if d > 1: if len(r) > 2: yield "%s-%s" % (r[0], r[-1]) else: for u in r: yield str(u) r = [v] elif d == 1: r.append(v) def collapsed_ranges(seq): s = list(seq) s.sort() return list(_ranges(s)) -- Christian Tanzer http://www.c-tanzer.at/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, Alexander 'boesi' Bösecke wrote:
Jezt machst Du noch * '%d' % l[c] -> str(lc[0]) * weg mit den ständigen Index-Zugriffen * for num in l, statt über den range Und du solltest Sieger sein :-)
cu boesi
-- Schönen Gruß - Regards Hartmut Goebel | Hartmut Goebel | IT-Security -- effizient | | h.goebel@goebel-consult.de | www.goebel-consult.de | _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Es läßt einem ja doch keine Ruhe ... Wie man's auch anstellt, die Laufzeit hängt (jedenfalls unter den angenommenen Bedingungen) vor allem von der Anzahl der Hinzufügungen ab, sei es ergebnis+=str(wert) oder ergebnis.append(str(wert)); alle anderen Optimierungen fallen dagegen kaum ins Gewicht. Also versuche ich in dieser Richtung etwas zu "schummeln": l = [3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] # l.sort() res = [] last = None inrange = False comma = "" for i in l: if i - 1 != last: closing = inrange and "-" + str(last) or "" res.extend((closing, comma, str(i))) inrange = False comma = "," else: inrange = True last = i if inrange: res.extend(("-", str(last))) result = "".join(res) Und siehe da, vor allem das extend zahlt sich aus ;-) : $ ./bench.py n = 100000 boesi: 155.6 µs / Durchlauf 3,5-12,22-26,32,34,36,38-41,44-45,47 det: 139.7 µs / Durchlauf 3,5-12,22-26,32,34,36,38-41,44-45,47 $ Mit cStringIO erhielt ich übrigens auch keine besseren Werte. Zwar ist res = cStringIO.StringIO() ... print >>res, "-", last usw. schneller (die Function Calls, z.B. bei res.write(str(...)), sind teuer!), aber das produziert zusätzliche Blanks, die hier unerwünscht wären. Detlef _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 18.06.2004 19:19:09 schrieb Detlef Lannert:
Und siehe da, vor allem das extend zahlt sich aus ;-) :
Dank den Anregungen von Hartmut hab ich meine Lösung nochmal angepasst, sieht jetzt so aus: zustand = 1 last = liste.pop(0) resListe = [str(last)] for element in liste: if zustand == 1: if element != last+1: resListe.extend((',', str(element))) else: zustand = 2 elif zustand == 2: if element != last+1: zustand = 1 resListe.extend(('-', str(last), ',', str(element))) last = element # wenn die letzten Elemente der Liste zusammengefasst werden müssen, # müßen diese noch angehängt werden if liste[-2] == last-1: resListe.extend(('-', str(liste[-1]))) return ''.join(resListe) Die Entfernung der ganzen Indexzugriffe hat am meisten gebracht. Meßergebnisse: Hab mir mal den Spaß gemacht und alle (optimierten) Lösungen verglichen. Die jeweils langsamsten hab ich beim naechsten Durchlauf weggelassen. Anzahl: 10000 Laufzeit (Frank): 0.1927 sec Laufzeit (kgm): 0.0994 sec Laufzeit (Jan): 0.0370 sec Laufzeit (Rene_y2): 0.0323 sec Laufzeit (Rene_x): 0.0249 sec Laufzeit (boesi): 0.0216 sec Laufzeit (Christian): 0.0301 sec Laufzeit (Gregor): 0.0235 sec Laufzeit (Detlef): 0.0228 sec Laufzeit (Thorsten): 15.8565 sec Laufzeit (Jochen): 0.4025 sec Anzahl: 40000 Laufzeit (Frank): 5.7550 sec Laufzeit (kgm): 3.2524 sec Laufzeit (Jan): 0.1623 sec Laufzeit (Rene_y2): 0.1374 sec Laufzeit (Rene_x): 0.1043 sec Laufzeit (boesi): 0.0892 sec Laufzeit (Christian): 0.1227 sec Laufzeit (Gregor): 0.0971 sec Laufzeit (Detlef): 0.0987 sec Laufzeit (Jochen): 13.1420 sec Anzahl: 1000000 Laufzeit (Jan): 4.2928 sec Laufzeit (Rene_y2): 3.6483 sec Laufzeit (Rene_x): 2.7883 sec Laufzeit (boesi): 2.4917 sec Laufzeit (Christian): 3.2152 sec Laufzeit (Gregor): 2.6467 sec Laufzeit (Detlef): 2.5715 sec Mit Anzahl ist übrigens die Listengröße gemeint, der Code zum erzeugen der Zufallsliste wurde von kgm gepostet. Wenn jemand die Messungen selber durchführen oder anpassen will, hab die Datei hierhin gepackt: http://www.stud.tu-ilmenau.de/~boesi/temp/BenchListe.py cu boesi PS: ein Algorithmus mit der Laufzeit O(1) waere nett ;) -- --==SECURITY ALERT==-- #1671 : icq-intern Your Computer Is Currently Broadcasting An #73628288 : icq-extern Internet IP Address. With This Address, boesi111 : aim Someone Can Begin Attacking Your Computer. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, Alexander 'boesi' Bösecke wrote:
Dank den Anregungen von Hartmut hab ich meine Lösung nochmal angepasst,
:-) Und es geht noch schneller: Nachdem es nur die Zustände 1 und 2 gibt, kann man diese elif zustand == 2: ändern in else: Wenn Du dazu noch die Zustände 0 und 1 nimmst, genügt hier if zustand == 1: ein if zustand: Und wieder zwei Bytecode-Instruktionen gespart :-) -- Schönen Gruß - Regards Hartmut Goebel | Hartmut Goebel | IT-Security -- effizient | | h.goebel@goebel-consult.de | www.goebel-consult.de | _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 21.06.2004 12:26:21 schrieb Hartmut Goebel:
Und wieder zwei Bytecode-Instruktionen gespart :-)
Und es geht noch schneller :) Wenn man statt str(element) `element` verwendet. Und interessanterweise ist resListe.append('-' + `last` + ',' + `element`) ebenfalls schneller als resListe.extend(('-', `last`, ',', `element`)) Das letzte ist dann aber fast schon Erbsenzaehlerei. append und extend im Vergleich: Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt (boesi): 2.1438 sec Laufzeit pro Loop im Schnitt (boesi_app): 2.0951 sec Die neue Version der Datei liegt wieder unter der bereits angegebenen URL. cu boesi -- #1671 : icq-intern ...schlafen ist sowieso ungesund... #73628288 : icq-extern .-==Police Academy I==-. boesi111 : aim i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
--On Montag, 21. Juni 2004 13:21 Uhr +0200 Alexander 'boesi' Bösecke <boesi.josi@gmx.net> wrote:
Wer solchen Code (wegen ein bischen Erbsenzählerei) produziert gehört mit drei Perlbüchern gehauen :-) -aj _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 21.06.2004 14:02:30 schrieb Andreas Jung:
Ohje merkt man mir meine schaendliche Perlvergangenheit so schlimm an? *gg* Am "schoensten" ist es sicher, wenn man den Ausgabestring direkt zusammenbaut, aber wir haben ja bereits gelernt, dass Python in diesem Bereich a****lahm ist und man deswegen zB den Umweg ueber eine Liste geht. Und welche Variante man da dann am "schoensten" findet, ist in meinen Augen hauptsaechlich eine Sache der Gewohnheit. -------- Am 21.06.2004 16:31:53 schrieb Christian Tismer:
Aehm noe also eigentlich bin ich ganz spontan davon ausgegangen, dass das Erzeugen eines Tupel schneller geht als das einer Liste. Warum kann ich nicht sagen und auch nicht ob das stimmt, aber... Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 2.0425 sec (resListe.append('-' + `last` + ',' + `element`)) boesi2 : 2.1516 sec (resListe.extend(('-', `last`, ',',`element`))) boesi3 : 2.3793 sec (resListe.append('-%d,%d' % (last, element))) boesi4 : 2.3118 sec (resListe.extend(['-', `last`, ',', `element`])) cu boesi -- #1671 : icq-intern <THammY-> und meine hände ham bisher immer #73628288 : icq-extern nur das gemacht was ich will </THammY> boesi111 : aim i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Das ist allerdings erstaunlich und unerwartet. Ich hatte vermutet, daß das Tupel zunächst in eine Liste gewandelt würde, die dann zum Extend benutzt wird. Aber offensichtlich wird das Sequence-Protokoll direkt benutzt, und in der Tat sind Tupel schneller erstellt, insbesondere, weil sie einen eigenen Objekt-Cache haben und Du in diesem Fall immer wieder daselbbe Objekt bekommst. Die Idee mit repr als "`" geschrieben scheint gut, spart Opcodes. boesi3 : 2.3793 sec (resListe.append('-%d,%d' % (last, element))) Hier kommen wohl die Extra-Kosten für das Formatier-Tupel hinzu. boesi3 : 2.3793 sec (resListe.append('-%d,%d' % (last, element))) Probierbar wäre .append('-%d,%%d' % last % element) wobei ich vermute, es ist nicht viel besser. Das Tupel wird gespart, dafür wird zweimal formatiert. Aaaber eine Sache kannst Du evtl. noch machen. Die erwünschte Schreibweise impliziert doch, daß die Liste keine negativen Zahlen enthalten kann? Also kommt auch kein "bis 0" vor. Dann ist es evtl. billiger, eine positive Zahl negativ zu machen: resListe.append(`-last` + ',' + `element`) Interessant, ciao - chris -- Christian Tismer :^) <mailto:tismer@stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 11:23:38 schrieb Christian Tismer:
Aha. Schoen zu wissen, dass Tupel doch noch Vorteile gegenueber Listen bieten. :)
Die Idee mit repr als "`" geschrieben scheint gut, spart Opcodes.
Ist auch nur von http://www.skymind.com/~ocrow/python_string/ geklaut.
Ist denn auch die langsamste Variante.
Ich war implizit davon ausgegangen, dass negative Zahlen vorkommen koennen, aber eigentlich hast du recht und ein klein wenig bringt auch das noch. Gersons Idee, statt dem append gleich mit Listindices zu arbeiten, bringt auch nochmal rund 10%, so dass nun zwischen der langsamsten und der schnellsten Version runde 70% liegen. Ist doch ganz ordentlich fuer ein bisschen Spielerei :) @Gerson: es ist nicht grad die feine Art, einbuchstabige Variablennamen zu verwenden. Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi1 : 2.4279 sec (resListe.append('-%d,%d' % (last, element))) boesi2 : 2.5484 sec (resListe.append('-%d,%%d' % last % element)) boesi3 : 2.0967 sec (resListe.append('-' + `last` + ',' + `element`)) boesi4 : 2.3170 sec (resListe.extend(['-', `last`, ',', `element`])) boesi5 : 2.1064 sec (resListe.extend(('-', `last`, ',', `element`))) boesi6 : 1.8772 sec (resListe[k] = '-' + `last` + ',' + `element`) boesi7 : 1.7992 sec (resListe[k] = `-last` + ',' + `element`) cu boesi -- #1671 : icq-intern Frueher hattet ihr die Freiheit zu entscheiden #73628288 : icq-extern Heute seid ihr von dieser Entscheidung befreit boesi111 : aim .-==Report der Magd==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Stimmt, und deshalb habe ich meine Variante mit dem Generator auch noch mal angepasst. Das läuft dann mehr als doppelt so schnell, wenn man die map/str Kombination weglässt und die Konversion in Strings schon in der Funktion ausführt. Anzahl 300000 Laufzeit (Rene,y2): 3.0700 sec # mit reduce Laufzeit (Rene,x): 2.6200 sec # mit Generator und map/str Laufzeit (Rene,x2): 1.1600 sec # mit Generator und `` Damit dürfte ich wieder an Peter's Zeiten dran sein ;-) MfG Rene ################################## def x2(data): minus=0 last=data[0] # erstes ausgeben yield `data[0]` for i in data[1:]: # wenn das ein Nachfolger ist if i-1 == last: # minus ist schon mal ausgegeben? if minus: pass else: # dann eben jetzt erstmal yield '-' minus=1 last = i else: # kein Nachfolger # also x-y abschliessen, y ausgeben if minus: yield `last` minus =0 # trennkomma ausgeben yield ',' # Neues Element ausgeben yield `i` last = i # da fehlt der abschluss noch if minus: yield `last` r = string.join(x2(l),"") ################################### _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Stimmt, und deshalb habe ich meine Variante mit dem Generator auch noch mal angepasst.
Mein Gott, was habe ich nur ausgelöst! Kommt jetzt auch noch je eine Version mit C und mit ASM-Einschub? ;-) Freundliche Grüße Klaus _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 21.06.2004 15:13:59 schrieb René Liebscher: Was zum Teufel hat GMX veranlasst deine Mail als Spam anzusehen?
Kann ich leider gar nicht bestaetigen. Anzahl Listenelemente: 10000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.0169 sec (Alexander B÷secke) Peter3 : 0.0130 sec (Peter Otten - schnell optimiert) Rene_x2 : 0.0162 sec (Rene Liebscher mit Generator und ``) Rene_x : 0.0250 sec (Rene Liebscher mit Generator und map/str) Anzahl Listenelemente: 100000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.1750 sec (Alexander B÷secke) Peter3 : 0.1381 sec (Peter Otten - schnell optimiert) Rene_x2 : 0.2196 sec (Rene Liebscher mit Generator und ``) Rene_x : 0.2613 sec (Rene Liebscher mit Generator und map/str) Anzahl Listenelemente: 300000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.5916 sec (Alexander B÷secke) Peter3 : 0.5711 sec (Peter Otten - schnell optimiert) Rene_x2 : 1.5888 sec (Rene Liebscher mit Generator und ``) Rene_x : 0.8867 sec (Rene Liebscher mit Generator und map/str) Also irgendwas laeuft da schief, den Versuch mit n=1000000 musste ich ganz abbrechen. Mit Generatoren hab ich mich leider noch gar nicht beschaeftigt, weswegen mir die Ursache absolut verborgen bleibt. Aber...
Was das soll, musst du mir mal erklaeren, warum machst du nicht einfach: if not minus: yield '-' minus=1 cu boesi -- #1671 : icq-intern Ohne Dich waeren die Gefuehle von heute #73628288 : icq-extern nur die leere Huelle der Gefuehle von damals boesi111 : aim .-==Die fabelhafte Welt der Amelie==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Aber vermutlich hast Du hier unabsichtlich ein Tupel kreiert, was zu einer Liste konvertiert werden muß. Keine Zeit zum testen, aber wie benimmt sich resListe.extend(['-', `last`, ',', `element`]) ? -- chris -- Christian Tismer :^) <mailto:tismer@stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo! On 21 Jun 2004 at 11:32, Alexander 'boesi' Bösecke wrote:
Dank für die Mühe! Also Perl-Geschädigter hätte ich noch einen Einzeiler anzubieten. def Jan2(l): """Jans Einzeiler""" return str(l[0]) + "," + "".join( [str(z)+(",","-")[l[i+2]-z==1] for i,z in enumerate(l[1:-1]) if l[i+2]-l[i]!=2] ) + str(l[-1]) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
On 21 Jun 2004 at 13:25, Jan Voges wrote:
Also Perl-Geschädigter hätte ich noch einen Einzeiler anzubieten.
Funktioniert leider nicht, also nicht beachten. Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
On 21 Jun 2004 at 13:42, Jan Voges wrote:
Funktioniert leider nicht, also nicht beachten. Jan
Jetzt aber ;-) def Jan2(l): """Jan' Einzeiler""" return "".join( [str(z)+(",","-")[l[i+1]-z==1] for i,z in enumerate(l[:-1]) if l[i+1]-l[i-1]!=2] ) + str(l[-1]) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Hab mir mal den Spaß gemacht und alle (optimierten) Lösungen verglichen. Die jeweils langsamsten hab ich beim naechsten Durchlauf weggelassen.
Hier zwei weitere Kandidaten für dein Testskript, Peter_schnell() und Peter_sauber(). Die schnellere Variante enthält den Stringkonvertierungscode "inline", der bei der sauberen Lösung in eine eigene Funktion chunk() ausgelagert ist. Peter_sauber() benötigt itertools.starmap(), funktioniert in dieser Form also erst ab Python 2.3. <BenchListe.py-Fragment> from itertools import starmap def chunk(s, t): if s == t: return "%s" % s else: return "%s-%s" % (s, t) def series(seq): it = iter(seq) first = prev = it.next() for item in it: if item - prev > 1: yield first, prev first = prev = item else: prev = item yield first, prev def Peter_sauber(sample): return ",".join(starmap(chunk, series(sample))) def inlineSeries(seq): it = iter(seq) first = prev = it.next() for item in it: if item - prev > 1: if first == prev: yield "%s" % first else: yield "%s-%s" % (first, prev) first = prev = item else: prev = item if first == prev: yield "%s" % first else: yield "%s-%s" % (first, prev) def Peter_schnell(sample): return ",".join(inlineSeries(sample)) funcListe = [Jan, Rene_y2, Rene_x, boesi, Christian, Gregor, Detlef, Peter_sauber, Peter_schnell] </BenchListe.py-Fragment> Ich habe festgestellt, dass bei der Messung die zuerst getestete Funktion etwas benachteiligt wird - hänge also bitte meine Funktionen ans Ende von funcListe :-) Um das Vertrauen in die präsentierten Algorithmen zu erhöhen, habe ich einen unittest geschrieben - nicht schön, aber leicht erweiterbar. Einige Lösungen bestehen nicht alle Tests. Damit das Testskript funktioniert, muss funcListe aus dem __main__-Block herausgenommen, d. h. in eine globale Variable umgewandelt werden. <test_BenchListe.py> import unittest import BenchListe for f in BenchListe.funcListe: class U(unittest.TestCase): def testEmpty(self, f=f): self.assertEqual(f([]), "") def testSingle(self, f=f): self.assertEqual(f([1]), "1") self.assertEqual(f([1,2]), "1-2") self.assertEqual(f([1,2,3]), "1-3") def testMulti(self, f=f): self.assertEqual(f([1,5,6,7,9]), "1,5-7,9") self.assertEqual(f([1,2,3,6,7,8,10,11,12]), "1-3,6-8,10-12") exec "U.__name__=%r\n%s = U" % (f.__name__, f.__name__) del U if __name__ == "__main__": unittest.main() </test_BenchListe.py> Hier die Zeiten auf meinem Rechner: Anzahl: 400000 Laufzeit (Jan): 1.6000 sec Laufzeit (Rene_y2): 1.4400 sec Laufzeit (Rene_x): 1.0800 sec Laufzeit (boesi): 0.8100 sec Laufzeit (Christian): 1.1500 sec Laufzeit (Gregor): 0.9200 sec Laufzeit (Detlef): 0.8300 sec Laufzeit (Peter_sauber): 0.6100 sec Laufzeit (Peter_schnell): 0.4900 sec Weiter viel Spaß beim Optimieren, Peter _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Das Packet liegt jetzt unter http://www.stud.tu-ilmenau.de/~boesi/temp/Bench.zip Die Algorithmen hab ich in AlgoListe.py ausgelagert, der Test wird mit Bench.py gestartet, die Unittests befinden sich in testBenchListe.py. Die Funktion benchFunc kann zum testen der Laufzeit beliebiger Funktionen genutzt werden. Als Parameter nimmt sie die Anzahl der Runden, die zu testende Funktion und eventuelle Parameter fuer die Funktion. Rueckgabewerte sind die Zeit fuer alle Runden (also kein Durchschnitt) und das Ergebnis der letzten Runde. Am 21.06.2004 13:56:37 schrieb Peter Otten:
Hier zwei weitere Kandidaten für dein Testskript, Peter_schnell() und Peter_sauber().
Sind genau wie die Funktion von Gerson in AlgoListe aufgenommen.
Das sollte sich nun erledigt haben...
Das liegt aber hautpsaechlich an der etwas ungenauen Spezifikation. So hat ein derartiger Algorithmus nur bei n>1 Sinn. Ausserdem ist nicht festgelegt was zB mit der Liste [1,3,4,6] passieren soll, soll 3,4 zusammengefasst werden oder nicht?
Hier die Zeiten auf meinem Rechner:
Bei deinen Algorithmen ist mir aufgefallen, dass sie bei größerem n gegebenueber anderen Algorithmen langsamer werden. Bei kleinem n aber ist besonders die schnelle Variante bisher ungeschlagen :) Anzahl Listenelemente: 100000 Anzahl Loops: 10 Laufzeit pro Loop im Schnitt: Jan : 0.3910 sec (Jan Voges) Jan2 : 0.2944 sec (Jan' Einzeiler) Rene_y2 : 0.3447 sec (Rene Liebscher mit reduce) Rene_x : 0.2541 sec (Rene Liebscher mit Generator) boesi : 0.1942 sec (Alexander B÷secke) Christian : 0.3086 sec (Christian Tanzer) Detlef : 0.2357 sec (Detlef Lannert) Gregor : 0.2474 sec (Gregor Lingl) Peter : 0.1916 sec (Peter Otten - sauber) Peter2 : 0.1570 sec (Peter Otten - schnell) Gerson : 0.1813 sec (Gerson Kurz) Anzahl Listenelemente: 1000000 Anzahl Loops: 10 Laufzeit pro Loop im Schnitt: Jan : 4.0364 sec (Jan Voges) Jan2 : 3.0187 sec (Jan' Einzeiler) Rene_y2 : 3.6156 sec (Rene Liebscher mit reduce) Rene_x : 2.7027 sec (Rene Liebscher mit Generator) boesi : 2.1021 sec (Alexander B÷secke) Christian : 3.2338 sec (Christian Tanzer) Detlef : 2.5933 sec (Detlef Lannert) Gregor : 2.6628 sec (Gregor Lingl) Peter : 3.1593 sec (Peter Otten - sauber) Peter2 : 2.7808 sec (Peter Otten - schnell) Gerson : 1.9040 sec (Gerson Kurz) cu boesi -- #1671 : icq-intern Ohne Dich waeren die Gefuehle von heute #73628288 : icq-extern nur die leere Huelle der Gefuehle von damals boesi111 : aim .-==Die fabelhafte Welt der Amelie==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Stimmt. Deshalb habe ich die "Konkurrenz" auch nicht fehlerhaft genannt, sondern eine neutrale Formulierung gewählt.
hat ein derartiger Algorithmus nur bei n>1 Sinn. Ausserdem ist nicht
Meine Vorlieben ergeben sich aus der sauberen Variante vor der Umwandlung in Strings. Ich halte list(series([])) == [] und list(series([1])) == [(1,1)] hier durchaus für sinnvoll - im Gegensatz zum Beispiel zu max([]). Wer anderer Meinung ist, sollte aber zumindest einen ValueError auslösen (in einem "echten" Programm, für den Benchmark ist das nicht sooo wichtig).
festgelegt was zB mit der Liste [1,3,4,6] passieren soll, soll 3,4 zusammengefasst werden oder nicht?
Ich halte "1,3-4,7" für besser lesbar als "1,3,4,7", weil 3 und 4 so leichter als benachbart erkennbar sind - aber das ist wiederum mehr Meinung als Tatsache oder gar Spezifikation. Fazit: eine Testsuite ist eine feine Sache, um kleinere Zweifelsfälle auszuräumen.
Vielleicht mache ich später noch ein t(N)-Diagramm, zunächst die Zeiten für deine aktuelle Version auf meinem Rechner. Anzahl Listenelemente: 1000000 Anzahl Loops: 10 Laufzeit pro Loop im Schnitt: Jan : 3.9890 sec (Jan Voges) Jan2 : 2.7010 sec (Jan' Einzeiler) Rene_y2 : 3.5420 sec (Rene Liebscher mit reduce) Rene_x : 2.5930 sec (Rene Liebscher mit Generator) boesi : 1.5670 sec (Alexander Bösecke) Christian : 2.9200 sec (Christian Tanzer) Detlef : 2.0510 sec (Detlef Lannert) Gregor : 2.3210 sec (Gregor Lingl) Peter : 1.4610 sec (Peter Otten - sauber) Peter2 : 1.1650 sec (Peter Otten - schnell) Gerson : 1.5090 sec (Gerson Kurz) Eine alternative Messung mit timeit.py $ timeit.py -s"import Bench as b" -s"s=b.erzListe(1000000)" "b.Peter2(s)" 10 loops, best of 3: 1.28e+06 usec per loop $ timeit.py -s"import Bench as b" -s"s=b.erzListe(1000000)" "b.Gerson(s)" 10 loops, best of 3: 1.55e+06 usec per loop bringt auch keine weiteren Erkenntnisse, außer dass der Lüfter nur bei Gerson() anläuft :-) Auf den ersten Blick kann ich nicht erkennen, dass mein Algorithmus schlecht skaliert - was ich auf Grund des Pythoncodes auch nicht erwartet habe. Ein zu kleiner Hauptspeicher scheidet als Ursache für die schlechteren Zeiten auf deinem Rechner wohl aus - ich habe nur 256MB und ausserdem benötigt Gerson() vermutlich mehr Speicher als Peter2(). Peter _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 12:14:45 schrieb Peter Otten:
Fazit: eine Testsuite ist eine feine Sache, um kleinere Zweifelsfälle auszuräumen.
Fazit2: eine TestSuite ist eine feine Sache, wenn die Testfälle streng nach der Spezifikation erstellt werden koennen, ohne das dabei irgendwelche Annahmen gemacht werden muessen
Eine alternative Messung mit timeit.py
Warum sacht mir denn keener, dasses den Scheiss schon gibt? *g*
Hmm und wo liegt dann die Ursache, dass deine Algorithmen auf meinem Rechner relativ stark einbrechen? Auch wenn die Meßergebnisse nur grobe Anhaltspunkte sind, so geben sie doch eine Tendenz an und sind zudem reproduzierbar. Aus deinem Prompt schließe ich, dass du ein unixiodes System verwendest, ich nutze WinXP - sollte hier das Problem liegen? Zuerst dachte ich, dass die Implementierung der Generator-Funktion unter Windows nicht so performant ist wie auf Unix-Systemen. Dem widerspricht aber Rene_x, denn der zeigt dieses Verhalten nicht. Anzahl Listenelemente: 10000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.0165 sec (Alexander B÷secke) Peter : 0.0191 sec (Peter Otten - sauber) Peter2 : 0.0169 sec (Peter Otten - schnell) Rene_x : 0.0279 sec (Rene Liebscher mit Generator) Gerson : 0.0175 sec (Gerson Kurz) Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 1.8552 sec (Alexander B÷secke) Peter : 3.1761 sec (Peter Otten - sauber) Peter2 : 2.8525 sec (Peter Otten - schnell) Rene_x : 2.6861 sec (Rene Liebscher mit Generator) Gerson : 1.9364 sec (Gerson Kurz) cu boesi -- #1671 : icq-intern Ohne Dich waeren die Gefuehle von heute #73628288 : icq-extern nur die leere Huelle der Gefuehle von damals boesi111 : aim .-==Die fabelhafte Welt der Amelie==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Ich habe mir Rene_x() gerade angesehen. Ich habe doch zusätzlichen Speicherbedarf - für das Tupel zur Stringformatierung. Vielleicht kommt Linux damit besser zurecht. Probier doch bitte mal die folgende Variante (ich habe die Tricks von dir und Christian Tismer geklaut) auf deinem Rechner: <code> def expSeries(seq): it = iter(seq) first = prev = it.next() # assert first >= 0 for item in it: if item - prev != 1: if first == prev: yield `first` else: yield `first` + `-prev` first = item prev = item if first == prev: yield `first` else: yield `first` + `-prev` def Peter_exp(sample): return ",".join(expSeries(sample)) </code> Falls Peter_exp() besser skaliert, wäre die Ursache für den Performanceeinbruch wohl geklärt. Peter _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 21:24:09 schrieb Peter Otten:
Hmm war das nicht so, dass Linux so spaet wie moeglich mit auslagern anfaengt, waerhend Windows das staendig tut? Aber ich glaub nicht, dass der Speicher das Problem ist, sofern man genug davon hat. Soweit ich dem Task-Manager vertrauen kann, verbraten alle Algorithmen in Abhaengigkeit von n etwa gleich viel Speicher (bei n=1000000 ca 90MB). Und die Auslagerungsstrategie sollte nur bei der ersten Runde eine Rolle spielen (wobei Linux in diesem Fall eigentlich schlechter abschneiden muesste).
Falls Peter_exp() besser skaliert, wäre die Ursache für den Performanceeinbruch wohl geklärt.
Anzahl Listenelemente: 10000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.0164 sec (Alexander B÷secke) Peter : 0.0187 sec (Peter Otten - sauber) Peter2 : 0.0148 sec (Peter Otten - schnell) Peter3 : 0.0129 sec (Peter Otten - schnell optimiert) Anzahl Listenelemente: 100000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 0.1796 sec (Alexander B÷secke) Peter : 0.1965 sec (Peter Otten - sauber) Peter2 : 0.1554 sec (Peter Otten - schnell) Peter3 : 0.1356 sec (Peter Otten - schnell optimiert) Bis hier skalieren alle Algorithmen mehr oder weniger gleich gut/schlecht. Anzahl Listenelemente: 1000000 Anzahl Loops: 100 Laufzeit pro Loop im Schnitt: boesi : 1.8804 sec (Alexander B÷secke) Peter : 3.2440 sec (Peter Otten - sauber) Peter2 : 2.8126 sec (Peter Otten - schnell) Peter3 : 2.6305 sec (Peter Otten - schnell optimiert) Ab jetzt nur noch 3 Loops, weil ich die Mail ja nicht erst uebermorgen abschicken will. Anzahl Listenelemente: 3000000 Anzahl Loops: 3 Laufzeit pro Loop im Schnitt: boesi : 5.8073 sec (Alexander B÷secke) Peter : 17.1955 sec (Peter Otten - sauber) Peter2 : 16.0502 sec (Peter Otten - schnell) Peter3 : 15.3162 sec (Peter Otten - schnell optimiert) Anzahl Listenelemente: 5000000 Anzahl Loops: 3 Laufzeit pro Loop im Schnitt: boesi : 12.6489 sec (Alexander B÷secke) Peter : 41.3377 sec (Peter Otten - sauber) Peter2 : 39.4509 sec (Peter Otten - schnell) Peter3 : 38.6418 sec (Peter Otten - schnell optimiert) Hier reichen meine 512MB Arbeitsspeicher nicht mehr aus und es wird massiv auf die Platte zugegriffen - so massiv, dass die CPU-Last des Python-Prozesses teilweise gegen 0 geht. Anzahl Listenelemente: 10000000 Anzahl Loops: 1 Laufzeit pro Loop im Schnitt: boesi : 149.6341 sec (Alexander B÷secke) Peter : 173.1672 sec (Peter Otten - sauber) Peter2 : 196.2615 sec (Peter Otten - schnell) Peter3 : 192.8397 sec (Peter Otten - schnell optimiert) Interessanterweise skaliert deine saubere Variante leicht besser als die beiden anderen. cu boesi -- #1671 : icq-intern Frueher hattet ihr die Freiheit zu entscheiden #73628288 : icq-extern Heute seid ihr von dieser Entscheidung befreit boesi111 : aim .-==Report der Magd==-. i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi, etwas spät aber immerhin, mein Versuch def gerson(l): r = [None] * len(l) s = l[0] o = s+1 k = 0 for e in l: if e > o: if s != o-1: s = "%s-%s" % (s, o-1) r[k] = str(s) k += 1 s = e o = e+1 if s != o-1: s = "%s-%s" % (s, o-1) r[k] = str(s) k += 1 return ",".join(r[:k]) ergibt mit Alexanders' Skript folgende Zahlen Anzahl: 400000 Laufzeit (Jan): 1.9093 sec Laufzeit (Rene_y2): 1.7564 sec Laufzeit (Rene_x): 1.3950 sec Laufzeit (boesi): 1.1616 sec Laufzeit (Christian): 1.4527 sec Laufzeit (Gregor): 1.2036 sec Laufzeit (Detlef): 1.2071 sec Laufzeit (gerson): 0.9139 sec Ciao, Gerson
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Alexander 'boesi' Bösecke wrote:
Kannste die bitte nochmal hochladen? habe 'ne Idee. ciao - chris -- Christian Tismer :^) <mailto:tismer@stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 22.06.2004 11:30:20 schrieb Christian Tismer:
Oehm warum? Weil die Datei existiert inzwischen bei mir nicht mehr. Aber letzten Endes hab ich nur die Algorithmen ausgelagert und einen Teil des __main__-Blocks in die Funktion benchFunc ausgelagert. Daher ist es trivial wieder die urspruengliche Datei herzustellen aber irgendwie fehlt mir die Intention das zu tun. Und die Datei Bench.zip aktualisier ich mehr oder weniger regelmaessig. cu boesi -- No matter where you are. #1671 : icq-intern Everyone is always connected. #73628288 : icq-extern boesi111 : aim i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Kann man bei den anderen Algos aber auch machen und dann ändert sich an den relativen Verhältnissen nichts. Es ist aber immer wieder überraschend, wie lahm Python bei gewissen String-Operationen ist. Hier sollte Python noch besser werden, den nicht jeder Entwickler denkt immer daran, das Py intern die Strings kopiert (neu anlegt), was die Laufzeit so schlecht macht. Der Weg, über eine Liste zu gehen und diese zu "joinen", gefällt mir aus Gründen der Verständlichkeit nicht so sehr, weil er das geplante Vorhaben eher verschleiert. -- Mit freundlichen Grüßen Klaus Meyer :-) _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo nochmal! On 18 Jun 2004 at 13:50, kgm wrote:
Passiert nicht mehr (so schnell) mit: r = re.sub(r"-\d+(?=-)","",r) Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
kgm schrieb:
Kann jemand mit Euren Eingaben nachmessen, wie schnell das ist: l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] # l.sort() r=str(l[0]) seq = False for a,b in zip(l,l[1:]): if b-a==1: if not seq: seq = True r+="-" else: if seq: r += str(a) seq = False r += "," + str(b) if seq: r+="%s"%b print r Interessiert mich wegen des zip Danke, Gregor _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
kgm schrieb:
Also wenn Du schon mal mit Laufzeitmessungen anfängst solltest Du, dann aber auch meinen Hinweis auf die schlechte Laufzeit beachten und die andere Lösung nehmen (die zuerst gepostete mit Generator). Dann kommt ungefähr folgendes raus (Python 2.2 mit einen mehr schlechten als rechten Nachbau von random.sample) Anzahl 30000 Laufzeit (Frank): 7.3800 sec Laufzeit (kgm): 1.8900 sec Laufzeit (Jan): 4.5400 sec Laufzeit (Rene): 62.5200 sec Laufzeit (Rene,y2): 0.2900 sec Laufzeit (Rene,x): 0.2300 sec x ist die Lösung mit Generator. y2 die mit reduce aber mit Veränderung der übergebenen Liste. (Es existiert also nur noch eine Liste und nicht bei jedem Funktionsaufruf eine neue.) ############################################## def y2(list,element): if len(list) == 0: return [element] # Nachfolger von letzem in der liste if list[-1] == element-1: # liste erst angefangen oder irgendwas wie '... , x' drin if len(list)<2 or list[-2]==',': # anhaengen list.append('-') list.append(element) return list else: # letztes Element in Liste austauschen list[-1]=element return list else: # neues anhaengen list.append(',') list.append(element) return list ############################################## So gesehen gefällt mir das Ergebnis viel besser, weil meine erste Lösung dann doch schon die schnellste war ;-) Man müsste das zwar nochmal gegen die anderen Verbesserungen vergleichen, aber die Lösung mit Generator halte ich irgendwie immer noch für die übersichtlichste. Zumal ich da auch jedes Listenelement nur einmal zugreifen muss, könnte der Input selbst wieder ein Iterator/Generator oder irgendeine andere nichtwiederholbare Sequenz sein. (Dann muss natürlich die for-Anweisung ersetzt werden.) Die zweite Sache mit dem nachträglichen Umwandeln in einen String (mit str/join) halte ich eher für einen Vorteil, weil man hinterher noch die einzelnen Elemente da hat, falls man die nochmal braucht. (Sonst ist String parsen angesagt.) MfG Rene PS: Mehr Kommentare im Quelltext bei den anderen Beiträgen wären schon sinnvoll gewesen, gerade wenn man versucht anderen die Funktionsweise der eigenen Lösung nahezubringen. _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Am 18.06.2004 09:24:32 schrieb Frank Immich:
Also ohne das ich deinen Code auch nur ansatzweise verstanden hab, wuerde ich das mit ner Zustandsmaschine machen: ---snip--- liste=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] liste.sort() status = 0 r = '' for c in range(len(liste)): if status == 0: r += '%d' % liste[c] status = 1 elif status == 1: if liste[c] == liste[c-1]+1: status = 2 r += '-' else: r += ',%d' % liste[c] elif status == 2: if liste[c] != liste[c-1]+1: status = 1 r += '%d,%d' % (liste[c-1], liste[c]) print r ---snap--- Wenn 44,45 nicht als 44-45 dargestellt werden soll, sieht das wie folgt aus: ---snip--- for c in range(len(liste)): if status == 0: r += '%d' % liste[c] status = 1 elif status == 1: if liste[c] == liste[c-1]+1: status = 2 else: r += ',%d' % liste[c] elif status == 2: if liste[c] == liste[c-1]+1: status = 3 r += '-' else: status = 1 r += ',%d,%d' % (liste[c-1], liste[c]) elif status == 3: if liste[c] != liste[c-1]+1: status = 1 r += '%d,%d' % (liste[c-1], liste[c]) ---snap--- hoffe das hilft dir weiter cu boesi -- Wenn de Lüch net waer un dr Neid #1671 : icq-intern gäbs lauter glückliche Leid #73628288 : icq-extern Uhne Lüch un Neid = ganz gewiß boesi111 : aim wär uf dr Ard is Paradies i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Also ich antworte mir mal selbst Hab die Zustandsmaschine noch ein wenig optimiert und ne Funktion draus gemacht: ---snip--- def formatListe(liste, opt=2): """ [1,2,3,5,7,8,9,11] soll als "1-3,5,7-9,11" ausgegeben werden Parameter: liste - zu formatierende Liste opt - 2: [2,4,5,7] wird zu "2,4,5,7" 3: [2,4,5,7] wird zu "2,4-5,7" """ liste.sort() zustand = 1 c = 0 ret = '%d' % liste[c] for c in range(1,len(liste)): if zustand == 1: if liste[c] != liste[c-1]+1: ret += ',%d' % liste[c] else: zustand = opt elif zustand == 2: if liste[c] != liste[c-1]+1: zustand = 1 ret += ',%d,%d' % (liste[c-1], liste[c]) else: zustand = 3 elif zustand == 3: if liste[c] != liste[c-1]+1: zustand = 1 ret += '-%d,%d' % (liste[c-1], liste[c]) return ret ---snap--- Was man nicht alles tut, um nicht fuer Pruefungen lernen zu muessen *grummel* cu boesi -- Wenn de Lüch net waer un dr Neid #1671 : icq-intern gäbs lauter glückliche Leid #73628288 : icq-extern Uhne Lüch un Neid = ganz gewiß boesi111 : aim wär uf dr Ard is Paradies i171 : reallife _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Frank! On 18 Jun 2004 at 9:24, Frank Immich wrote:
Von mir noch eine eher 'textuelle', denn algorithmische Lösung, bei der ich alle "-<zahl>-"-Folgen am Schluss lösche: import re l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() r="" for i in xrange(len(l)-1): if l[i+1] - l[i] == 1: r += str(l[i])+"-" else: r += str(l[i])+"," r += str(l[-1]) print r r = re.sub(r"-(\d+-)+","-",r) print r Die Ausgabe wäre: 3,5-6-7-8-9-10-11-12,22-23-24-25-26,32,34,36,38-39-40-41,44-45,47 3,5-12,22-26,32,34,36,38-41,44-45,47 Ich erläutere den Regulären Ausdruck erstmal nicht, da Du damit ja vielleicht vertraut bist. Funktioniert nur für positive Ganzzahlen. Jan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Frank Immich wrote:
Ob das jetzt einfacher oder eleganter ist, weiß ich nicht, aber es geht mit ein 2 Hilfsfunktionen in einer Zeile :->... def lastNum(s): i = 1 if len(s) == 1: return 2 else: while((len(s) - i > 0) and s[-i].isdigit()): i = i + 1 return i def stripDashes(s): d = s.split("-") if len(d) > 1: return '-'.join((d[0], d[-1])) return s l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l[0] = str(l[0]) [stripDashes(i) for i in reduce(lambda x, y:("%s-%s" % (x, y), "%s,%s" % (x, y))[y != int(x[-lastNum(x) + 1:]) + 1], l).split(",")] Gruss, Jochen _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
* Frank Immich (2004-06-18 09:24 +0100)
Das was mir an deiner Lösung und der der anderen nicht gefällt ist, das alles in eins geschmissen wird: die Generierung der "Intervallenden" und die Ausgabe. So würde ich es machen: numbers = [3, 5, 6, 7, 8, 9, 10, 11, 12, 22, 23, 24, 25, 26, 32, 34, 36, 38, 39, 40, 41, 44, 45, 47] import itertools intervals = [] result = [] while numbers: rangelist = list(itertools.takewhile(lambda x: x[0] == x[1], zip(numbers, range(numbers[0], numbers[0] + len(numbers))))) intervals.append((rangelist[0][0], rangelist[-1][0])) del numbers[:len(rangelist)] for interval in intervals: if interval[0] == interval[1]: result.append(str(interval[0])) else: result.append(''.join([str(interval[0]), '-', str(interval[1])])) print ', '.join(result) Wie schneidet mein Programm in der Laufzeit ab? Thorsten _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Am Freitag, 18. Juni 2004 19:10 schrieb Thorsten Kampe:
Anzahl 40000 Laufzeit (jochen): 0.5900 sec Laufzeit (jan): 0.2200 sec Laufzeit (bösi): 0.1400 sec Laufzeit (gregor): 8.7500 sec Laufzeit (thorsten): 483.7400 sec starttime = time.clock() from copy import copy def z(x, y): if (y - 1 == x[-1]): x.append(y) else: x.append("x");x.append(y) return x ml = copy(l) ml[0] = [ml[0]] # Markieren e = reduce(z, ml) #Auseinanderschneiden m, n = [], [] for i in e: if i == "x": m.append(("%s-%s" % (n[0], n[-1]), "%s" % n[0])[n[0] == n[-1]]);n = [] elif e[-1] == i: n.append(i);m.append(("%s-%s" % (n[0], n[-1]), "%s" % n[0])[n[0] == n[-1]]) else: n.append(i) #Zusammenjoinen r = ', '.join(m) #print r print "Laufzeit (jochen): %3.4f sec" % (time.clock() - starttime) Der reduce-Teil gefällt mir ganz gut, der ist auch schön schnell. Das Auseinanderschneiden ist sehr langsam, das geht bestimmt irgendwie besser. Gruss, Jochen _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Jochen! Ich fürchte, das ist jetzt für die Liste vielleicht nicht mehr so interessant, doch ... Jochen Wersdörfer schrieb:
Am Freitag, 18. Juni 2004 19:10 schrieb Thorsten Kampe:
Anzahl 40000
Was bedeutet hier die 40000? Etwa 40000 Durchläufe, oder wird eine Liste mit 40000 Elementen generiert. Wann dies, dann welche, wie? (Damit ich selber zum Vergleich messen kann). Das mit dem zip hat sich nicht so recht bewährt :-[ Hab aus dem Thread - hoff' ich - ein bisschen gelernt und bin jetzt bei folgendem angelangt: l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() a = l.pop(0) r = [str(a)] seq = False for b in l: if b-a==1: if not seq: seq = True r.append("-") else: if seq: r.append(str(a)) seq = False r.append(","+str(b)) a = b if seq: r.append(str(b)) r = ''.join(r) print r Sollte doch erheblich schneller sein. Schöne Grüße Gregor P.S.: Wie man an an den unmöglichen Zeiten, wo ich poste erkennen kann, bin ich offenbar nicht Profi- sondern Freizeitprogrammierer. (Wenn man bei Lehrern von Freizeit sprechen kann ... ;-)
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo, ich habe gerade die ganzen mails gesehen die ich hiermit noch ausgelöst habe :-) Vielen Dank für die ganzen Antworten. Da kann ich eine Menge lernen (und wohl nicht nur ich) Grüße Frank --- Weitergeleitete Nachricht / Forwarded Message --- Date: Fri, 18 Jun 2004 09:24:32 +0200 (MEST) From: "Frank Immich" <frankimmich@gmx.de> To: python-de@python.net Subject: 1,2,3,5,7,8,9 -> "1-3,5,7-9" Hallo zusammen, ich bin irgendwie nicht zufrieden... Ich würde gerne aus einer Liste: z.b. 1,2,3,5,7,8,9,11 einen String generieren, wobei fortlaufende Reihen zusammengefasst werden. -> "1-3,5,7-9,11" hier mein kläglicher Vesuch... irgendwie habe ich das Gefühl: Das muss einfacher gehen ? Vielleicht hat ja jemand Lust auf diese kleine morgendliche Denksportaufgabe... Vielen Dank Grüße Frank #!/usr/local/bin/python l=[3,5,6,7,8,9,10,11,12,22,23,24,25,26,32,34,36,38,39,40,41,44,45,47] l.sort() r="" mylist=[] for c in xrange(len(l)-1): mylist.append(l[c]) if l[c]+1 == l[c+1]:continue if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," mylist=[] mylist.append(l[len(l)-1]) if len(mylist)==1:r=r+str(mylist[0])+ "," else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+"," print r -- NEU: WLAN-Router für 0,- EUR* - auch für DSL-Wechsler! GMX DSL = supergünstig & kabellos http://www.gmx.net/de/go/dsl _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
participants (15)
-
Alexander 'boesi' Bösecke -
Andreas Jung -
Christian Tismer -
Detlef Lannert -
Frank Immich -
Gerson Kurz -
Gregor Lingl -
Hartmut Goebel -
Jan Voges -
Jochen Wersdörfer -
kgm -
Peter Otten -
René Liebscher -
tanzer＠swing.co.at -
Thorsten Kampe