Count occurences of all items of a list in a tuple

Question

I have a tuple (1,5,2,3,4,5,6,7,3,2,2,4,3) and a list [1,2,3] and now want to count how often all items of the list occur in the tuple (so it should return 7).

I could loop the list, count each item in the tuple and then sum up the results, but I bet there is a better possibility in python.

Thats not a duplicate of How to count the occurrences of a list item? because I explicitly said that I am not just asking for list.count(item_of_list) (that would need to be done in a loop) but for a better method.

Answer 1

Being NumPy tagged, here's a NumPy solution -

In [846]: import numpy as np

In [847]: t = (1,5,2,3,4,5,6,7,3,2,2,4,3)

In [848]: a = [1,2,3]

In [849]: np.in1d(t,a).sum()
Out[849]: 7

# Alternatively with np.count_nonzero for summing booleans
In [850]: np.count_nonzero(np.in1d(t,a))
Out[850]: 7

Another NumPy one with np.bincount for the specific case of positive numbered elements in the inputs, basically using the numbers as bins, then doing bin based summing, indexing into those with the list elements to get the counts and a final summation for the final output -

In [856]: np.bincount(t)[a].sum()
Out[856]: 7

Other approaches -

from collections import Counter
# @Brad Solomon's soln
def collections_counter(tgt, tup):
    counts = Counter(tup)
    return sum(counts[t] for t in tgt)

# @timgeb's soln
def set_sum(l, t):
    l = set(l)
    return sum(1 for x in t if x in l)

# @Amit Tripathi's soln
def dict_sum(l, t):
    dct = {}
    for i in t:
        if not dct.get(i):
            dct[i] = 0
        dct[i] += 1
    return sum(dct.get(i, 0) for i in l)

Runtime tests

Case #1 : Timings on a tuple with 10,000 elements and with a list of 100 random elements off it -

In [905]: a = np.random.choice(1000, 100, replace=False).tolist()

In [906]: t = tuple(np.random.randint(1,1000,(10000)))

In [907]: %timeit dict_sum(a, t)
     ...: %timeit set_sum(a, t)
     ...: %timeit collections_counter(a, t)
     ...: %timeit np.in1d(t,a).sum()
     ...: %timeit np.bincount(t)[a].sum()
100 loops, best of 3: 2 ms per loop
1000 loops, best of 3: 437 µs per loop
100 loops, best of 3: 2.44 ms per loop
1000 loops, best of 3: 1.18 ms per loop
1000 loops, best of 3: 503 µs per loop

set_sum from @timgeb's soln looks quite efficient for such inputs.

Case #2 : Timings on a tuple with 100,000 elements that has 10,000 unique elements and with a list of 1000 unique random elements off it -

In [916]: t = tuple(np.random.randint(0,10000,(100000)))

In [917]: a = np.random.choice(10000, 1000, replace=False).tolist()

In [918]: %timeit dict_sum(a, t)
     ...: %timeit set_sum(a, t)
     ...: %timeit collections_counter(a, t)
     ...: %timeit np.in1d(t,a).sum()
     ...: %timeit np.bincount(t)[a].sum()
10 loops, best of 3: 21.1 ms per loop
100 loops, best of 3: 5.33 ms per loop
10 loops, best of 3: 24.2 ms per loop
100 loops, best of 3: 13.4 ms per loop
100 loops, best of 3: 5.05 ms per loop

Answer 2

Define a set of your target values (for the O(1) membership-test) and combine the sum builtin with a generator expression.

>>> t = (1,5,2,3,4,5,6,7,3,2,2,4,3)
>>> l = [1,2,3]
>>> l = set(l)
>>> 
>>> sum(1 for x in t if x in l)
7

Answer 3

With collections.Counter:

from collections import Counter
tup = (1,5,2,3,4,5,6,7,3,2,2,4,3)
tgt = [1, 2, 3]
counts = Counter(tup)
sum(counts[t] for t in tgt)
# 7

Answer 4

In [25]: t= (1,5,2,3,4,5,6,7,3,2,2,4,3)

In [26]: l = [1,2,3]

In [27]: sum(t.count(i) for i in l)
Out[27]: 7

On juanpa-arrivillaga's comment, I have implemented a solution that takes more memory but its more efficient. It trades space for complexity. If not using numpy like library this will be efficient and its equivalent to using itertools.groupby. Its complexity will be O(n+m) in the worst case.

In [43]: t = (1,5,2,3,4,5,6,7,3,2,2,4,3)

In [44]: l = [1,2,3]

In [45]: dct = {}

In [46]: for i in t:
    ...:     if not dct.get(i):
    ...:         dct[i] = 0
    ...:     dct[i] += 1
    ...:

In [47]: sum(dct.get(i, 0) for i in l)
Out[47]: 7