Seite 1 von 2

Problem mit summen in tupeln

Verfasst: Montag 11. Juni 2007, 11:25
von jo_hb
Hallo,
hat jemand ne idee wie ich das folgende mache? (Nein, ist keine Hausaufgabe, aber ich komm trotzdem nicht drauf... :)

ich habe eine Liste mit tupeln, etwa wie folgt:

Code: Alles auswählen

a = [ (4,4),
        (1,10),
        (7,7),
        (10,10)]
Und es sollen jetzt summen gebildet werden, und zwar so, dass immer wenn ein tupel (1,10) auftaucht beide varianten berechnet werden, also einmal +1, einmal +10 - im obigen Beispiel sollte also [22, 31] herrauskommen, wenn mehr (1, 10) tupel auftauchen sollen auch entsprechend mehr Summen rauskommen.

Gruss,
Jo

Verfasst: Montag 11. Juni 2007, 11:45
von thelittlebug
hi,

warscheinlich weiß blackjack noch ne schönere lösung :)
aber hier mal meine

Code: Alles auswählen

>>> a=[(4,4),(1,10),(7,7),(10,10)]
>>> (sum([x[0] for x in a]), sum(x[1] for x in a))
(22, 31)
>>> 

Verfasst: Montag 11. Juni 2007, 11:47
von BlackJack
Ein Anwendungsfall für `reduce()`:

Code: Alles auswählen

In [11]: a = [(4, 4), (1, 10), (7, 7), (10, 10)]

In [12]: reduce(lambda (a, b), (c, d): (a + c, b + d),
   ....:        a,
   ....:        (0, 0))
Out[12]: (22, 31)

Verfasst: Montag 11. Juni 2007, 11:48
von jo_hb
Blackjack, je genau, hehe...
Also vielen Dank, das sieht schon um einiges besser aus als meine bisherigen kläglichen Versuche, die nie unter 15 Zeilen kamen... :)

Jo

Verfasst: Montag 11. Juni 2007, 12:04
von mitsuhiko
Ein klarer Anwendungsfall für zip:

Code: Alles auswählen

>>> a = [(4,4),(1,10),(7,7),(10,10)]
>>> map(sum, zip(*a))
[22, 31]

Verfasst: Montag 11. Juni 2007, 12:53
von birkenfeld
Und jetzt benchmarken wir mal die zip-Lösung gegen die reduce-Lösung... ;)

Verfasst: Montag 11. Juni 2007, 12:55
von Michael Schneider
Hi Blackbird,

hätte ich auch gesagt. Aber da Du nicht darauf hinwiest, dass zip erst eine neue Liste erzeugt, was bei großen Teillisten immense Ressourcen frisst, warte ich auf eine entsprechende Bemerkung von Blacky (Blackjack). ^^

Grüße,
Michael

Verfasst: Montag 11. Juni 2007, 12:57
von Michael Schneider
birkenfeld hat geschrieben:Und jetzt benchmarken wir mal die zip-Lösung gegen die reduce-Lösung... ;)
... ok, Birkenfeld war schneller. :lol:

Michel

Verfasst: Montag 11. Juni 2007, 13:06
von EyDu
birkenfeld hat geschrieben:Und jetzt benchmarken wir mal die zip-Lösung gegen die reduce-Lösung... ;)
premature optimization is the root of all evil
;-)

Verfasst: Montag 11. Juni 2007, 13:26
von birkenfeld
Wenn ich von Haus aus den schnelleren Algorithmus nehme, ist das ja noch keine Optimierung...

Verfasst: Montag 11. Juni 2007, 13:40
von mitsuhiko

Code: Alles auswählen

reduce_method 2.22972607613
map_method 1.34840607643
imap_method 1.23970103264
sogar map ist schneller als reduce.

Verfasst: Montag 11. Juni 2007, 13:43
von birkenfeld
Ich hab nie gesagt, was ich nehmen würde... :)

Verfasst: Montag 11. Juni 2007, 14:05
von Y0Gi
Man könnte blackbirds Code auch mit izip und einer GE umsetzen.

Verfasst: Montag 11. Juni 2007, 14:10
von mitsuhiko
Jetzt wo's eh schon so absurd ist:

Code: Alles auswählen

from time import time
from itertools import izip, imap
from random import randrange

TESTDATA = [(randrange(100), randrange(100)) for x in range(500)]

