[TableModel] Doppelte einträge finden (bzw. verhindern)

[finupsen]

Hallo,

Ich wollte mal wissen, wie man es am besten macht, wenn man doppelte einträge in einem Vector-Vector (TableModel)
verhindern will. Mein erster gedanke war pro "addRow" eine iteration auf den gesamten vector zu machen und im fall
einer übereinstimmung das "addRow" zu verwerfen. Ich vermute aber das könnte sehr performance-kritsch werden,
insbesondere dann, wenn das TableModel bereits 50000 einträge oder mehr hat.

Wie sind eure erfahrungen damit (bzgl. performance) und gibt es für sowas spezielle lösungen ?

vielen dank schonmal im vorraus
Andy

 

[Wildcard]

Wie währ's statt mit Vectoren mit Hashtable oder Hashmap. Da können gar keine doppelten rein.

 

[Beni]

Dein Vorschlag wäre ein O( n^2 )-Algorithmus (das Positive: man kann noch schlimmere Algorithmen schreiben :wink

Eine Variante: die Einträge in der Tabelle sortieren, und dann suchen. Sortieren kann man in O( n log n ) (siehe Collections.sort..., bzw. Arrays.sort), und in einem sortierten Array nach doppelten Vorkommen suchen geht in O( n ) (weil doppelte Einträge immer Nachbarn sein müssen).

Andere Variante: Wenn du zusätzlich zu einer Tabelle eine HashMap/Table/Irgendwas (Hauptsache HASH) machst, kannst du in O(1) überprüfen, ob ein Element schon in der Tabelle ist (allerdings: zusätzliche Datenstruktur. Bei 50000 muss man sich langsam Gedanken über den Platz machen?).

Der erste Vorschlag ist gut, wenn du erst in der gefüllten Tabelle suchen musst, der zweite wenn du beim Einfügen prüfen willst.

 

[finupsen]

hallo,

> Eine Variante: die Einträge in der Tabelle sortieren, und dann suchen.

Ja, das mache ich bereits um der tabelle eine sort-funktion zugeben. also: Collections.sort(vector, comparator);
Bei ca. 50000 einträgen dauert das sortieren etwa 500mS was auch akzeptabel ist. Wenn ich aber jedesmal
ein sort pro addRow() starte, wäre das auch nicht sonderlich gut.
Dazu muss ich noch anmerken, daß die addrows alle auf einen schlag kommen. Ist also keine user-aktion sondern
ein laufender thread der die daten in den vector schiebt.

> Andere Variante: Wenn du zusätzlich zu einer Tabelle eine HashMap/Table/Irgendwas (Hauptsache HASH) machst,

Also parralel zu meinem model noch ein hashmap... das klingt garnicht schlecht. Was den platz betrifft: da müsste ich
wohl schleunigst dafür sorgen, daß wenn kein addrow mehr zu erwarten ist, dieses hashmap vom heap verschwinden
zulassen, oder ?

Eine andere sache die mir grade noch eingefallen ist, ist zusätzlich die einträge noch in eine mysql-db zuschreiben
wärend ein bestimmtes feld als UNIQUE deklariert wurde. Kommt eine duplicate-exception zurück wird addrow
verworfen. BTW. ich verwende in der applikation ohnehin mysql.

aber ich glaube da ist wohl ein hashmap deutlich schneller unterwegs , oder ?