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

Peter Otten __peter__ at web.de
Mon Jun 21 13:56:37 CEST 2004


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