Je travaille sur un projet où je traite beaucoup de tweets; L'objectif est d'éliminer les doublons lorsque je les traite. J'ai les identifiants Tweet, qui entrent comme des chaînes du format J'ai utilisé un et cela le permet d'obtenir un Un peu plus loin, mais est toujours extrêmement lent (environ 10 millions, il prend 3 fois de temps à traiter). Comment puis-je optimiser cela? Étant donné que j'ai une idée approximative du montant de l'ensemble des articles dans l'ensemble d'ici la fin (dans ce cas, environ 20-22 millions) Devrais-je créer un hashset qui ne rénonce que deux ou trois fois ou que les frais généraux pour un tel Définir trop de pénalités de temps? Les choses auraient-elles mieux fonctionner si je n'utilisais pas de chaîne ou si je définis une fonction de hashcode différente (qui, dans ce cas d'une instance particulière d'une chaîne, je ne sais pas comment faire)? Cette partie du code de mise en œuvre est ci-dessous. P> "166471306949304320" code> hashset tweetaids = nouveau hashset import gnu.trove.set.hash.TLongHashSet;
...
TLongHashSet tweetids; // class variable
...
tweetids = new TLongHashSet(23000000,0.80F); // in constructor
...
// inside for(each record)
String twid = (String) tweet_twitter_data.get("id");
if (!(tweetids.add(Long.parseLong(twid)))) {
duplicates++;
continue;
}
3 Réponses :
Suggestion simple, non commise et éventuellement stupide: Créez une carte des ensembles, indexés par les premiers / derniers caractères de l'ID Tweet: qui vous permet de garder la taille maximale de l'espace de hachage inférieur à une valeur raisonnable.
qui ajoute beaucoup d'opérations ... c'est essentiellement un hachage de hachage (+ plusieurs égaux) avec lequel vous ne gagneriez rien
Vous voudrez peut-être regarder au-delà du cadre de collections Java. J'ai fait une certaine transformation intensive de mémoire et vous ferez face à plusieurs problèmes
Étant donné que, jetez un coup d'œil à Trove ou Guava pour des alternatives. En outre, vos identifiants ressemblent à des longs. Ce sont 64 bits, un peu plus petit que la représentation de chaîne.
Une alternative que vous souhaiterez envisager est d'utiliser des filtres de fleurs (GUAVA a une implémentation décente). Un filtre de floraison vous dirait si quelque chose n'est définitivement pas dans un ensemble et avec une certitude raisonnable (moins de 100%) si quelque chose est contenu. C'est associé à une solution basée sur disque (par exemple la base de données, MAPDB, Mecached, ...) devrait fonctionner raisonnablement bien. Vous pouvez faire tamponner les nouveaux identifiants entrants, écrivez-les en lots et utilisez le filtre de floraison pour vérifier si vous devez consulter la base de données et éviter ainsi des recherches coûteuses la plupart du temps.
Si vous recherchez simplement l'existence de chaînes, je vous suggère d'essayer d'utiliser un Trie (également appelé un arbre de préfixe). L'espace total utilisé par une trie doit être inférieur à un hashset et il est plus rapide pour les recherches de cordes.
L'inconvénient principal est qu'il peut être plus lent lorsqu'il est utilisé à partir d'un disque dur lors de la chargement d'un arbre, pas une structure linéaire stockée comme un hachage. Alors assurez-vous que cela peut être tenu à l'intérieur de la RAM.
Le lien que j'ai donné est une bonne liste de pros / inconvénients de cette approche.
* À côté, les filtres de Bloom suggéré par Jilles Van Gurp sont de grands préfiltres rapides.
Pourquoi je n'ai pas pensé à ça? J'utilise déjà une trie pour une autre partie du programme, mais je ne pensais pas à en faire un pour ce problème. Si cela fonctionne (et cela semble évident maintenant), vous obtiendrez certainement la réponse.
Aie. J'ai eu une surcharge GC de seulement 1 million d'enregistrements. Je ne pense pas qu'une trie va travailler.
Peut-être que je le mette en œuvre faux? Le mien est juste une liste de matrices récursives de 10 caractères pour caractères 0-9 - '0' . Je suppose que d'y ajouter un million de fois bloque l'utilisation de la mémoire et exigeant la réaffectation. Connaissez-vous une implémentation plus efficace, étant donné que tout ce que je sais sur mon contribution est que ce sera des chiffres de 0 à 9 et 18 chiffres?
Je devinerais que chaque nœud trie aurait 1 caractère et une matrice / liste d'enfants. Ne pas comprendre le tableau récursif de 10 caractères
Oui, exactement comment je la mettant en œuvre. Chaque nœud a des enfants [10] et une étiquette au point de 19 caractères.
Je ne pense pas que vous devriez avoir des enfants [10], ça va que la trie a toujours un facteur de ramification de 10. Les premiers nœuds pourraient avoir 10, mais comme vous continuez à la suite de la trie qui ne sera plus vraie. Vous devriez probablement utiliser un tableau aussi gros que le nombre de nombre d'enfants pour économiser de l'espace
Que diriez-vous de traiter les identifiants comme des nombres, de trouver une bonne valeur de base et de travailler avec des différences à cela? Vous pouvez alors utiliser un
hashset , qui devrait surperformer des chaînes; Vous pouvez également utiliser la bibliothèque Trove pour travailler avec des primitives. Vous ne pouvez pas simplement augmenter la taille de votre tas?
Si vous savez que l'ensemble contiendra éventuellement 22 millions d'articles, pourquoi ne créez-vous pas un hashsette avec une capacité de 22_000_000 / 0,75 dès le début? Cela empêcherait tout réhabité.
@Jbnizet Vous voulez dire 22_000_000 / 1.0?
En ce qui concerne l'augmentation de la taille du tas avec quelque chose comme
java -xms2gb , ma compréhension est que ce serait une aide à la bande contre les erreurs de GC mais ne pourrait pas aider à la dégradation de la vitesse dramatique.@Jbnizet je me demandais à ce sujet. Oui, je pourrais faire ça; Mais il n'y a-t-il pas un coût de traitement majeur pour commencer initialement avec un tel hachage? Les avantages de minimiser les rénummes risquent-ils de compenser cela?
@assylias: non. Malheureusement, le constructeur de hashset prend une capacité d'argumentation et non une taille. Donc, en passant 22_000_000 causerait une REVASH dès que l'élément 15_500_001th est ajouté à l'ensemble. C'est pourquoi GUAVA a SETS.NEWHASHSHASETWithExpecySIZE () qui est beaucoup plus naturel.
@Worldsendedless: à la fin, une matrice suffisamment grande devra être allouée, alors pourquoi ne pas l'attribuer dès le début, au lieu d'attribuer un petit, puis un plus grand, puis une plus grande, puis une plus grande, puis une plus grande, puis une plus grande, puis une plus grande, puis une plus grande, puis une plus grande, puis une plus grande encore, puis une plus grande, puis et avoir à tout réhabiter à chaque fois?
@Jbnizet grande question; C'est ce que je me demande. Ne commence pas par une matrice humoneuse augmente le coût temporel de chaque opération standard (ici,
ajouter )? Je vais essayer de voir à quoi ça ressemble, cependant.Qu'en est-il d'un filtre de floraison si vous pouvez accepter un petit pourcentage (contrôlable) de tweets mal étiquetés comme des doublons? Vous pouvez descendre à 9,6 bits par tweet à un taux d'erreur de 1% selon Wikipedia. Prendrait seulement environ 25 Mo pour 22 millions d'éléments
@Worldsendless: Je suis sûr que ce n'est pas le cas, du moins pas sensiblement. À la fin, c'est quelque chose comme appel à Hashcode, faire une opération binaire rapide et accéder à un tableau à un index spécifié. Et l'ajout d'un élément une fois plus rapide que l'ajout de trois, quatre de cinq fois en raison de la réhabation. N'oubliez pas non plus que les rehases provoquent deux tableaux dans la mémoire en même temps.
@Jbnizet malentendu ici! Je pensais que votre
22m / 0,75 signifiait la capacité de 22 m et du facteur de charge de 0,75f (je comprends maintenant que vous comprenez 42 m divisé par 0,75), donc j'ai répondu que vous devriez utiliser un Capacité de 22 m et un facteur de charge de 1,0.