danh sách phù hợp trong python: có được chỉ số của một danh sách phụ trong một danh sách lớn hơn

Question

Đối với hai danh sách,

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) 

làm thế nào để chúng ta hãy trở lại get_indices_of_aindices = [0, 2, 0,...] với array(a)[indices] = b? Có phương pháp nhanh hơn sử dụng a.index, quá lâu không?

Đặt b một tập hợp là một phương pháp nhanh chóng kết hợp danh sách và chỉ mục quay lại (xem compare two lists in python and return indices of matched values), nhưng nó sẽ mất chỉ mục của số 1 thứ hai cũng như chuỗi chỉ số trong trường hợp này.

Answer 1

Một phương pháp nhanh (khi a là một danh sách lớn) sẽ được sử dụng một dict để lập bản đồ giá trị trong a để chỉ số:

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

này sẽ mất thời gian tuyến tính trong trường hợp trung bình, so với sử dụng a.index mà sẽ mất thời gian bậc hai.

Answer 2

Giả sử chúng ta đang làm việc với danh sách nhỏ hơn, đây là dễ dàng như:

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

Mở danh sách lớn hơn, điều này sẽ trở nên khá tốn kém.

(Nếu có trùng lặp, lần xuất hiện đầu tiên sẽ luôn là lần xuất hiện trong danh sách kết quả, nếu not set(b) <= set(a), bạn sẽ nhận được một ValueError).