Duplikate finden

[MrVertigo]

Hallo,

ich habe eine Liste von Daten (die in einer Datei steht oder aus der DB kommt), wobei jeder Datensatz eine ID hat, die nicht immer eindeutig ist.
Nun soll ich die List von Daten durch gehen und die Duplikate (IDs) raus filtern.

Mein erste Ansatz war eine HashMap anzulegne in der ich die ID speichere.
Ich nehme mir also ein Element von der List, ueberpruefe ob die dazugehoerige ID schon in der HashMap ist. Ist sie noch nicht in der HashMap dann packe ich sie mit in die HashMap und den dazugehoerigen Datensatz wird in die Ausgangsdatei geschrieben. Wenn die ID schon in der HashMap ist, dann passiert gar nichts.

Das ganze funktioniert ganz gut mit kleinen Datensaetzen. Aber wenn ich das ganze fuer grosse datenSaetze ausfuehre dann wird sehr viel CPU in Anspruch genommen und dann ganze wird hinten heraus sehr sehr langsam.

Hat jemand eine Idee wie man die Duplikate noch heraus filtern koennte?

 

[Gast]

Was heißt den etwas konkreter groß und klein?

Du könntest ja im ersten schritt nur mit den IDs arbeiten und erst wenn du daraus eine eindeutige Liste erzeugt hast, die konkretn Daten aus der DB abfragen und umkopieren, oder sonst was damit anstellen.

 

[SlaterB]

sowas kann nicht lange dauern,
in einer Sekunde musst du mehr überprüfen können als überhaupt Objekte in den Arbeitsspeicher passen,
vom Laden/ Speichern/ Löschen dieser Daten ganz abgesehen,

speicherst du die fraglichen Objekte in der HashMap? brauchst du sie überhaupt?
reicht es nicht, nur die Ids zu speichern, dann ginge auch ein HashSet, welches intern aber auch nur eine HashMap verwendet

finde heraus, wie es zu der Langsamkeit kommt, was in der fraglichen Zeit alles passiert,
verwende testweise zum Zeitpunkt der Langsamkeit eine neue leere HashMap statt der alten (-> hats mit der Map zu tun oder nicht)

um wieviele Einträge gehts überhaupt, woher kommen die Daten?

 

[MrVertigo]

Meiner Meinung nach ist das problem die HashMap die zu gross wird. Die ganze Verarbeitung der Daten hat ja funktioniert, nur wurden die Daten bis jetzt nicht auf Duplikate ueberprueft, was nun aber so sein soll.
Also den Teil der die Daten aus der DB holt und den Teil der die Daten dann in das File schreibt habe ich nicht geaendert.

Ich habe nur den Check eingefuegt, der bevor eine Zeile in die Datei geschrieben wird, laeuft.

Nur die IDs aus der DB holen bringt nichts, denn das macht den Prozess noch langsamer.

Um Speicher zu sparen, speichere ich nur die ID in der HashMap, als Object gebe ich NULL mit.

Es handelt sich um ca 1 000 000 Datensaetze.

 

[Gelöschtes Mitglied 5909]

ich würde ein bak.pcj.set.LongOpenHashSet von pcj verwenden

sehr schnell und braucht viel weniger Speicher als die java.util Version

http://pcj.sourceforge.net/

 

[SlaterB]

public class Test
{
    public static void main(String[] args)
        throws Exception
    {
        long time = System.currentTimeMillis();
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 1000000; i++)
        {
            list.add(Integer.valueOf((int)(Math.random() * 900000)));
        }
        System.out.println("time1: " + (System.currentTimeMillis() - time));
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Integer test = Integer.valueOf(-1);

        int countDouble = 0;
        for (Integer k : list)
        {
            if (map.put(k, test) != null)
            {
                countDouble++;
            }
        }
        System.out.println("time2: " + (System.currentTimeMillis() - time) 
             + ", double: " + countDouble);

    }
}

--------

Ausgabe:
time1: 562
time2: 1578, double: 395948

dauert also ungefähr eine Sekunde für 1 Mio. Objekte,

wenn jedes derartige Objekt 1000 Bytes belegt, dann kommt meine Aussage '1 Sekunde für ganzen Speicher' ja ganz gut hin
(wären dann ~1GB)

ich habe hier noch Objekte in die Map gespeichert, um nicht erst contains zu testen und dann noch einzufügen,
so macht es ein HashSet auch, welches du statt der Map verwenden könntest

-----

was dein Programm ansonsten langsam macht, kann ich derzeit nicht erahnen,
die Map braucht 20 MB Speicher