Efficiently check if an element occurs at least n times in a list

Question

How to best write a Python function (check_list) to efficiently test if an element (x) occurs at least n times in a list (l)?

My first thought was:

def check_list(l, x, n):
    return l.count(x) >= n

But this doesn't short-circuit once x has been found n times and is always O(n).

A simple approach that does short-circuit would be:

def check_list(l, x, n):
    count = 0
    for item in l:
        if item == x:
            count += 1
            if count == n:
                return True
    return False

I also have a more compact short-circuiting solution with a generator:

def check_list(l, x, n):
    gen = (1 for item in l if item == x)
    return all(next(gen,0) for i in range(n))

Are there other good solutions? What is the best efficient approach?

Thank you

Answer 1

Instead of incurring extra overhead with the setup of a range object and using all which has to test the truthiness of each item, you could use itertools.islice to advance the generator n steps ahead, and then return the next item in the slice if the slice exists or a default False if not:

from itertools import islice

def check_list(lst, x, n):
    gen = (True for i in lst if i==x)
    return next(islice(gen, n-1, None), False)

Note that like list.count, itertools.islice also runs at C speed. And this has the extra advantage of handling iterables that are not lists.

---

Some timing:

In [1]: from itertools import islice

In [2]: from random import randrange

In [3]: lst = [randrange(1,10) for i in range(100000)]

In [5]: %%timeit # using list.index
   ....: check_list(lst, 5, 1000)
   ....:
1000 loops, best of 3: 736 µs per loop

In [7]: %%timeit # islice
   ....: check_list(lst, 5, 1000)
   ....:
1000 loops, best of 3: 662 µs per loop

In [9]: %%timeit # using list.index
   ....: check_list(lst, 5, 10000)
   ....:
100 loops, best of 3: 7.6 ms per loop

In [11]: %%timeit # islice
   ....: check_list(lst, 5, 10000)
   ....:
100 loops, best of 3: 6.7 ms per loop

Answer 2

You could use the second argument of index to find the subsequent indices of occurrences:

def check_list(l, x, n):
    i = 0
    try:
        for _ in range(n):
            i = l.index(x, i)+1
        return True
    except ValueError:
        return False

print( check_list([1,3,2,3,4,0,8,3,7,3,1,1,0], 3, 4) )

About index arguments

The official documentation does not mention in its Python Tutuorial, section 5 the method's second or third argument, but you can find it in the more comprehensive Python Standard Library, section 4.6:

s.index(x[, i[, j]]) index of the first occurrence of x in s (at or after index i and before index j) ⁽⁸⁾

⁽⁸⁾ index raises ValueError when x is not found in s. When supported, the additional arguments to the index method allow efficient searching of subsections of the sequence. Passing the extra arguments is roughly equivalent to using s[i:j].index(x), only without copying any data and with the returned index being relative to the start of the sequence rather than the start of the slice.

Performance Comparison

In comparing this list.index method with the islice(gen) method, the most important factor is the distance between the occurrences to be found. Once that distance is on average 13 or more, the list.index has a better performance. For lower distances, the fastest method also depends on the number of occurrences to find. The more occurrences to find, the sooner the islice(gen) method outperforms list.index in terms of average distance: this gain fades out when the number of occurrences becomes really large.

The following graph draws the (approximate) border line, at which both methods perform equally well (the X-axis is logarithmic):

Answer 3

Ultimately short circuiting is the way to go if you expect a significant number of cases will lead to early termination. Let's explore the possibilities:

Take the case of the list.index method versus the list.count method (these were the two fastest according to my testing, although ymmv)

For list.index if the list contains n or more of x and the method is called n times. Whilst within the list.index method, execution is very fast, allowing for much faster iteration than the custom generator. If the occurances of x are far enough apart, a large speedup will be seen from the lower level execution of index. If instances of x are close together (shorter list / more common x's), much more of the time will be spent executing the slower python code that mediates the rest of the function (looping over n and incrementing i)

The benefit of list.count is that it does all of the heavy lifting outside of slow python execution. It is a much easier function to analyse, as it is simply a case of O(n) time complexity. By spending almost none of the time in the python interpreter however it is almost gaurenteed to be faster for short lists.

Summary of selection criteria:

• shorter lists favor list.count
• lists of any length that don't have a high probability to short circuit favor list.count
• lists that are long and likely to short circuit favor list.index