list match in python: Ermitteln der Indizes einer Unterliste in einer größeren Liste

Question

Für zwei Listen,

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)

wie man vermietet get_indices_of_a return indices = [0, 2, 0,...] mit array(a)[indices] = b ? Gibt es eine schnellere Methode als die Verwendung von a.index Was dauert zu lange?

Herstellung b eine Menge ist eine schnelle Methode, um Listen abzugleichen und Indizes zurückzugeben (siehe zwei Listen in Python vergleichen und Indizes der übereinstimmenden Werte zurückgeben ), aber es verliert den Index des zweiten 1 sowie die Reihenfolge der Indizes in diesem Fall.

Answer 1

Eine schnelle Methode (wenn a eine große Liste ist) würde ein dict verwenden, um die Werte in a zu Indizes:

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

Dies nimmt im Durchschnitt linear Zeit in Anspruch, verglichen mit der Verwendung von a.index was quadratische Zeit in Anspruch nehmen würde.

Answer 2

Wenn man davon ausgeht, dass wir mit kleineren Listen arbeiten, ist das so einfach wie:

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

Bei größeren Listen wird dies recht teuer.

(Wenn es Duplikate gibt, wird das erste Vorkommen immer dasjenige sein, auf das in der resultierenden Liste verwiesen wird, wenn not set(b) <= set(a) erhalten Sie einen ValueError).