Edificio ad indice parziale parzialmente invertito

Question

Ho bisogno di costruire un parziale Inverted Index. Qualcosa di simile:

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}}} 
*) 

Penso che sia abbastanza chiaro cosa fa. Nell'elenco di input, {x, y ...} sono unici, mentre {a, b, c, ..} non lo sono. L'uscita dovrebbe essere ordinata per #[[1]].

In questo momento, sto facendo questo:

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

ma sembra troppo complicata per un compito così facile, sembra troppo lento, e dovrei essere in grado di far fronte con Legion.

un test drive per confrontare i risultati:

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

Quindi, tutte le idee per un aumento di velocità?

Answer 1

Sembra un compito classico per Reap-Sow (miglioramento nella versione finale a causa di @Heike):

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

Poi,

iI[l] 

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

e

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

Ecco una versione alternativa con un simile (leggermente peggiore) prestazioni:

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

E 'interessante che Reap-Sow qui dà una soluzione ancora leggermente più veloce rispetto a quella basata su azioni strutturali.

EDIT 2

Solo per un'illustrazione - per chi preferisce le soluzioni basate su regole, qui è una basata su una combinazione di Dispatch e ReplaceList:

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

Si tratta di circa 2- 3 volte più lento degli altri due, però.