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

[kgm]

Hi,

On Fri, 18 Jun 2004 10:54:39 +0200, René Liebscher <R.Liebscher at gmx.de>  
wrote:

> Wie das von der Laufzeit bei sehr grossen Eingabelisten aussieht, ist

habe Deine Laufzeit-Anmerkung mal zum Anlass genommen, einige der  
geposteten Varianten zu messen. Hier die Messung für 30000 Zahlen:

Anzahl 30000
Laufzeit (Frank): 7.6432 sec
Laufzeit (kgm): 3.1479 sec
Laufzeit (Jan): 6.8867 sec
Laufzeit (Rene): 122.2487 sec


Jan Lösungen mit der re-Engine (die ich ganz interessant fand, da ich  
vermutlich nicht auf diese Idee gekommen wäre) hat den Effekt, bei manchen  
großen Listen mit "recursion limit" rauszufliegen! Hat mich etwas  
gewundert.

Traceback (most recent call last):
   File "C:\Test\liste-laufzeit.py", line 22, in ?
     r = re.sub(r"-(\d+-)+","-",r)
   File "C:\Programme\Python\lib\sre.py", line 143, in sub
     return _compile(pattern, 0).sub(repl, string, count)
RuntimeError: maximum recursion limit exceeded


Hier die Source für eigene Tests:

#Laufzeit-Test
import time, random, re, string

anzahl = 10000  #Anzahl der Zahleneintraege in Liste

#Zufallsliste ohne Wiederholung
random.seed(7)
l = range( 2*anzahl )
l = random.sample(xrange(2*anzahl), anzahl)
l.sort()
print "Anzahl", anzahl
#print l


#Frank Immich
starttime = time.clock()
r=""
mylist=[]
for c in xrange(len(l)-1):
         mylist.append(l[c])
         if l[c]+1 == l[c+1]:continue
         if len(mylist)==1:r=r+str(mylist[0])+ ","
         else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+","
         mylist=[]
mylist.append(l[len(l)-1])
if len(mylist)==1:r=r+str(mylist[0])+ ","
else:r=r + str(mylist[0]) +"-" + str(mylist[len(mylist)-1])+","
#print r
print "Laufzeit (Frank): %3.4f sec" % (time.clock() - starttime)

# kgm
starttime = time.clock()
l.append(l[-1]+2);
r=""
start = l[0]
last = start
for v in l:
     if v-last > 1:
         r += str(start)
         if last != start:
             r += "-" + str(last)
         r += ","
         start = v
     last = v
del l[-1] #append wieder aufheben
r = r[0:-1] #letzte Komma weg
#print r
print "Laufzeit (kgm): %3.4f sec" % (time.clock() - starttime)


# Jan Voges
starttime = time.clock()
r=""
for i in xrange(len(l)-1):
     if l[i+1] - l[i] == 1:   r += str(l[i])+"-"
     else:                    r += str(l[i])+","
r += str(l[-1])
#print r
r = re.sub(r"-(\d+-)+","-",r)
#print r
print "Laufzeit (Jan): %3.4f sec" % (time.clock() - starttime)


#Rene Liebscher
starttime = time.clock()
def y(list,element):
     if len(list) == 0:
         return [element]
     # Nachfolger von letzem in der liste
     if list[-1] == element-1:
         # liste erst angefangen oder irgendwas wie '... , x' drin
         if len(list)<2 or list[-2]==',':
             # anhaengen
             return list+['-',element]
         else:
             # letztes Element in Liste austauschen
             return list[:-1]+[element]
     else:
         # neues anhaengen
         return list+[',',element]

r = string.join(
     # die Zahlen muessen noch Strings werden
     map(str, reduce(y,l,[])
         ),"")
#print r
print "Laufzeit (Rene): %3.4f sec" % (time.clock() - starttime)

#ende


-- 
Mit freundlichen Grüßen
Klaus Meyer :-)