Suppression des doublons d'un grand tableau d'entiers à l'aide de Java

Question

Connaissez-vous un moyen efficace de supprimer les valeurs dupliquées d'un très grand tableau d'entiers à l'aide de Java? La taille du tableau dépend de l'utilisateur connecté, mais dépassera toujours 1500000 valeurs non triées avec quelques doublons. Chaque entier contient un nombre entre 100000 et 9999999.

J'ai essayé de le convertir en Liste, mais le tas sur mon serveur n'autorise pas cette quantité de données (mon FAI l'a restreint). Et une boucle régulière dans une boucle for prend plus de 5 minutes pour calculer.

La taille du tableau sans les doublons est celle que je vais stocker dans ma base de données.

L'aide serait appréciée!

Answer 1

Vous pourriez peut-être utiliser un jeu de bits? Je ne sais pas à quel point le BitSet de Java est efficace. Mais 9999999 valeurs possibles ne prendrait que 9999999/8 = 1250000 octets = un peu plus de 1Mb. Lorsque vous parcourez le tableau de valeurs, définissez le bit correspondant sur true. Vous pouvez ensuite parcourir le jeu de bits et afficher la valeur correspondante chaque fois que vous trouvez un bit défini sur true. 1Mo va entrer dans un cache CPU, donc cela pourrait être assez efficace en fonction de l'implémentation de l'ensemble de bits.

Cela a également l'effet secondaire de trier les données aussi.

Et ... il s'agit d'un algorithme O (n) car il nécessite un seul passage sur les données d'entrée, les opérations sont O (1) (pour un ensemble basé sur un tableau comme celui-ci), et la sortie est également O (m) où m est le nombre de valeurs uniques et, par définition, doit être < = n.

Answer 2

Je créerais un hashset où je stockerais toutes les valeurs contenues dans la liste, avant que je commence à ajouter des articles à la liste. Puis vérifiez juste que le hashset ne contient pas la valeur que vous voulez ajouter.

Answer 3

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

vous aurez juste besoin d'un tableau de Integer[] au lieu de int[].

Answer 4

Vous pouvez trier le tableau d'abord:

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

Answer 5

Peut-être que vous pouvez faire quelques passes sur les données? Par exemple, si vous avez effectué dix passages sur les données et appliqué l'une des suggestions d'ensemble ci-dessus à un sous-ensemble plus petit des données (par exemple, lorsque la valeur mod passe # == 0). Ainsi:

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 cette façon, vous troquer le temps de la mémoire (augmenter le nombre de passes pour moins de mémoire/plus de temps et vice-versa).

Answer 6

Peut-être un ensemble de hachage qui fonctionne avec primitives à la place des objets fera le travail?Il existe des implémentations libres (havn't les utiliser avant, mais peut-être cela fonctionne):

http://trove4j.sourceforge.net/

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

doit ressembler à:

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 vous êtes sûr , que les entiers ont de petites valeurs resonables (par exemple toujours plus de zéro et moins de 1000 ou 10000), vous pouvez essayer un truc comme celui-ci:

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)); 

sortie: [0, 10, 11, 99]

Answer 9

Le pourrait vraiment désespéré écrire la matrice de disque et bifurquer sort | uniq | wc -l <infile.txt et capturer la sortie. Cela serait nécessaire si la mémoire était encore trop serrée ou si l'espace de domaine des entiers devenait plus grand. Je n'aime pas ça (il exécute même unix!) Mais mon point est qu'il y a beaucoup de manières d'accomplir la tâche.

Une autre observation est que la valeur minimale est 100 000. Nous pourrions donc soustraire 100 000 de la valeur maximale de 9 999 999, réduisant ainsi l'espace du domaine et économisant ainsi de la mémoire. Peut-être que 100k/8 bits sont des cacahuètes dans le schéma des choses, mais c'est essentiellement libre de le faire.