Savez-vous de tout moyen efficace de supprimer les valeurs dupliquées d'un très grand tableau entier à l'aide de Java? La taille de la matrice dépend de l'utilisateur connecté, mais dépassera toujours 1500 000 valeurs non traitées avec certains duplicats. Chaque entier contient un nombre compris entre 100 000 et 9999999.
J'ai essayé de la convertir à une liste, mais le tas sur mon serveur n'autorise pas cette quantité de données (mon fournisseur de services Internet la limite). Et une boucle régulière dans A pour la boucle prend plus de 5 minutes pour calculer.
La taille de la matrice sans duplicates est celle que je vais stocker dans ma base de données.
aide serait apprécié!
9 Réponses :
Je ferais un hashset où je stocke toutes les valeurs contenues dans la liste, avant que je commence à ajouter des éléments à la liste. Ensuite, vérifiez simplement que le hashset ne contient pas la valeur que vous souhaitez ajouter.
"J'ai essayé de la convertir à une liste, mais le tas sur mon serveur n'autorise pas cette quantité de données" - cela règle probablement des ensembles.
Dans mon esprit, une liste est un peu plus gaspillée avec la mémoire qu'un hashset, pour de grands ensembles de données. Mais je pourrais avoir tort. = /
Cela dépend en grande partie de la mise en œuvre de la liste. Je crois que ArrayList est plus efficace de la mémoire que hashset , mais je pourrais me tromper aussi :-)
Set<Integer> set = new HashSet<Integer>(); Collections.addAll(set, array); you will just need an array of Integer[] instead of int[].
"J'ai essayé de la convertir à une liste, mais le tas sur mon serveur n'autorise pas cette quantité de données" - cela règle probablement des ensembles.
Oui, c'est plus au point. @ user435140 Notez que cela ne fonctionnera que si votre tableau contient INTEGER S, non primitif int s.
Vous pouvez essayer de trier le tableau:
int arr[] = yourarray; Arrays.sort(arr); // then iterate arr and remove duplicates
@Bozho, il pouvait itérer le tableau et compter des valeurs uniques. Apparemment, la seule chose qu'il ait besoin de faire ... la taille de la matrice sans les duplicats est celle que je vais stocker dans ma base de données ...
En tri en premier, vous pouvez ensuite effectuer une travertiale finale de la matrice et garder l'une de chaque valeur unique. Cela devrait donner une complexité de O (n log n) par opposition à O (n ^ 2) pour la double boucle mentionnée.
En supposant que vous avez des ressources suffisantes pour trier la chose en premier lieu!
@Danny, Arrays.sort (...) n'utilise pas plus d'espace: il est "en place".
@Bart K - Cela dépend de votre implémentation, mais le JDK ne garantit pas de sorte de place. Beaucoup utilisent réellement une forme de fuselort qui nécessite O (n) espace supplémentaire.
Oui, mais vous supposez qu'il y a suffisamment de mémoire pour le charger en premier lieu. Ou bien, vous devrez mettre en place un algorithme de tri de disque. (Accordé à l'OP dit qu'ils ont déjà un tableau - je souligne simplement des problèmes possibles avec la solution en général)
@Mikera, true. La prochaine fois que je parlerai explicitement que je parle de JVM de Sun / Orcale. Hors de curiosité, ce que JVM ne trie pas de matrice primitive en place?
@Danny, de l'article original de l'utilisateur435140, j'ai conclu qu'il dispose déjà de la matrice et que la "conversion à une liste" produit le problème du tas.
@Mikera, au cas où vous cherchez toujours ces implémentations JVM, ne vous embêtez pas :)
@Bart K - En fait, je pensais à des sorties d'objet / comparables plutôt que de primitives - vous avez raison les types primitives actuels dans JDK6 / 7 sont en place. Pas sûr de connaître des contre-exemples pour les primitives, mais je ne voudrais certainement pas compter sur le comportement ...
Peut-être que vous pourriez faire une poignée de passes sur les données? Par exemple, si vous avez effectué dix passes sur les données et appliquée l'une des suggestions définies ci-dessus à un sous-ensemble inférieur des données (par exemple, lorsque la valeur MOD passe # == 0). Ainsi: De cette façon, vous échangerez du temps de congé pour la mémoire (augmenter le nombre de passes pour moins de mémoire / plus de temps et inversement).
Vous pouvez peut-être utiliser un bit jeu? Je ne sais pas à quel point Bitset de Java est efficace. Mais 9999999 Les valeurs possibles ne prendraient que 99999999/8 = 1250000 octets = un peu plus de 1 Mo. Lorsque vous marchez la gamme de valeurs, définissez le bit correspondant sur true. Ensuite, vous pouvez marcher sur le bit défini et sortir la valeur correspondante chaque fois que vous trouverez un bit défini sur TRUE.
1 Mo sera adapté dans un cache de la CPU, cela pourrait donc être assez efficace en fonction de la mise en œuvre du bit.
Ceci a également l'effet secondaire du tri des données.
et ... ceci est un algorithme O (n) car il nécessite une seule passe sur les données d'entrée, les opérations définies sont O (1) (pour un ensemble de matrice comme celui-ci), et la passe de sortie est également O (m) où m est le nombre de valeurs uniques et, par définition, doit être <= n.
Les réponses intelligentes comme celles-ci sont la raison pour laquelle je viens à Stackoverflow
Peut-être un ensemble de hash qui fonctionne avec http: //trove4j.sourceforge .NET / http: // trove4j.sourceforge.net/javadocs/gnu/trove/tighashst.html ressemblerait alors à:
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)
Si le résultat n'a pas besoin d'être trié, vous pouvez copier des valeurs à partir du «Démarrer» (qui incrémente lors de la copie) pour réduire le nombre de copies. (un par duplicata au lieu d'un par élément)
Si vous êtes sûr, que des entiers ont des valeurs de petites valeurs (par exemple, plus de zéro et moins de 1000 ou 10000), vous pouvez essayer un truc comme ceci: sortie: [ 0, 10, 11, 99]
Ceci est essentiellement identique à celui de ma suggestion de masse, sauf que vous utilisez 32 bits par entrée au lieu de 1, la mémoire devient donc un problème assez rapidement. En outre, l'OP a déclaré que les valeurs vont jusqu'à 9999999.
Étant donné que "chaque entier contient un nombre compris entre 100 000 et 9999999", cela ne fonctionnera pas.
Tu as raison. Et bonne idée est de changer de gamme de valeurs de Int [] à Bitset comme l'idée de Danny.
Le véritable désespéré pourrait écrire la matrice sur le disque et la fourche off Une autre observation est que la valeur minimale est de 100 000. Nous pourrions donc soustraire 100 000 de la valeur maximale de 9 999 9999, réduisant ainsi l'espace de domaine et permettant ainsi une certaine mémoire. Peut-être que 100k / 8 bits sont des cacahuètes dans le schéma de choses, mais c'est essentiellement libre de le faire. Trier | UNIQ | wc -l