Eliminar elementos de la lista de repetición que conservan el orden de aparición

Question

Estoy produciendo listas planas con 10^6 a 10^7 números reales, y algunos de ellos se repiten.

Necesito eliminar las instancias que se repiten, manteniendo la primera aparición solamente y sin modificar el orden de la lista.

La clave aquí es la eficiencia, ya que tengo muchas listas para procesar.

Ejemplo (falso):

de entrada:

{.8, .3 , .8, .5, .3, .6} 

salida deseada

{.8, .3, .5, .6} 

Aparte nota

Eliminación de la repetición de elementos con Unión (sin preservar el orden) da en el lapt de mi pobre hombre op:

DiscretePlot[a = RandomReal[10, i]; First@Timing@Union@a, {i, 10^6 Range@10}] 

Answer 1

¿Quieres DeleteDuplicates, que conserva orden de la lista:

In[13]:= DeleteDuplicates[{.8, .3, .8, .5, .3, .6}] 

Out[13]= {0.8, 0.3, 0.5, 0.6} 

Fue añadida en Mathematica 7.0.

Answer 2

Para las versiones de Mathematica anteriores a 7, y para el interés general, aquí hay varias formas de implementar la función UnsortedUnion (es decir, DeleteDuplicates). Estos se recopilan de los documentos de ayuda y MathGroup. Se han ajustado para aceptar listas múltiples que luego se unen, en analogía a la Unión.

Para Mathematica 4 o anterior

UnsortedUnion = Module[{f}, f[y_] := (f[y] = Sequence[]; y); f /@ Join@##] & 

---

Para Mathematica 5

UnsortedUnion[x__List] := Reap[Sow[1, Join@x], _, # &][[2]] 

---

Para Mathematica 6

UnsortedUnion[x__List] := Tally[Join@x][[All, 1]] 

---

De Leonid Shifrin para Mathematica 3+

unsortedUnion[x_List] := Extract[x, Sort[Union[x] /. Dispatch[MapIndexed[Rule, x]]]] 

Answer 3

no competir con otras respuestas, pero simplemente no podía dejar de compartir un Compile (?) - solución basada. La solución se basa en construir un árbol de búsqueda binario y luego verificar cada número en la lista, independientemente de si su índice en la lista es el utilizado para construir el árbol b. Si es así, es el número original, si no, es un duplicado. Lo que hace que esta solución sea interesante para mí es que muestra una forma de emular "pass-by-reference" con Compile. El punto es que, si incorporamos funciones compiladas en otras funciones compiladas (y eso se puede lograr con una opción "InlineCompiledFunctions"), podemos referirnos en funciones internas a las variables definidas en el alcance de función externo (debido a la forma en que entra en funcionamiento) .Esta no es una verdadera referencia de paso a paso, pero aún permite combinar funciones de bloques más pequeños, sin penalización de eficiencia (esto es más en el espíritu de macroexpulsión). No creo que esto esté documentado, y no tengo idea de si esto permanecerá en futuras versiones. De todas formas, aquí está el código:

(* A function to build a binary tree *) 
Block[{leftchildren , rightchildren}, 
makeBSearchTree = 
Compile[{{lst, _Real, 1}}, 
Module[{len = Length[lst], ctr = 1, currentRoot = 1}, 
leftchildren = rightchildren = Table[0, {Length[lst]}]; 
For[ctr = 1, ctr <= len, ctr++, 
    For[currentRoot = 1, lst[[ctr]] != lst[[currentRoot]],(* 
    nothing *), 
    If[lst[[ctr]] < lst[[currentRoot]], 
    If[leftchildren[[currentRoot]] == 0, 
    leftchildren[[currentRoot]] = ctr; 
    Break[], 
    (* else *) 
    currentRoot = leftchildren[[currentRoot]] ], 
    (* else *) 
    If[rightchildren[[currentRoot]] == 0, 
    rightchildren[[currentRoot]] = ctr; 
    Break[], 
    (* else *) 
    currentRoot = rightchildren[[currentRoot]]]]]]; 
], {{leftchildren, _Integer, 1}, {rightchildren, _Integer, 1}}, 
CompilationTarget -> "C", "RuntimeOptions" -> "Speed", 
CompilationOptions -> {"ExpressionOptimization" -> True}]]; 


(* A function to query the binary tree and check for a duplicate *) 
Block[{leftchildren , rightchildren, lst}, 
isDuplicate = 
Compile[{{index, _Integer}}, 
Module[{currentRoot = 1, result = True}, 
While[True, 
    Which[ 
    lst[[index]] == lst[[currentRoot]], 
    result = index != currentRoot; 
    Break[], 
    lst[[index]] < lst[[currentRoot]], 
    currentRoot = leftchildren[[currentRoot]], 
    True, 
    currentRoot = rightchildren[[currentRoot]] 
    ]]; 
result 
], 
{{leftchildren, _Integer, 1}, {rightchildren, _Integer, 
    1}, {lst, _Real, 1}}, 
CompilationTarget -> "C", "RuntimeOptions" -> "Speed", 
CompilationOptions -> {"ExpressionOptimization" -> True} 
]]; 


(* The main function *) 
Clear[deldup]; 
deldup = 
Compile[{{lst, _Real, 1}}, 
    Module[{len = Length[lst], leftchildren , rightchildren , 
    nodup = Table[0., {Length[lst]}], ndctr = 0, ctr = 1}, 
makeBSearchTree[lst]; 
For[ctr = 1, ctr <= len, ctr++, 
If[! isDuplicate [ctr], 
    ++ndctr; 
    nodup[[ndctr]] = lst[[ctr]] 
    ]]; 
Take[nodup, ndctr]], CompilationTarget -> "C", 
"RuntimeOptions" -> "Speed", 
CompilationOptions -> {"ExpressionOptimization" -> True, 
"InlineCompiledFunctions" -> True, 
"InlineExternalDefinitions" -> True}]; 

Estas son algunas pruebas:

In[61]:= intTst = N@RandomInteger[{0,500000},1000000]; 

In[62]:= (res1 = deldup[intTst ])//Short//Timing 
Out[62]= {1.141,{260172.,421188.,487754.,259397.,<<432546>>,154340.,295707.,197588.,119996.}} 

In[63]:= (res2 = Tally[intTst,Equal][[All,1]])//Short//Timing 
Out[63]= {0.64,{260172.,421188.,487754.,259397.,<<432546>>,154340.,295707.,197588.,119996.}} 

In[64]:= res1==res2 
Out[64]= True 

no tan rápido como la versión Tally, sino también Equal - basado, y como he dicho, mi punto era ilustrar una técnica interesante (IMO).