Summing a 2D list
Karsten Heymann
karsten.heymann at blue-cable.net
Fri Jun 13 08:12:40 EDT 2008
Hi Mark,
Mark <markjturner at gmail.com> writes:
> I have a scenario where I have a list like this:
>
> User Score
> 1 0
> 1 1
> 1 5
> 2 3
> 2 1
> 3 2
> 4 3
> 4 3
> 4 2
>
> And I need to add up the score for each user to get something like
> this:
>
> User Score
> 1 6
> 2 4
> 3 2
> 4 8
>
> Is this possible? If so, how can I do it? I've tried looping through
> the arrays and not had much luck so far.
Although your problem has already been solved, I'd like to present a
different approach which can be quite a bit faster. The most common
approach seems to be using a dictionary:
summed_up={}
for user,vote in pairs:
if summed_up.has_key(user):
summed_up[user]+=vote
else:
summed_up[user]=vote
But if the list of users is compact and the maximum value is known
before, the using a list and coding the user into the list position is
much more elegant:
summed_up=list( (0,) * max_user )
for user,vote in pairs:
summed_up[user] += vote
I've run a quick and dirty test on these approaches and found that the
latter takes only half the time than the first. More precisely, with
about 2 million pairs, i got:
* dict approach: 2s
(4s with "try: ... except KeyError:" instead of the "if")
* list approach: 0.9s
BTW this was inspired by the book "Programming Pearls" I read some
years ago where a similar approach saved some magnitudes of time
(using a bit field instead of a list to store reserved/free phone
numbers IIRC).
Yours,
Karsten
More information about the Python-list
mailing list