Inefficient summing

[Bruno Desthuilliers]

beginner a écrit :

Hi All,

I have a list of records like below:

rec=[{"F1":1, "F2":2}, {"F1":3, "F2":4} ]

Now I want to write code to find out the ratio of the sums of the two
fields.

One thing I can do is:

sum(r["F1"] for r in rec)/sum(r["F2"] for r in rec)

But this is slow because I have to iterate through the list twice.
Also, in the case where rec is an iterator, it does not work.

I can also do this:

sum1, sum2= reduce(lambda x, y: (x[0]+y[0], x[1]+y[1]), ((r["F1"],
r["F2"]) for r in rec))
sum1/sum2

This loops through the list only once, and is probably more efficient,
but it is less readable.

I can of course use an old-fashioned loop. This is more readable, but
also more verbose.

What is the best way, I wonder?

The best way is the one that give you the correct answer while being
fast enough - for a definition of 'fast enough' that is highly
project-specific - and still readable - for a definition of 'readable'
that may be somehow subjective, but clearly favours a plain for loop
over your 'I can also do this' snippet.

 

[beginner]

Hi All,

I have a list of records like below:

rec=[{"F1":1, "F2":2}, {"F1":3, "F2":4} ]

Now I want to write code to find out the ratio of the sums of the two
fields.

One thing I can do is:

sum(r["F1"] for r in rec)/sum(r["F2"] for r in rec)

But this is slow because I have to iterate through the list twice.
Also, in the case where rec is an iterator, it does not work.

I can also do this:

sum1, sum2= reduce(lambda x, y: (x[0]+y[0], x[1]+y[1]), ((r["F1"],
r["F2"]) for r in rec))
sum1/sum2

This loops through the list only once, and is probably more efficient,
but it is less readable.

I can of course use an old-fashioned loop. This is more readable, but
also more verbose.

What is the best way, I wonder?


-a new python programmer

 

[Chris Rebert]

I personally would probably do:

from collections import defaultdict

label2sum = defaultdict(lambda: 0)
for r in rec:
for key, value in r.iteritems():
label2sum[key] += value

ratio = label2sum["F1"] / label2sum["F2"]

This iterates through each 'r' only once, and (imho) is pretty
readable provided you know how defaultdicts work. Not everything has
to unnecessarily be made a one-liner. Coding is about readability
first, optimization second. And optimized code should not be
abbreviated, which would make it even harder to understand.

I probably would have gone with your second solution if performance
was no object.

Cheers,
Chris

 

[bearophileHUGS]

beginner:

I can of course use an old-fashioned loop. This is more readable, but
also more verbose.
What is the best way, I wonder?

In such situation the old loop seems the best solution. Short code is
good only when it doesn't make the code too much slow/difficult to
understand. Keeping the code quite readable is very important. So I
think a simple solution is the best in this situation. The following
code can be understood quickly:

records = [{"F1": 1, "F2": 2}, {"F1": 3, "F2": 4}]

f1sum, f2sum = 0, 0
for rec in records:
f1sum += rec["F1"]
f2sum += rec["F2"]
ratio = f1sum / float(f2sum)
print ratio

Output:
0.666666666667

Note that I allowed myself to use this line of code:
f1sum, f2sum = 0, 0
because the two values on the right are equal, so you don't need one
bit of brain to understand where each value goes

You can of course generalize the code in various ways, for example:

keys = ["F1", "F2"]
totals = [0] * len(keys)

for rec in records:
for i, key in enumerate(keys):
totals += rec[key]

ratio = totals[0] / float(totals[1])
print ratio

But that already smells of over-engineering. Generally it's better to
use the simpler solution that works in all your cases at a speed that
is acceptable for you (my variant of the KISS principle).

Bye,
bearophile

 

[Matt Nordhoff]

I personally would probably do:

from collections import defaultdict

label2sum = defaultdict(lambda: 0)

FWIW, you can just use:

label2sum = defaultdict(int)

You don't need a lambda.

for r in rec:
for key, value in r.iteritems():
label2sum[key] += value

ratio = label2sum["F1"] / label2sum["F2"]

This iterates through each 'r' only once, and (imho) is pretty
readable provided you know how defaultdicts work. Not everything has
to unnecessarily be made a one-liner. Coding is about readability
first, optimization second. And optimized code should not be
abbreviated, which would make it even harder to understand.

