[Java] Efficient Vectoren vergelijken

[Deddiekoel]

Ik vraag me af of er een efficientere manier is om Vectoren met elkaar te vergelijken. Ik ben momenteel het volgende aan het doen. Ik heb een recordset uit een database opgeslagen in vectoren. Dus ikheb per recordset 1 vector die weer uit andere vectoren bestaat per record.

Ik heb momenteel 2 recordsets van 55000 en 11000 records. Het is de bedoeling dat ik bepaal welke records uit recordset A niet voorkomen in recordset B. De records in de recordset bevatten vier dezelfde kolommen maar recordset B heeft nog een extra kolom. Momenteel vergelijk ik deze recordsets door door recordset B te loopen en voor elke record door recordset A te loopen totdat ik een hit heb. Als ik die heb stopt de loop.

Dit proces werkt goed maar heeft zijn tijd nodig. Dus vroeg ik me af of er geen efficientere manier is...

[Janoz]

Is het misschien niet handiger om dit gelijk al in de db queries eruit te filteren?

Daarnaast gebruik je op dit moment een O(n²) algoritme. Het is dus een stuk goedkoper om eerst beide lijsten te sorteren. Dan hoef je namelijk niet voor elk element uit de ene lijst de complete andere lijst door. in dat geval wordt het een O(N+ NlogN) algoritme.

[Verwijderd]

Deddiekoel schreef op 29 oktober 2004 @ 12:05:


Dit proces werkt goed maar heeft zijn tijd nodig. Dus vroeg ik me af of er geen efficientere manier is...

Misschien kun je de vectoren sorteren en dan een soort van binairy search alogoritme toepassen. Dat zou de snelheid zeker ten goede moeten komen.

[Macros]

Ja, gebruik Collections.binairySearch(), zorg wel dat de Lists gesorteerd zijn en dat je een goede Comparator voor het sorteren en de binairySearch gebruikt.

[Deddiekoel]

In de DB filteren is geen optie. Het is juist de bedoeling om de database te ontlasten.

Op zich zijn de vectoren al gesorteerd op een kolom (kunnen er natuurlijk meer worden). Het is momenteel zo dat Recordset A is opgebouwd uit weer twee andere recordsets. Maar die kunnen ook weer los van elkaar worden vergeleken.

Ik snap alleen niet hoe ik van een O(n²) naar een O(N+ NlogN) algoritme ga. Ook heb ik geen idee wat een binairy search is...

[Janoz]

Waarom nog binairy search? Waneer beide lijsten gesorteerd zijn kun je gewoon bij beiden aan het begin beginnen. Zijn de elementen gelijk, dan heb je d'r 1 gevonden. Is de ene kleiner dan de andere dan ga je in die lijst een stap verder. Dit doe je net zo lang todat je aan het einde van 1 van de lijsten aangekomen bent.

[Soultaker]

Als gelijkheid voor je records goed gedefinieerd is (de equals()-methode dus), dan kun je gewoon een Set object gebruiken. In je Set stop je alle elementen, en vervolgens haal je met removeAll alle elementen uit de andere verzameling eruit.

[Robtimus]

De xxxAll methods van Set zijn idd handig ja

Java:

// verschil set1 - set2
Set diff = new HashSet(set1);
diff.removeAll(set2);

// union van set1 en set2
Set union = new HashSet(set1);
union.addAll(set2);

// intersectie van set1 en set2
Set intersection = new HashSet(set1);
intersection.retainAll(set2);

// kijken of set2 een subset van set1 is
boolean subset = set1.containsAll(set2);

[Deddiekoel]

Zou voor Set.removeAll ook werken als set1 veel kleiner is dan set2. Haalt hij dan alleen de elementen uit set1 die voorkomen in set2?

[Deddiekoel]

Ik haal eerst gegevens op uit Database X. Daarna ga ik naar database Y en haal daar twee recordsets op...
Momenteel plak ik die twee recordsets uit dbase Y aanelkaar. Het is dus de bedoeling om om de records te vinden die wel in de recordset uit X zitten maar niet in de recordsets uit Y.

Doordat ik met twee recordsets zit kan ik ze niet simpel orderen...

[_js_]

UNION gebruiken? (zie sql handleiding voor jouw database)

[Soultaker]

...en een UNION is hier niet bruikbaar.

[Robtimus]

Deddiekoel schreef op 29 oktober 2004 @ 13:06:
Zou voor Set.removeAll ook werken als set1 veel kleiner is dan set2. Haalt hij dan alleen de elementen uit set1 die voorkomen in set2?

Removes from this set all of its elements that are contained in the specified collection (optional operation). If the specified collection is also a set, this operation effectively modifies this set so that its value is the asymmetric set difference of the two sets.

Ja dus.

Eventjes de code in 1.4.2:

Java:

public boolean removeAll(Collection c) {
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator i = iterator(); i.hasNext(); ) {
            if(c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

Er wordt dus geitereerd over de kleinste van de 2. Remove levert alleen false als het element niet in de collectie zit.

[Deddiekoel]

Hmmm, dat is interessant! Maar hoe ga ik van een vector naar een set... Dat ga ik maar eens uitzoeken.

[Macros]

Java:

Set set = new HashSet(vector);

[Soultaker]

Zullen we de code ook nog even voor je schrijven, compileren en inleveren bij je baas? IceManX heeft al veel meer voorbeeldcode gegeven dan nodig was; als je er nu nog niet uit kunt komen kun je beter ander werk zoeken.

[ Voor 3% gewijzigd door Soultaker op 30-10-2004 11:16 ]

[Deddiekoel]

Thanks!

Dit is wat ik nu ga doen. Ik ga eerst door de recordset met 4 kolommen loopen. In die loop haal ik steeds de 4e kolom eruit. Dan maak ik van die Vector een Set. Van de 'gecombineerde' vector maak ik dan ook een Set en ga dan met RemoveAll aan de slag.

Dit lijkt mij de meest logische aanpak. Alhoewel ik wel een snellere oplossing zou willen voor het verwijderen van de 4e kolom uit de recordset. Maar 1 keer loopen is natuurlijk beter dan 55000 keer!