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

Peter Otten __peter__ at web.de
Die Jun 22 12:14:45 CEST 2004


Alexander 'boesi' Bösecke wrote:

>> 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.
> 
> Das liegt aber hautpsaechlich an der etwas ungenauen Spezifikation. So

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.

> 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 :)

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