Time efficiency Parcial Inverted Index building

Question

Necesito construir un Inverted Index parcial. Algo como:

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

Creo que es bastante claro lo que hace. En la lista de entrada, {x, y ...} son únicos, mientras que {a, b, c, ..} no lo son. La salida debe ser ordenada por #[[1]].

En este momento, estoy haciendo esto:

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

pero parece demasiado complicado para una tarea tan fácil, parece demasiado lento, y yo debería ser capaz de hacer frente a la legión.

Una unidad de prueba para comparar sus resultados:

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

Así, cualquier idea para un aumento de velocidad?

Answer 1

Parece una tarea clásica para Reap-Sow (mejora en la versión final debido a @Heike):

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

Entonces,

iI[l] 

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

y

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

EDITAR

Aquí es una versión alternativa con un rendimiento similar (ligeramente peor):

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

Es interesante que Reap-Sow aquí da una solución aún ligeramente más rápido que el basado en las operaciones estructurales.

EDIT 2

Sólo para una ilustración - para aquellos que prefieren soluciones basadas en reglas, aquí es una basada en una combinación de Dispatch y ReplaceList:

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

Se trata de 2- 3 veces más lento que los otros dos, sin embargo.