partido de lista en Python: obtener índices de una sub-lista en una lista más grande

Question

Durante dos listas,

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) 

cómo vamos get_indices_of_a retorno indices = [0, 2, 0,...] con array(a)[indices] = b? ¿Hay un método más rápido que usar a.index, que tarda demasiado?

Haciendo b un conjunto es un método rápido de búsqueda de listas y volviendo índices (ver compare two lists in python and return indices of matched values), pero perderá el índice de la segunda 1 así como la secuencia de los índices en este caso.

Answer 1

Un método rápido (cuando a es una lista grande) estaría utilizando un diccionario para asignar valores de a a los índices:

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

Esto llevará tiempo lineal en el caso promedio, en comparación con el uso de a.index cuales tomaría tiempo cuadrático.

Answer 2

Suponiendo que estamos trabajando con listas más pequeñas, esto es tan fácil como:

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

en las listas más grandes, esto va a llegar a ser bastante caro.

(Si hay duplicados, la primera aparición siempre será la que se hace referencia en la lista resultante, si es not set(b) <= set(a), obtendrá un ValueError).