Need a fast way to count and sum an iterable in a single pass

Question

Can any one help me? I'm trying to come up with a way to compute

>>> sum_widths = sum(col.width for col in cols if not col.hide)

and also count the number of items in this sum, without having to make two passes over cols.

It seems unbelievable but after scanning the std-lib (built-in functions, itertools, functools, etc), I couldn't even find a function which would count the number of members in an iterable. I found the function itertools.count, which sounds like what I want, but It's really just a deceptively named range function.

After a little thought I came up with the following (which is so simple that the lack of a library function may be excusable, except for its obtuseness):

>>> visable_col_count = sum(col is col for col in cols if not col.hide)

However, using these two functions requires two passes of the iterable, which just rubs me the wrong way.

As an alternative, the following function does what I want:

>>> def count_and_sum(iter):
>>>     count = sum = 0
>>>     for item in iter:
>>>         count += 1
>>>         sum += item
>>>     return count, sum

The problem with this is that it takes 100 times as long (according to timeit) as the sum of a generator expression form.

If anybody can come up with a simple one-liner which does what I want, please let me know (using Python 3.3).

Edit 1

Lots of great ideas here, guys. Thanks to all who replied. It will take me a while to digest all these answers, but I will and I will try to pick one to check.

Edit 2

I repeated the timings on my two humble suggestions (count_and_sum function and 2 separate sum functions) and discovered that my original timing was way off, probably due to an auto-scheduled backup process running in the background.

I also timed most of the excellent suggestions given as answers here, all with the same model. Analysing these answers has been quite an education for me: new uses for deque, enumerate and reduce and first time for count and accumulate. Thanks to all!

Here are the results (from my slow netbook) using the software I'm developing for display:

┌───────────────────────────────────────────────────────┐
│                 Count and Sum Timing                  │
├──────────────────────────┬───────────┬────────────────┤
│          Method          │Time (usec)│Time (% of base)│
├──────────────────────────┼───────────┼────────────────┤
│count_and_sum (base)      │        7.2│            100%│
│Two sums                  │        7.5│            104%│
│deque enumerate accumulate│        7.3│            101%│
│max enumerate accumulate  │        7.3│            101%│
│reduce                    │        7.4│            103%│
│count sum                 │        7.3│            101%│
└──────────────────────────┴───────────┴────────────────┘

