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

Gerson Kurz gerson.kurz at pergamon-software.de
Mon Jun 21 14:44:35 CEST 2004


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

> -----Ursprüngliche Nachricht-----
> Von: python-de-bounces at python.net
> [mailto:python-de-bounces at python.net]Im Auftrag von Alexander 'boesi'
> Bösecke
> Gesendet: Montag, 21. Juni 2004 10:33
> An: Python-de
> Betreff: Re: [Python-de] 1,2,3,5,7,8,9 -> "1-3,5,7-9"
>
>
> 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 at python.net
> http://python.net/mailman/listinfo/python-de
>