Positive und negative Zahlen aus Liste separat addieren

[Sirius3]

PyPy liefert Ergebnisse die wesentlich näher sind an dem was man erwarten würde.

Die Frage ist, was würde man erwarten?

Wie viel Zeit kostet
1. das Vergleichen zweier Zahlen
2. das Durchlaufen einer Liste
3. das Erstellen von Tupeln
4. das Aufrufen einer Filter-Funktion

Ich hab mal nach Kosten sortiert, wobei ein Funktionsaufruf am teuersten ist.
Damit ist die with_filter-Methode weit abgeschlagen, da 1,2 und 4 jeweils zweifach
ausgeführt wird.
Stellt sich noch die Frage ist 1+2+3 oder 2*(1+2) größer?

Das pypy-Ergebnis verwundert mich.

Code: Alles auswählen

  mov ecx, count
  mov esi, offset kassa
  xor ebx,ebx
  xor edx,edx
@loop:
  lodsd
  or eax,eax
  jns @p
  add ebx,eax
  jmp @g
@p:
  add edx,eax
@g:
  loop @loop

[Sirius3]

Warum unbedingt ein Einzeiler? Was die Anzahl der Zeichen betrifft,
Geschwindigkeit, usw:

Code: Alles auswählen

result = [0, 0]
for n in kassa:
    result[n<0] += n

[snafu]

Warum unbedingt ein Einzeiler? Was die Anzahl der Zeichen betrifft,
Geschwindigkeit, usw:

Code: Alles auswählen

result = [0, 0]
for n in kassa:
    result[n<0] += n

Schon witzig, dass die Lösung ohne den ganzen "funktionalen Kram" die beste Performance zeigt. Zudem ist sie relativ kurz, wirkt elegant und auch nicht zu komplex. Damit ist sie für mich persönlich der Sieger.

[/me]

Code: Alles auswählen

result = [0, 0]
for n in kassa:
    result[n<0] += n

Das kann ja jeder.

Für mich ist es aber definitiv die übersichtlichste Lösung.

[mutetella]

Code: Alles auswählen

result = [0, 0]
for n in kassa:
    result[n<0] += n

Echt super schön! Da hat man gleich am morgen ein Lächeln im Gesicht...

mutetella

[kbr]

Code: Alles auswählen

result = [0, 0]
for n in kassa:
    result[n<0] += n

Mein Favorit wäre dies:

Code: Alles auswählen

p = sum(i for i in kassa if i > 0)
n = sum(kassa) - p

Läuft auch ähnlich schnell.

[mutetella]

Ach nö, Schatz, lass gut sein, mein Tag war heute furchtbar anstrengend...:

Code: Alles auswählen

import random
import sys
import time

if sys.version.startswith('3'):
    from functools import reduce
else:
    range = xrange

numbers = list(range(100000)) + list(range(-100000, 0))
random.shuffle(numbers)

def with_filter():
    t = time.time()
    sum(filter(lambda e: e > 0, numbers))
    sum(filter(lambda e: e < 0, numbers))
    return time.time() - t

def with_map():
    t = time.time()
    map(sum, zip(*((0, item) if item < 0 else (item, 0) for 
                   item in numbers)))
    return time.time() - t

def with_lc():
    t = time.time()
    sum(i for i in numbers if i<0)
    sum(i for i in numbers if i>0)
    return time.time() - t

def with_reduce():
    t = time.time()
    reduce(lambda pos_neg, next: (pos_neg[0] + next, pos_neg[1]) if
                  next >= 0 else (pos_neg[0], pos_neg[1] + next), 
                  numbers, (0, 0))
    return time.time() - t

def with_sub():
    t = time.time()
    p = sum(i for i in numbers if i > 0)
    sum(numbers) - p
    return time.time() - t

def with_for():
    t = time.time()
    result = [0, 0]
    for n in numbers:
        result[n<0] += n
    return time.time() - t

