Efficiently check if an element occurs at least n times in a list
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 islicedef 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 isliceIn [2]: from random import randrangeIn [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 loopIn [7]: %%timeit # islice ....: check_list(lst, 5, 1000) ....:1000 loops, best of 3: 662 µs per loopIn [9]: %%timeit # using list.index ....: check_list(lst, 5, 10000) ....:100 loops, best of 3: 7.6 ms per loopIn [11]: %%timeit # islice ....: check_list(lst, 5, 10000) ....:100 loops, best of 3: 6.7 ms per loop
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 Falseprint( 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) (8)(8)
index
raisesValueError
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 usings[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):
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