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

Detlef Lannert lannert at uni-duesseldorf.de
Fre Jun 18 19:19:09 CEST 2004


> >Die beiden schnellsten nochmal im direkten Vergleich:
> >Anzahl 1000000
> >Laufzeit (Jan_opt):   4.1980 sec
> >Laufzeit (boesi_opt): 2.8218 sec

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