List match in python: get sub-list indices in a larger list

Question

For two lists

a = [1, 2, 9, 3, 8, ...] (no duplicate values in a, but a is very big) b = [1, 9, 1,...] (set(b) is a subset of set(a), 1<<len(b)<<len(a)) indices = get_indices_of_a(a, b) 

how to get_indices_of_a return indices = [0, 2, 0,...] using array(a)[indices] = b ? Is there a faster method than using a.index that is too long?

Creating a b set is a quick method for matching lists and return indices (see comparing two lists in python and return indices of consistent values ), but this will lose the index of the second 1 , as well as the sequence of indices in this case.

Answer 1

A quick method (when a is a large list) will use a dict to map the values ​​in a to the indices:

 >>> index_dict = dict((value, idx) for idx,value in enumerate(a)) >>> [index_dict[x] for x in b] [0, 2, 0] 

This will lead to linear time in the average case compared to using a.index , which will take quadratic time.

Answer 2

Assuming we are working with smaller lists, it is as simple as:

 >>> a = [1, 2, 9, 3, 8] >>> b = [1, 9, 1] >>> [a.index(item) for item in b] [0, 2, 0] 

On large lists, this will become quite expensive.

(If there are duplicates, the first occurrence will always be what is indicated in the resulting list, if not set(b) <= set(a) , you will get a ValueError).