def start_test(count):
    t_filter, t_map, t_lc, t_reduce, t_sub, t_for = 0, 0, 0, 0, 0, 0
    for i in range(count):
        t_filter += with_filter()
        t_map += with_map()
        t_lc += with_lc()
        t_reduce += with_reduce()
        t_sub += with_sub()
        t_for += with_for()
    print ('filter: {0}\n'
           'map   : {1}\n'
           'lc    : {2}\n'
           'reduce: {3}\n'
           'sub   : {4}\n'
           'for   : {5}'.format(t_filter / count,
                                t_map / count,
                                t_lc / count, 
                                t_reduce / count, 
                                t_sub / count,
                                t_for / count))

if __name__ == '__main__':
    start_test(int(sys.argv[1]))

Python 2.6.6

Code: Alles auswählen

$ python ./measure_sum.py 100
filter: 0.0847445440292
map   : 0.523688633442
lc    : 0.0519872546196
reduce: 0.0740648984909
sub   : 0.0361274647713
for   : 0.0377649760246

Python 3.3.0

Code: Alles auswählen

python3 ./measure_sum.py 100
filter: 0.10626415252685546
map   : 0.3320684552192688
lc    : 0.06279780626296998
reduce: 0.08097020864486694
sub   : 0.04472310304641724
for   : 0.04908294916152954

Python 3 scheint tendenziell langsamer zu sein...

mutetella

[BlackJack]

@mutetella: Ich traue solchen Ergebnissen nicht unbedingt, weil ich die Rahmenbedingungen nicht kenne und nicht weiss in wie weit sich der Tester Gedanken darüber gemacht hat. Das fängt in diesem Fall beim händischen `time()` an. Ob man `clock()` oder `time()` nehmen sollte, hängt vom Betriebssystem ab. Das heisst Dein Code auf dem „falschen” Betriebssystem ausgeführt liefert keine vergleichbaren Ergebnisse. Unter anderem deswegen gibt es ja extra das `timeit`-Modul in der Standardbibliothek, was einen vor ein paar gängigen Fehlern bei solchen Messungen bewahren kann.

Eine weitere Sache: Du scheinst das nur einmal aufzurufen. Wenn man so etwas mehrfach laufen lässt, findet man manchmal erstaunliche Abweichungen zwischen den einzelnen Läufen. Manchmal auch nicht so Erstaunliche: Wenn Du den Test öfter in einer Schleife aufrufst, würde es mich nicht wundern wenn er schneller wird. Moderne Systeme takten den Prozessor oft nach Bedarf hoch und runter. Das kann Ergebnisse verfälschen wenn die ersten Varianten noch mit langsamen Prozessor und die letzten mit Hochgetaktetem gefahren werden.

[snafu]

Und es kommt auch auf den Interpreter an. Mit PyPy sind nämlich "for" (das mit den zwei Listen) und "reduce" die mit Abstand führenden.

[mutetella]

... Du scheinst das nur einmal aufzurufen. ...

Nö, jeweils 100 mal.

Wegen 'time()' vs 'clock()' vs 'timeit': Das leuchtet mir wohl ein, auffallend finde ich halt, dass nicht nur das eine oder andere sondern sämtliche Ergebnisse unter Py3 etwas langsamer durchlaufen werden.
Und zumindest in meinem Alter erwartet man doch, dass neuer immer auch schneller ist...

mutetella

[kbr]

Vielleicht noch ein Hinweis zur Performance-Messung auf Multitasking-Systemen: Bei mehreren Messungen ist nicht der Mittelwert zu bilden, sondern der Minimalwert beschreibt am ehesten die Performance des getesteten Codes.
Bei anderen Vergleichen zwischen Python 2.7 und 3.3 habe ich aber auch beobachtet, dass 3.3 meistens etwas behäbiger daher kommt (wie man selbst auch, wenn man älter wird ).

[BlackJack]

