Python: Traverse list from end to find first element satisfying a condition

Question

I want to iterate over elements from the end of a list to find the index of the last occurrence of an element which contains a '}'.

Ideally, I want to maintain efficiency using iterators rather than actually reversing the whole list or searching for all occurrences that match this condition.

If I were finding the first occurrence, I would use:

next(i for i,x in enumerate(list) if '}' in x)

However, I tried something similar using reversed to create a reverse iterator, but this did not seem to work, presumably because enumerate doesn't handle iterators, or maybe I have misunderstood...

next(i for i,x in enumerate(reversed(list)) if '}' in x)

I am aware other ways of doing this would be:

[i for i,x in enumerate(list) if '}' in x][-1]

or:

next(i for i,x in enumerate(list[::-1]) if '}' in x)

However, I am looking for the most efficient way. I could of course write a loop for efficiency, but was wondering if there was a neat way of doing it using the functions available.

I am relatively new to Python so go easy on me, and let me know if I have misunderstood anything. I am using Python 2.7.

Thanks in advance.

Answer 1

def rfind(lst, condition):
    return next((len(lst) - n
                 for (n, i) in enumerate(reversed(lst), 1)
                 if condition(i)),
                -1) # If we couldn't find anything, return -1

>>> lst = ['{b}', '[c]', '{a}', 'g']
>>> print rfind(lst, lambda i: '{' in i)
2
>>> print rfind(lst, lambda i: 'q' in i)
-1

Answer 2

Your example

next(i for i,x in enumerate(reversed(lst)) if '}' in x)

works, but it returns the index of the reversed list. So if it finds the '}' in the last string of the (unreversed) list it will return 0.

So to get the index in the original, unreversed list you could do

len(lst) - 1 - next(i for i,x in enumerate(reversed(lst)) if '}' in x)

---

The above code raises StopIteration if '}' isn't found in lst. You can avoid that by doing

len(lst) - 1 - next((i for i,x in enumerate(reversed(lst)) if '}' in x), len(lst))

and (like Kupiakos's code) it will return -1 if '}' isn't found.

---

BTW, don't use list as a variable name (even in example code) since it shadows the built-in list type.

Answer 3

Code for finding max index of item in list:

mylist = [10, 1, 2, 3, 10, 3]
max_index=max([i for i, j in enumerate(mylist) if j==10])
max_index

Output: 4

You can see that the index of 10 is at four, python indexes start at zero. Cheers.

Answer 4

Using itertools.ifilter() should be efficient:

from itertools import ifilter

def rsearch(lst, condition):
    try:
        return (len(lst) - next(ifilter(lambda t: condition(t[1]),
                                        enumerate(reversed(lst), 1)))[0])
    except StopIteration:
        return None  # nothing satisfied condition

lst = ['{b}', '[c]', '{a}', 'g']

print(rsearch(lst, lambda s: '}' in s))  # -> 2

Answer 5

This seems to be comparable in time to a generator expression.

a = map(str, xrange(1000000))
a[2000] = 'a'

def f(a):
    for i,n in enumerate(reversed(a)):
        if 'a' in n:
            return len(a) - i - 1