python中的列表匹配：获取较大lis中子列表的索引

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用array(a)[indices] = b返回indices = [0, 2, 0,...]？有没有比使用耗时太长的a.index更快的方法？

使b成为一个集合是匹配列表和返回索引的一种快速方法（参见compare two lists in python and return indices of matched values），但在这种情况下，它将丢失第二个1的索引以及索引的序列。

Answer 1

假设我们正在处理较小的列表，这很容易：

>>> 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）。

Answer 2

快速方法（当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相比，在平均情况下，这需要线性时间，而使用a.index则需要二次时间。