@mutetella: Da wird 100 mal die Schleife durchlaufen, aber es kommt am Ende trotzdem nur ein Ergebnis pro Variante heraus. Man kann also nicht erkennen wie gross eventuelle Schwankungen sind, und ob und wo vielleicht der Prozessor hochgetaktet wurde. Bei solchen „Mikro”-Zeitmessungen nehme ich immer `timeit` und rufe das von der Shell so oft in einer Schleife auf, dass ich sicher sein kann, dass ich mindestens 5 Messergebnisse mit einem voll „aufgeweckten” Prozessor bekomme.

[DasIch]

Timeit hilft aber auch nicht wenn der Algorithmus immer mit den gleichen Werte aufgerufen wird, da dass Optimationen erlaubt die in "echtem" Code nicht greifen würden.

[Sirius3]

Um die Liste der Funktionen, die aufgerufen werden, nicht immer länger anwachsen zu lassen:

Code: Alles auswählen

def start_test(count):
    functions = [func for name,func in globals().iteritems() if name.startswith('with_')]
    times = [0]*len(functions)
    for i in range(count):
        for idx, func in enumerate(functions):
            times[idx] += func()
    print '\n'.join('{0:6s}: {1}'.format(func.__name__.lstrip('with_'),t/count) for t,func in zip(times,functions))

Der Name start_test ist auch etwas irreführend. da der Test gestartet durchgeführt und beendet wird.

[jerch]

Bei mir ist tatsächlich die Problembär-Variante die Schnellste

Code: Alles auswählen

>>> def neg_pos(it):
...   n, p = 0, 0
...   for el in it:
...     if el<0:
...       n += el
...     else:
...       p += el
...   return n, p

[mutetella]

Code: Alles auswählen

def start_test(count=5, repeat=3):
    functions = [func for name, func in globals().items() if 
                 name.startswith('with_')]
    result = {}
    timer = time.time
    for func in functions:
        import_ = 'from __main__ import {0}'.format(func.__name__)
        func_ = '{0}()'.format(func.__name__)
        results = timeit.repeat(stmt=func_, setup=import_, timer=timer, 
                                repeat=repeat, number=count)
        result[func.__name__] = min(results), max(results)
    result = sorted(result.items(), key=lambda e: e[0])
    print('{0} repetitions of {1} runs:'.format(repeat, count))
    print('\t\tmin\t\tmax')
    for func, times in result:
        print('{func}:\t{times[0]:f}\t{times[1]:f}'.format(times=times, 
                                                           func=func))

if __name__ == '__main__':
    args = map(int, sys.argv[1:3])
    start_test(*args)

Python 2.6.6

Code: Alles auswählen

$ python ./measure_sum.py 10 5
5 repetitions of 10 runs:
             min         max
with_filter: 0.856682    0.864453
with_for:    0.387800    0.404242
with_ifelse: 0.282156    0.295538
with_lc:     0.529992    0.540703
with_map:    1.683503    1.728494
with_reduce: 0.761827    0.793188
with_sub:    0.369928    0.388947

Python 3.3.0

Code: Alles auswählen

$ python3 ./measure_sum.py 10 5
5 repetitions of 10 runs:
             min         max
with_filter: 1.111608    1.166339
with_for:    0.493963    0.498310
with_ifelse: 0.407400    0.417205
with_lc:     0.630200    0.632272
with_map:    1.335373    1.345122
with_reduce: 0.807354    0.809970
with_sub:    0.453200    0.454332

Auf BlackJacks Einwand hin hab' ich noch Wiederholungen eingebaut. Auch wenn es abhängig vom OS, vom Rechner und Dingen, die sich mir nicht erschließen sicher Schwankungen gibt: Tendenziell arbeitet Python 3 in dieser Disziplin langsamer.

Der Name start_test ist auch etwas irreführend. da der Test gestartet durchgeführt und beendet wird.

Ich will einfach auch mal etwas entwickelt haben, das sowas wie einen "Start"-Button hat...
Wer weiß? Soll Leute geben, die damit Milliarden verdient haben...

mutetella