[Python-de] 1,2,3,5,7,8,9 -> "1-3,5,7-9"

Alexander 'boesi' Bösecke boesi.josi at gmx.net
Mon Jun 21 11:32:49 CEST 2004


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