def runtest(t):
    s = time()
    for x in xrange(10000):
        a, b = t(TESTDATA)
    return time() - s

def reduce_method(a):
    return reduce(lambda (a, b), (c, d): (a + c, b + d), a, (0, 0))

def map_method(a):
    return map(sum, zip(*a))

def imap_method(a):
    return imap(sum, izip(*a))

def izip_in_ge_method(a):
    return (sum(x) for x in izip(*a))

for name, test in sorted(locals().items()):
    if name.endswith('_method'):
        print name[:-7], runtest(test)
Ergibt:

Code: Alles auswählen

imap 1.37107610703
izip_in_ge 1.53157806396
map 1.60974383354
reduce 3.47407388687

Verfasst: Montag 11. Juni 2007, 14:19
von EyDu
birkenfeld hat geschrieben:Wenn ich von Haus aus den schnelleren Algorithmus nehme, ist das ja noch keine Optimierung...
Willst du damit sagen, dass du optimierst, ohne zu prüfen ob die Optimierung auch schneller ist ;-) ?

Verfasst: Montag 11. Juni 2007, 14:29
von mitsuhiko
EyDu hat geschrieben:Willst du damit sagen, dass du optimierst, ohne zu prüfen ob die Optimierung auch schneller ist ;-) ?
Das muss man nicht prüfen, das kann man mit der Zeit riechen :D

Verfasst: Montag 11. Juni 2007, 16:23
von birkenfeld
Nein, das will ich nicht...

Verfasst: Montag 11. Juni 2007, 20:58
von jo_hb
Hallo nochmal,
also vielen Dank, aber ihr habt euch so in eure Optimierung verstrickt dass ihr ganz übersehen habt dass keine der Möglichkeiten mein Problem löst... :)
Aber ihr habt sicher nichts dagegen wenn's noch ein bisschen komplizierter wird...
wenn mehr (1, 10) tupel auftauchen sollen auch entsprechend mehr Summen rauskommen.
Also damit meine ich, wenn die Liste am Anfang zB so aussieht:

Code: Alles auswählen

a = [(4,4),
       (1,10),
       (7,7),
       (10,10),
       (1,10)]
soll die Lösung so aussehen:

Code: Alles auswählen

[23, 32, 41]
Um das Prinzip nochmal zu verdeutlichen:

Code: Alles auswählen

[(1,10)]		      # ---> [1, 10]
[(1,10),(1,10)]		   # ---> [2, 11, 20]
[(1,10),(1,10),(1,10)]	# ---> [3, 12, 21, 30]
# etc.
Gruss,
Jo

Verfasst: Montag 11. Juni 2007, 22:00
von BlackJack
Vielleicht liegt's an der Hitze, aber ich verstehe die Bildungsvorschrift nicht. :?:

Verfasst: Dienstag 12. Juni 2007, 07:09
von Michael Schneider
jo_hb hat geschrieben: Also damit meine ich, wenn die Liste am Anfang zB so aussieht:

Code: Alles auswählen

a = [(4,4),
       (1,10),
       (7,7),
       (10,10),
       (1,10)]
soll die Lösung so aussehen:

Code: Alles auswählen

[23, 32, 41]
Um das Prinzip nochmal zu verdeutlichen:

Code: Alles auswählen

[(1,10)]		      # ---> [1, 10]
[(1,10),(1,10)]		   # ---> [2, 11, 20]
[(1,10),(1,10),(1,10)]	# ---> [3, 12, 21, 30]
# etc.
:shock:
Moin,

ich hab die Vorschrift:

Code: Alles auswählen

[(1,10),(1,10)]		   # ---> (1,  10)
Durchgang 1: Erweitern     #  (1,   0, 10)
Durchgang 2: Plus (1, 0)   #   (2,   1, 10)
Durchgang 3: Plus (0, 10) #   (2, 11, 20)
Nur, warum das Tupel erweitert wird, ist mir aus Jos Erklärung nicht erkennbar. Denn wenn man nur einfach die Elemente einzeln addiert, dann ergäbe sich (1+1+10, 10+1+10) = (12, 21). Sieht ein wenig aus wie Binomische Formeln der Addition. :lol:
Wie auch immer, mit der obigen Regel sollte Jo das jetzt in einen Pythonausdruck bringen können.

Viel Spaß,
Michael