Java: ottimizzazione dell'hashset per il rilevamento di duplicati su larga scala

Question

Sto lavorando a un progetto in cui sto elaborando molti tweet; l'obiettivo è rimuovere i duplicati mentre li elaboro. Ho gli ID tweet, che arrivano come stringhe del formato "166471306949304320"

Per questo ho usato uno HashSet<String>, che funziona bene per un po '. Ma nel momento in cui raggiungo circa 10 milioni di oggetti, mi sto drasticamente impantanando e alla fine ottengo un errore di GC, presumibilmente dal rehashing. Ho provato a definire una migliore dimensione/di carico con

tweetids = new HashSet<String>(220000,0.80F);

e che gli permette di ottenere un po 'più lontano, ma è ancora estremamente lento (di circa 10 milioni sta prendendo 3x del tempo per elaborare). Come posso ottimizzare questo? Dato che ho un'idea approssimativa di quanti elementi dovrebbero essere nel set alla fine (in questo caso, circa 20-22 milioni) dovrei creare un HashSet che rihashes solo due o tre volte, o sarebbe il sovraccarico per tale il set ha subito troppe penalità? Le cose funzionerebbero meglio se non usassi una stringa, o se definissi una funzione HashCode diversa (che, in questo caso di una particolare istanza di una stringa, non sono sicuro di come fare)? Questa parte del codice di implementazione è sotto.

tweetids = new HashSet<String>(220000,0.80F); // in constructor 
duplicates = 0; 
... 
// In loop: For(each tweet) 
String twid = (String) tweet_twitter_data.get("id"); 
// Check that we have not processed this tweet already 
if (!(tweetids.add(twid))){ 
    duplicates++; 
    continue; 
} 

SOLUZIONE

grazie ai vostri suggerimenti, ho risolto. Il problema era la quantità di memoria richiesta per le rappresentazioni di hash; primo, HashSet<String> era semplicemente enorme e non richiesto perché il String.hashCode() è esorbitante per questa scala. Successivamente ho provato un Trie, ma si è bloccato a poco più di 1 milione di voci; la riallocazione degli array era problematica. Ho usato uno HashSet<Long> per migliorare l'effetto e quasi ce l'ho fatto, ma la velocità è decaduta e alla fine si è schiantato sull'ultima parte dell'elaborazione (circa 19 milioni). La soluzione è arrivata con l'uscita dalla libreria standard e utilizzando Trove. Ha terminato 22 milioni di record con pochi minuti in più rispetto al non aver controllato affatto i duplicati. implementazione finale era semplice, e si presentava così:

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

Answer 1

Si consiglia di guardare oltre il framework delle raccolte Java. Ho fatto un po 'di trattamento intensivo della memoria e si troveranno ad affrontare diversi problemi

1. Il numero di benne per grandi HashMaps e set hash sta per causare un sacco di spese generali (memoria). Puoi influenzare questo utilizzando un tipo di funzione di hash personalizzata e un modulo di ad es. 50000
2. Le stringhe sono rappresentate utilizzando caratteri a 16 bit in Java. Puoi dimezzare quello usando gli array di byte codificati utf-8 per la maggior parte degli script.
3. Le HashMaps sono in generale strutture di dati piuttosto sprecate e gli Hashset sono fondamentalmente solo un involucro sottile attorno a quelli.

Detto questo, date un'occhiata a trove o guava per le alternative. Inoltre, i tuoi ID sembrano lunghi. Quelle sono a 64 bit, un po 'più piccole della rappresentazione a stringa.

Un'alternativa da prendere in considerazione è l'uso di filtri di fioritura (guava ha un'implementazione decente). Un filtro di fioritura ti dirà se qualcosa non è sicuramente in un set e con ragionevole certezza (meno del 100%) se qualcosa è contenuto. Ciò combinato con una soluzione basata su disco (ad esempio database, mapdb, mecached, ...) dovrebbe funzionare abbastanza bene. È possibile memorizzare i nuovi ID in entrata, scriverli in batch e utilizzare il filtro bloom per verificare se è necessario cercare nel database ed evitare così costose ricerche la maggior parte del tempo.

Answer 2

suggerimento semplice, non provato e forse stupida: Creazione di una mappa di assortimenti, indicizzati dai primi/ultimi N caratteri del Tweet ID:

Map<String, Set<String>> sets = new HashMap<String, Set<String>>(); 
String tweetId = "166471306949304320"; 
sets.put(tweetId.substr(0, 5), new HashSet<String>()); 
sets.get(tweetId.substr(0, 5)).add(tweetId); 
assert(sets.containsKey(tweetId.substr(0, 5)) && sets.get(tweetId.substr(0, 5)).contains(tweetId)); 

Ciò consente di mantenere facilmente la dimensione massima dello spazio di hashing al di sotto di un valore ragionevole.

Answer 3

Se stai solo cercando l'esistenza di stringhe, ti suggerirei di provare a utilizzare uno Trie (chiamato anche albero di prefisso). Lo spazio totale utilizzato da un Trie dovrebbe essere inferiore a un HashSet ed è più veloce per le ricerche di stringhe.

Lo svantaggio principale è che può essere più lento se utilizzato da un disco rigido mentre carica un albero, non una struttura lineare memorizzata come un hash. Quindi assicurati che possa essere contenuto all'interno della RAM.

Il link che ho fornito è una buona lista di pro/contro di questo approccio.

* a parte, i filtri di fioritura suggeriti da Jilles Van Gurp sono ottimi prefiltri veloci.