Xây dựng một phần chỉ số đảo ngược thời gian hiệu quả

Question

Tôi cần phải xây dựng một phần Inverted Index. Một cái gì đó như:

l = {{x, {h, a, b, c}}, {y, {c, d, e}}} 
iI[l] 
(* 
-> {{a, {x}}, {b, {x}}, {c, {x, y}}, {d, {y}}, {e, {y}}, {h, {x}}} 
*) 

Tôi nghĩ rằng nó là khá rõ ràng những gì nó làm. Trong danh sách đầu vào, {x, y ...} là duy nhất, trong khi {a, b, c, ..} thì không. Đầu ra phải được đặt hàng bởi #[[1]].

Ngay bây giờ, tôi đang làm điều này:

iI[list_List] := {#, list[[Position[list, #][[All, 1]]]][[All, 1]]} & /@ 
        (Union@Flatten@Last@Transpose@list) 

Nhưng nó có vẻ quá phức tạp cho một nhiệm vụ dễ dàng như vậy, dường như quá chậm, và tôi sẽ có thể đối phó với Legion.

Một lái thử để so sánh kết quả của bạn:

words = DictionaryLookup[]; 
abWords = DictionaryLookup["ab" ~~ ___]; 
l = {#, RandomChoice[abWords, RandomInteger[{1, 30}]]} & /@ words[[1 ;; 3000]]; 
First@Timing@iI[l] 
(* 
-> 5.312 
*) 

Vì vậy, bất kỳ ý tưởng cho một sự tăng tốc?

Answer 1

Có vẻ là một nhiệm vụ cổ điển cho Reap-Sow (cải tiến trong phiên bản cuối cùng do @Heike):

iI[list_] := Sort[Reap[Sow @@@ list, _, List][[2]]] 

Sau đó,

iI[l] 

{{a, {x}}, {b, {x}}, {c, {x, y}}, {d, {y}}, {e, {y}}, {h, {x}}} 

và

In[22]:= 
words=DictionaryLookup[]; 
abWords=DictionaryLookup["ab"~~___]; 
l={#,RandomChoice[abWords,RandomInteger[{1,30}]]}&/@words[[1;;3000]]; 
First@Timing@iI[l] 
Out[25]= 0.047 

EDIT

Dưới đây là một phiên bản thay thế với một hiệu suất tương tự (hơi xấu):

iIAlt[list_] := 
    Sort@Transpose[{#[[All, 1, 2]], #[[All, All, 1]]}] &@ 
      GatherBy[Flatten[Thread /@ list, 1], Last]; 

Điều thú vị là Reap-Sow đây đưa ra một giải pháp thậm chí hơi nhanh hơn so với một dựa trên hoạt động cơ cấu.

EDIT 2

Chỉ cần cho một minh hoạ - cho những người thích các giải pháp dựa trên luật lệ, đây là một trong dựa trên sự kết hợp của Dispatch và ReplaceList:

iIAlt1[list_] := 
    With[{disp = Dispatch@Flatten[Thread[Rule[#2, #]] & @@@ list]}, 
     Map[{#, ReplaceList[#, disp]} &, Union @@ list[[All, 2]]]] 

Đó là về 2- Tuy nhiên, chậm hơn 3 lần so với hai loại kia.