Fastest way to find Indexes of item in list?

Question

If one was to attempt to find the indexes of an item in a list you could do it a couple different ways here is what I know to be the fastest:

aList = [123, 'xyz', 'zara','xyz', 'abc']; 
indices = [i for i, x in enumerate(aList) if x == "xyz"]
print(indices)

Another way not pythonic and slower:

count = 0
indices = []
aList = [123, 'xyz', 'zara','xyz', 'abc'];
for i in range(0,len(aList):
    if 'xyz' == aList[i]:
        indices.append(i)
print(indices)

The first method is undoubtedly faster however what if you wanted to go faster, is there a way? For the first index using method:

aList = [123, 'xyz', 'zara','xyz', 'abc'];             
print "Index for xyz : ", aList.index( 'xyz' ) 

is very fast but can't handle multiple indexes.
How might one go about speeding things up?

Solution 1

def find(target, myList):
    for i in range(len(myList)):
        if myList[i] == target:
            yield i

def find_with_list(myList, target):
     inds = []
     for i in range(len(myList)):
         if myList[i] == target:
             inds += i,
     return inds


In [8]: x = range(50)*200
In [9]: %timeit [i for i,j in enumerate(x) if j == 3]
1000 loops, best of 3: 598 us per loop

In [10]: %timeit list(find(3,x))
1000 loops, best of 3: 607 us per loop
In [11]: %timeit find(3,x)
1000000 loops, best of 3: 375 ns per loop

In [55]: %timeit find_with_list(x,3)
1000 loops, best of 3: 618 us per loop

Assuming you want a list as your output:

• All options seemed exhibit similar time performance for my test with the list comprehension being the fastest (barely).

If using a generator is acceptable, it's way faster than the other approaches. Though it doesn't account for actually iterating over the indices, nor does it store them, so the indices cannot be iterated over a second time.

Solution 2

Use list.index(elem, start)! That uses a for loop in C (see its implementation list_index_impl function in the source of CPython's listobject.c). Avoid looping through all the elements in Python, it is slower than in C.

def index_finder(lst, item):
    """A generator function, if you might not need all the indices"""
    start = 0
    while True:
        try:
            start = lst.index(item, start)
            yield start
            start += 1
        except ValueError:
            break

import array
def index_find_all(lst, item, results=None):
    """ If you want all the indices.
    Pass results=[] if you explicitly need a list,
    or anything that can .append(..)
    """
    if results is None:
        length = len(lst)
        results = (array.array('B') if length <= 2**8 else
                   array.array('H') if length <= 2**16 else
                   array.array('L') if length <= 2**32 else
                   array.array('Q'))
    start = 0
    while True:
        try:
            start = lst.index(item, start)
            results.append(start)
            start += 1
        except ValueError:
            return results

# Usage example
l = [1, 2, 3, 4, 5, 6, 7, 8] * 32

print(*index_finder(l, 1))
print(*index_find_all(l, 1))

Solution 3

Simply create a dictionary of item->index from the list of items using zip like so:

items_as_dict = dict(zip(list_of_items,range(0,len(list_of_items))))
index = items_as_dict(item)

Solution 4

To get the index of the item, you can use the dictionary.

aList = [123, 'xyz', 'zara','xyz', 'abc'];
#The following apporach works only on lists with unique values
aList = list(np.unique(aList)); 
dict = enumerate(aList);
# get inverse mapping of above dictionary, replace key with values
inv_dict = dict(zip(dict.values(),dict.keys()))
# to get index of item by value, use 'inv_dict' and to get value by index, use 'dict'
valueofItemAtIndex0 = dict[0]; # value = 123
indexofItemWithValue123 = inv_dict[123]; # index = 0

View more solutions