I probably would have gone with your second solution if performance
was no object.

Cheers,
Chris

--

 

[bieffe62]

Hi All,

I have a list of records like below:

rec=[{"F1":1, "F2":2}, {"F1":3, "F2":4} ]

Now I want to write code to find out the ratio of the sums of the two
fields.

One thing I can do is:

sum(r["F1"] for r in rec)/sum(r["F2"] for r in rec)

But this is slow because I have to iterate through the list twice.
Also, in the case where rec is an iterator, it does not work.

I can also do this:

sum1, sum2= reduce(lambda x, y: (x[0]+y[0], x[1]+y[1]), ((r["F1"],
r["F2"]) for r in rec))
sum1/sum2

This loops through the list only once, and is probably more efficient,
but it is less readable.

I can of course use an old-fashioned loop. This is more readable, but
also more verbose.

What is the best way, I wonder?

-a new python programmer

The loop way is probably the right choice.
OTHA, you could try to make more readable the 'reduce' approach,
writing it like this:

def add_r( sums, r ): return sums[0]+r['F1'], sums[1]+r['F2']
sum_f1, sum_f2 = reduce( add_r, rec, (0,0) )
result = sum_f1/sum_f2

Less verbose than the for loop, but IMO almost as understandable : one
only needs to know the semantic
of 'reduce' (which for a python programmer is not big thing) and most
important the code does only one thing per line.


Ciao

 

[bearophileHUGS]

FB:

def add_r( sums, r ): return sums[0]+r['F1'], sums[1]+r['F2']
sum_f1, sum_f2 = reduce( add_r, rec, (0,0) )
result = sum_f1/sum_f2

Until this feature vanishes I think it's better to use it (untested):

add_r = lambda (a, b), r: (a + r['F1'], b + r['F2'])

Bye,
bearophile

 

[Terry Reedy]

FWIW, you can just use:

label2sum = defaultdict(int)

You don't need a lambda.

Indeed, in this case, with two known keys, the defaultdict is not needed
either, since the following should work as well to initialize

label2sum = {'F1':0,'F2':0}

for r in rec:
for key, value in r.iteritems():
label2sum[key] += value

ratio = label2sum["F1"] / label2sum["F2"]

 

[Alexander Schmolck]

Hi All,

I have a list of records like below:

rec=[{"F1":1, "F2":2}, {"F1":3, "F2":4} ]

Now I want to write code to find out the ratio of the sums of the two
fields.

One thing I can do is:

sum(r["F1"] for r in rec)/sum(r["F2"] for r in rec)

But this is slow because I have to iterate through the list twice.
Also, in the case where rec is an iterator, it does not work.

how about:


ratio = (lambda c: c.real/c.imag)(sum(complex(r["F1"], r["F2"] for r in rec)))

?

 

[beginner]

Hi All,

I have a list of records like below:

rec=[{"F1":1, "F2":2}, {"F1":3, "F2":4} ]

Now I want to write code to find out the ratio of the sums of the two
fields.

One thing I can do is:

sum(r["F1"] for r in rec)/sum(r["F2"] for r in rec)

But this is slow because I have to iterate through the list twice.
Also, in the case where rec is an iterator, it does not work.

how about:

ratio = (lambda c: c.real/c.imag)(sum(complex(r["F1"], r["F2"] for r in rec)))

?

- Hide quoted text -

- Show quoted text -

Neat, but I will have a problem if I am dealing with three fields,
right?

 

[Alexander Schmolck]

how about:

ratio = (lambda c: c.real/c.imag)(sum(complex(r["F1"], r["F2"] for r in rec)))

Neat, but I will have a problem if I am dealing with three fields,
right?

Sure but then how often do you want to take the ratio of 3 numbers?

More seriously if you often find yourself doing similar operations and are
(legimately) worried about performance, numpy and pytables might be worth a
look. By "legitimately" I mean that I wouldn't be bothered by iterating twice
over rec; it doesn't affect the algorithmic complexity at all and I woudn't be
surprised if sum(imap(itemgetter("F1"),rec))/sum(imap(itemgetter("F2"),rec))
weren't faster than the explicit loop version for the cases you care about
(timeit will tell you). You're right that you loose some generality in not
being able to deal with arbitrary iterables in that case though.

'as