python中的列表匹配:获取更大列表中的子列表的索引

Question

对于两个列表,

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)

如何让get_indices_of_a回indices = [0, 2, 0,...]用array(a)[indices] = b？有没有比使用更快的方法a.index,这需要太长时间？

制作b一集是匹配的列表,并返回指数的快速方法(见的匹配值的Python和回报指数比较两个列表),但它会失去第二的指标1,以及在这种情况下,指数序列.

Answer 1

快速方法(何时a是大型列表)将使用dict将值映射a到索引:

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

与使用a.index二次时间的情况相比,这将在平均情况下采用线性时间.

Answer 2

假设我们正在使用较小的列表,这很简单:

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

在较大的列表中,这将变得非常昂贵.

(如果存在重复项,则第一次出现将始终是结果列表中引用的那个,如果出现not set(b) <= set(a),则会出现ValueError).