(I didn't time the complex and fold methods as being just too obscure, but thanks anyway.)

Since there's very little difference in timing among all these methods I decided to use the count_and_sum function (with an explicit for loop) as being the most readable, explicit and simple (Python Zen) and it also happens to be the fastest!

I wish I could accept one of these amazing answers as correct but they are all equally good though more or less obscure, so I'm just up-voting everybody and accepting my own answer as correct (count_and_sum function) since that's what I'm using.

What was that about "There should be one-- and preferably only one --obvious way to do it."?

Answer 1

Thanks for all the great answers, but I decided to use my original count_and_sum function, called as follows:

>>> cc, cs = count_and_sum(c.width for c in cols if not c.hide) 

As explained in the edits to my original question this turned out to be the fastest and most readable solution.

Answer 2

Something else to consider: If it is possible to determine a minimum possible count, we can let the efficient built-in sum do part of the work:

from itertools import islice

def count_and_sum(iterable):
    # insert favorite implementation here

def count_and_sum_with_min_count(iterable, min_count):
    iterator = iter(iterable)
    slice_sum = sum(islice(iterator, None, min_count))
    rest_count, rest_sum = count_and_sum(iterator)
    return min_count + rest_count, slice_sum + rest_sum

For example, using the deque method with a sequence of 10000000 items and min_count of 5000000, timing results are:

count_and_sum: 1.03
count_and_sum_with_min_count: 0.63

Answer 3

You might only need the sum & count today, but who knows what you'll need tomorrow!

Here's an easily extensible solution:

def fold_parallel(itr, **fs):
    res = {
        k: zero for k, (zero, f) in fs.items()
    }

    for x in itr:
        for k, (_, f) in fs.items():
            res[k] = f(res[k], x)

    return res

from operator import add

print(fold_parallel([1, 2, 3],
    count = (0, lambda a, b: a + 1),
    sum = (0, add),
))
# {'count': 3, 'sum': 6}

Answer 4

Here's some timing data that might be of interest:

import timeit

setup = '''
import random, functools, itertools, collections

x = [random.randint(0, 10) for _ in range(10**5)]

def count_and_sum(it):
    c, s = 0, 0
    for i in it:
        c += 1
        s += i
    return c, s

def two_pass(it):
    return sum(i for i in it), sum(True for i in it)

def functional(it):
    return functools.reduce(lambda pair, x: (pair[0]+1, pair[1]+x), it, [0, 0])

def accumulator(it):
    return max(enumerate(itertools.accumulate(it), 1))

def complex(it):
    cpx = sum(x + 1j for x in it)
    return cpx.real, int(cpx.imag)

def dequed(it):
    return collections.deque(enumerate(itertools.accumulate(it), 1), maxlen=1)

'''

number = 100
for stmt in ['count_and_sum(x)',
             'two_pass(x)',
             'functional(x)',
             'accumulator(x)',
             'complex(x)',
             'dequed(x)']:
    print('{:.4}'.format(timeit.timeit(stmt=stmt, setup=setup, number=number)))

Result:

3.404 # OP's one-pass method
3.833 # OP's two-pass method
8.405 # Timothy Shields's fold method
3.892 # DSM's accumulate-based method
4.946 # 1_CR's complex-number method
2.002 # M4rtini's deque-based modification of DSM's method

Given these results, I'm not really sure how the OP is seeing a 100x slowdown with the one-pass method. Even if the data looks radically different from a list of random integers, that just shouldn't happen.

Also, M4rtini's solution looks like the clear winner.

---

To clarify, these results are in CPython 3.2.3. For a comparison to PyPy3, see James_pic's answer, which shows some serious gains from JIT compilation for some methods (also mentioned in a comment by M4rtini.

Answer 5

As a follow-up to senshin's answer, it's worth noting that the performance differences are largely due to quirks in CPython's implementation, that make some methods slower than others (for example, for loops are relatively slow in CPython). I thought it would be interesting to try the exact same test in PyPy (using PyPy3 2.1 beta), which has different performance characteristics. In PyPy the results are:

0.6227 # OP's one-pass method
0.8714 # OP's two-pass method
1.033 # Timothy Shields's fold method
6.354 # DSM's accumulate-based method
1.287 # 1_CR's complex-number method
3.857 # M4rtini's deque-based modification of DSM's method

In this case, the OP's one-pass method is fastest. This makes sense, as it's arguably the simplest (at least from a compiler's point of view) and PyPy can eliminate many of the overheads by inlining method calls, which CPython can't.

For comparison, CPython 3.3.2 on my machine give the following:

1.651 # OP's one-pass method
1.825 # OP's two-pass method
3.258 # Timothy Shields's fold method
1.684 # DSM's accumulate-based method
3.072 # 1_CR's complex-number method
1.191 # M4rtini's deque-based modification of DSM's method

Answer 6

1_CR's complex number solution is cute but overly hacky. The reason it works is that a complex number is a 2-tuple, that sums elementwise. The same is true of numpy arrays and I think it's slightly cleaner to use those:

import numpy as np
z = [1, 2, 4, 5, 6]
y = sum(np.array([x, 1]) for x in z)
sum_z, count_z = y[0], y[1]
print sum_z, count_z
18 5

Answer 7

Adaption of DSM's answer. using deque(... maxlen=1) to save memory use.

import itertools 
from collections import deque 
deque(enumerate(itertools.accumulate(x), 1), maxlen=1)

timing code in ipython:

import itertools , random
from collections import deque 

def count_and_sum(iter):
     count = sum = 0
     for item in iter:
         count += 1
         sum += item
     return count, sum

X = [random.randint(0, 10) for _ in range(10**7)]
%timeit count_and_sum(X)
%timeit deque(enumerate(itertools.accumulate(X), 1), maxlen=1)
%timeit (max(enumerate(itertools.accumulate(X), 1)))

results: now faster than OP's method

1 loops, best of 3: 1.08 s per loop
1 loops, best of 3: 659 ms per loop
1 loops, best of 3: 1.19 s per loop

Answer 8

How about this? It seems to work.

from functools import reduce

class Column:
    def __init__(self, width, hide):
        self.width = width
        self.hide = hide

lst = [Column(10, False), Column(100, False), Column(1000, True), Column(10000, False)]

print(reduce(lambda acc, col: Column(col.width + acc.width, False) if not col.hide else acc, lst, Column(0, False)).width)

Answer 9

You can use this:

from itertools import count

lst = range(10)
c = count(1)
tot = sum(next(c) and x for x in lst if x % 2)
n = next(c)-1
print(n, tot)

# 5 25

It's kind of a hack, but it works perfectly well.

Answer 10

Using complex numbers

z = [1, 2, 4, 5, 6]
y = sum(x + 1j for x in z)
sum_z, count_z = y.real, int(y.imag)
print sum_z, count_z
18.0 5

Answer 11

You can keep count inside the sum with tricks similar to this

>>> from itertools import count
>>> cnt = count()
>>> sum((next(cnt), x)[1] for x in range(10) if x%2)
25
>>> next(cnt)
5

But it's probably going to be more readable to just use a for loop

Answer 12

I don't know about speed, but this is kind of pretty:

>>> from itertools import accumulate
>>> it = range(10)
>>> max(enumerate(accumulate(it), 1))
(10, 45)

Answer 13

I don't know what the Python syntax is off hand, but you could potentially use a fold. Something like this:

(count, total) = fold((0, 0), lambda pair, x: (pair[0] + 1, pair[1] + x))

The idea is to use a seed of (0,0) and then at each step add 1 to the first component and the current number to the second component.

For comparison, you could implement sum as a fold as follows:

total = fold(0, lambda t, x: t + x)