Eliminar duplicados de una matriz de enteros grandes utilizando Java

Question

¿Conoce alguna forma eficiente en el tiempo de eliminar valores duplicados de una matriz de enteros muy grande utilizando Java? El tamaño de la matriz depende del usuario que haya iniciado sesión, pero siempre superará los 1500000 valores sin clasificar con algunos duplicados. Cada número entero contiene un número entre 100000 y 9999999.

Intenté convertirlo en una lista, pero el montón en mi servidor no permite esta cantidad de datos (mi ISP lo ha restringido). Y un bucle regular para dentro de un bucle for toma más de 5 minutos para calcular.

El tamaño de la matriz sin los duplicados es el que almacenaré en mi base de datos.

¡La ayuda sería apreciada!

Answer 1

¿Quizás podría usar un juego de bits? No sé cuán eficiente es el BitSet de Java. Pero los valores posibles de 9999999 solo tomarían 9999999/8 = 1250000 bytes = poco más de 1Mb. A medida que recorre la matriz de valores, establezca el bit correspondiente en verdadero. Luego puede caminar sobre el conjunto de bits y generar el valor correspondiente siempre que encuentre un bit establecido en verdadero.

1Mb cabe en una caché de la CPU, por lo que esto podría ser bastante eficiente dependiendo de la implementación del conjunto de bits.

Esto también tiene el efecto secundario de ordenar los datos también.

Y ... este es un algoritmo O (n) ya que requiere un pase único sobre los datos de entrada, las operaciones establecidas son O (1) (para un conjunto basado en arreglos como este), y el pase de salida también es O (m) donde m es el número de valores únicos y, por definición, debe ser < = n.

Answer 2

Haría un hashset donde almacenaría todos los valores contenidos en la lista, antes de comenzar a agregar elementos a la lista. Luego, simplemente verifique que el hashset no contenga el valor que desea agregar.

Answer 3

Set<Integer> set = new HashSet<Integer>(); 
Collections.addAll(set, array); 

que sólo necesitarán una serie de Integer[] en lugar de int[].

Answer 4

Usted puede tratar de la clasificación de la primera matriz:

int arr[] = yourarray; 
Arrays.sort(arr); 
// then iterate arr and remove duplicates 

Answer 5

Tal vez usted podría hacer un puñado de pasadas sobre los datos? Por ejemplo, si realizó diez pasadas sobre los datos y aplicó una de las sugerencias anteriores a un subconjunto más pequeño de los datos (por ejemplo, cuando value mod pass # == 0). Por lo tanto:

for (int i = 0 to 9) { 
    set = new Set() 
    for (each entry in the data set) { 
    if (entry % i == 0) { 
     set.add(entry) 
    } 
    } 
    output set 
} 

De esta manera se comercio fuera de tiempo para la memoria (aumentar el número de pases para menos memoria/más tiempo y viceversa).

Answer 6

Tal vez un conjunto de hash que funciona con primitivos en lugar de objetos hará el trabajo?Existen implementaciones libres (havn't los usaba antes, pero tal vez funciona):

http://trove4j.sourceforge.net/

http://trove4j.sourceforge.net/javadocs/gnu/trove/TIntHashSet.html

sería parecido a:

int[] newArray = new TIntHashSet(yourArray).toArray(); 

Answer 7

int[] a; 
Arrays.sort(a); 
int j = 0; 
for (int i = 1; i < a.length; ++i) { 
    if (a[i] != a[j]) { 
    ++j; 
    a[j] = a[i]; 
    } 
} 
// now store the elements from 0 to j (inclusive - i think) 

Answer 8

Si está seguro , que los enteros tienen valores pequeños razonables (por ejemplo, siempre más de cero y menos de 1000 o 10000), puedes probar un truco como este:

final int MAX = 100; 
    int[] arrayWithRepeats = {99, 0, 10, 99, 0, 11, 99}; 

    //we are counting here integers with the same value 
    int [] arrayOfValues = new int[MAX+1]; 
    int countOfUniqueIntegers = 0; 
    for(int i : arrayWithRepeats) { 
     if(arrayOfValues[i] == 0) { 
      countOfUniqueIntegers++; 
     } 
     arrayOfValues[i]++; 
    } 

    // you can use arrayOfValues (smaller) or convert it 
    // to table of unique values (more usable) 

    int[] arrayOfUniqueValues = new int[countOfUniqueIntegers]; 
    int index = 0; 
    for(int i = 0; i<arrayOfValues.length; i++) { 
     if(arrayOfValues[i] != 0) { 
      arrayOfUniqueValues[index] = i; 
      index++; 
     } 
    } 

    //and now arrayOfUniqueValues is even sorted 
    System.out.println(Arrays.toString(arrayOfUniqueValues)); 

de salida: [0, 10, 11, 99]

Answer 9

Los verdaderamente desesperada podría escribir la matriz de disco y horquilla fuera sort | uniq | wc -l <infile.txt y capturar la salida. Esto sería necesario si la memoria aún estaba demasiado ajustada o si el espacio de dominio de los enteros aumentaba. No me gusta esto (¿está ejecutando unix?), Pero mi punto es que hay muchas formas de llevar a cabo la tarea.

Otra observación es que el valor mínimo es 100.000. Por lo tanto, podríamos restar 100,000 del valor máximo de 9,999,999, reduciendo el espacio del dominio y así ahorrar algo de memoria. Tal vez 100k/8 bits son cacahuetes en el esquema de las cosas, pero esencialmente es libre de hacerlo.