Multithread Suche von einzelnen Sammlung für Duplikate

Question

Verwendung Ich kann nicht in Segmente teilen. Wie für mein Beispiel oben, wenn 5 Threads gesetzt sind, dann würde das erste Segment 2 erste Objekt nehmen, und das zweite 3te und 4te, so dass sie keine Dups finden, aber es gibt Dups, wenn wir sie zusammenführen, ihre 2te und 3te.

Es könnte komplexere Strategie von den ersten Threads nehmen .. ah vergiss, zu schwer zu erklären.

Und natürlich, Problemstellung selbst in meinen Plänen.

Tha EDIT:

InChunk, und dann weiter bis zum Ende, dass die Klumpen zu analysieren. ;/

Answer 1

Ich würde eine Chunk-basierte Division, eine Aufgabenwarteschlange (z. B. ExecutorService) und private Hash-Tabellen verwenden, um Duplikate zu sammeln.

Jeder Thread im Pool nimmt bei Bedarf Chunks aus der Warteschlange und addiert 1 zum Wert, der dem Schlüssel des Elements in der privaten Hash-Tabelle entspricht. Am Ende werden sie mit der globalen Hash-Tabelle verschmelzen.

Am Ende parsen nur den Hash-Tabelle und sehen, welche Tasten haben einen Wert größer als 1

zum Beispiel mit einer Blockgröße von 3 und die Einzelteile:

1 2 2 2 3 4 5 5 6 6 

2 sei angenommen haben Threads im Pool. Thread 1 dauert 1 2 2 und Thread 2 dauert 2 3 4.Die privaten Hash-Tabellen werden wie folgt aussehen:

1 1 
2 2 
3 0 
4 0 
5 0 
6 0 

und

1 0 
2 1 
3 1 
4 1 
5 0 
6 0 

nächstes Thema 1 5 5 6 verarbeitet und Faden 2 wird Verfahren 6:

1 1 
2 2 
3 0 
4 0 
5 2 
6 1 

und

1 0 
2 1 
3 1 
4 1 
5 0 
6 1 

Am Ende sind die Duplikate 2 , 5 und 6:

1 1 
2 3 
3 1 
4 1 
5 2 
6 2 

Dies kann eine gewisse Menge an Raum auf Grund der privaten Tabellen jedes Fadens aufzunehmen, sondern um die Fäden parallel zu arbeiten, bis der Mischphase am Ende zu ermöglichen.

Answer 2

Ich denke, der Prozess der Aufteilung der zu entschärfenden Objekte muss am Ende des Abschnitts aussehen und sich vorwärts bewegen, um die dahinterliegenden Duples zu umfassen. wenn Sie hatte zum Beispiel:

1 1 2 . 2 4 4 . 5 5 6 

Und Sie in Blöcke von 3 aufzuteilen, dann würde der Teilungsprozess 1 1 2 nehmen, aber sehen, dass es eine andere 2 so wäre es 1 1 2 2 wie der erste Block zu erzeugen. Es würde sich wieder 3 vorwärts bewegen und 4 4 5 generieren, aber sehen, dass es Dups vorwärts gab und 4 4 5 5 generieren. Der 3. Thread hätte nur 6. Es würde:

1 1 2 2 . 4 4 5 5 . 6 

Die Größe der Blöcke werden inkonsistent sein, aber als die Anzahl der Elemente in der gesamten Liste groß wird, diese kleinen Veränderungen unbedeutend sein werden. Der letzte Thread kann sehr wenig zu tun haben oder kurz geändert werden, aber wiederum, da die Anzahl der Elemente groß wird, sollte dies die Leistung des Algorithmus nicht beeinträchtigen.

Ich denke, diese Methode wäre besser als irgendwie mit einem Thread die überlappenden Blöcke behandeln. Mit dieser Methode, wenn Sie viele Duplikate hatten, konnten Sie sehen, dass es viel mehr als 2 zusammenhängende Blöcke handhaben musste, wenn Sie Pech hatten, wenn Sie die Duplikate setzen. Zum Beispiel:

Ein Thread müsste die gesamte Liste wegen der 2s und der 5s behandeln.