Meer multidimensionale arrays, hoe duplicaten verwijderen?

[Wijnbo]

Misschien een heel simpele vraag maar kom er even niet uit: Ik heb een lijst met multidimensionale arrays, dus zoiets:

ArrayList<Integer[][]>

Nu wil ik binnen deze arraylist de duplicaten verwijderen, dus stel de lijst bevat :

op 1 : [0,0,0][0,1,1]
op 2 : [0,0,0][0,1,2]
op 3 : [0,0,0][0,1,1]
op 3 : [1,0,0][0,1,1]

Dan wil ik nummer 3 er uit gooien, de rest houden.Heb geprobeerd om met contains te checken alvorens ze in te voegen, maar:

Java:

ArrayList<Integer[][]> integers = new ArrayList<Integer[][]>();
        integers.add( new Integer[][]{{1},{2}} );
        if(integers.contains( new Integer[][]{{1},{2}} ) )
            System.out.println( "BLAAT" );

Geeft geen blaat weer (omdat het een nieuw object is en dus een andere hash?). Hoe los ik dit op een handige manier op?

[Marcj]

De contains functie van een List roept de equals functie van de array aan. Helaas is deze in java niet geimplementeerd zoals je nu verwacht, maar is deze effectief hetzelfde als array1 == array2.

Een oplossing hiervoor is om Arrays.deepEquals(array1, array2) te gebruiken.

[Wijnbo]

Java:

int[][] a = new int[][]{{1,1,1},{2,2,2},{3,3,3}};
int[][] b = new int[][]{{1,1,1},{2,2,2},{3,3,3}};
System.out.println( a.equals( b ));
System.out.println( Arrays.deepEquals( a, b ));

- false
- true

Werkt!

Die deepequals had ik gemist... Thx!

[ Voor 5% gewijzigd door Wijnbo op 27-11-2008 10:49 ]

[Wijnbo]

Hm, nu ben ik er nog niet echt. Moet nu nog checken of Arraylist dus dubbele waarden bevat. Hoe doe ik dat?

[Haan]

De enige manier die ik zo even kan bedenken is dat je door de items in de ArrayList heenloopt en ze vergelijkt met alle items die verderop in de lijst staan. Kom je dan een gelijke tegen, gooi je die uit de lijst.

[GrooV]

Wijnbo schreef op donderdag 27 november 2008 @ 11:42:
Hm, nu ben ik er nog niet echt. Moet nu nog checken of Arraylist dus dubbele waarden bevat. Hoe doe ik dat?

Je hebt in de ArrayList met multidimensionale arrays? Ik denk dat je het beste er gewoon doorheen kan lopen met deepEquals voordat je hem toevoegt. Of naderhand dat je een voor een bekijkt of hij al bestaat

[ Voor 7% gewijzigd door GrooV op 27-11-2008 11:52 ]

[Wijnbo]

GrooV schreef op donderdag 27 november 2008 @ 11:52:
[...]


Je hebt in de ArrayList met multidimensionale arrays? Ik denk dat je het beste er gewoon doorheen kan lopen met deepEquals voordat je hem toevoegt. Of naderhand dat je een voor een bekijkt of hij al bestaat

Daar was ik al bang voor Beetje jammer dat ik een ENORME arraylist heb, met max 1,6 miljoen multidimensionale arrays. Als ik die helemaal moet door lopen voor elke entry, ga ik dat niet in m'n heap redden Denk dat ik het maar exporteer naar TXT ofzo, en vervolgens duplicaten er uit ga vissen

[.oisyn]

Gooi ze dan in een Set, of sorteer ze eerst.
En als je weinig duplicaten hebt kun je ook een Bloom filter overwegen.

[ Voor 58% gewijzigd door .oisyn op 27-11-2008 12:23 ]

[Marcj]

Is het dan ook niet makkelijker om een eigen klasse te definieren waarin je die multidim-array plaatst? Dan kun je zelf makkelijk de equals() en hashcode() methodes overriden. Daarna kun je inderdaad gewoon een Set gebruiken.

[Hydra]

Marcj schreef op donderdag 27 november 2008 @ 12:34:
Is het dan ook niet makkelijker om een eigen klasse te definieren waarin je die multidim-array plaatst? Dan kun je zelf makkelijk de equals() en hashcode() methodes overriden. Daarna kun je inderdaad gewoon een Set gebruiken.

Die doet bij een contains() ook niks anders dan gewoon de hele lijst checken Ik snap niet helemaal waarom de heap voor de TS een probleem zou zijn, die lijst wordt alleen maar kleiner.

[.oisyn]

Dat was idd een beetje een loze opmerking van de TS, maar dat algoritme is wel O(n²), wat je met 1.6 miljoen elementen zeker goed gaat merken.

Maar waarom zou een Set over alle elementen heen lopen? Nou ben ik geen Java guru, maar als ik zo snel in de docs kijk dan zijn alle classes die extenden van Set gebaseerd op hashtables of gebalanceerde bomen. Zeker geen O(n²) dus.

[ Voor 84% gewijzigd door .oisyn op 27-11-2008 16:10 ]

[Soultaker]

Marcj schreef op donderdag 27 november 2008 @ 12:34:
Is het dan ook niet makkelijker om een eigen klasse te definieren waarin je die multidim-array plaatst? Dan kun je zelf makkelijk de equals() en hashcode() methodes overriden. Daarna kun je inderdaad gewoon een Set gebruiken.

Dit wilde ik ook suggeren. In Java lenen arrays zich mijns inziens niet zo om als value-types te gebruiken, dus wrap ik ze bij voorkeur ook in een object.

Een simper alternatief is het implementeren van een Comparator voor je lijsten (die dan gewoon Arrays.deepCompare() aanroept als dat is wat je wil) en die Comparator meegeven bij het construeren van de Set.

[Hydra]

.oisyn schreef op donderdag 27 november 2008 @ 16:05:
Maar waarom zou een Set over alle elementen heen lopen? Nou ben ik geen Java guru, maar als ik zo snel in de docs kijk dan zijn alle classes die extenden van Set gebaseerd op hashtables of gebalanceerde bomen. Zeker geen O(n²) dus.

Zou goed kunnen, ik ging uit van een linkedlist of arraylist achtige collection. Sowieso zou je het handiger aan kunnen pakken door een sorted list / tree te gebruiken en bij het inserten al te kijken of 'ie al bestaat. Neem aan dat die data ergens ingelezen wordt.

[.oisyn]

Een Set dus, daar hebben we het al de hele tijd over . Een ArrayList of LinkedList is geen Set. Een eigenschap van een set is dat elementen er maar 1 keer in staan (en dat volgorde verder niet boeit). ArrayLists en LinkedLists zijn sequences, waarbij volgorde wel uitmaakt en elementen er bovendien meerdere keren in mogen staan.

[ Voor 111% gewijzigd door .oisyn op 27-11-2008 17:09 ]

[Janoz]

HashSet hoeft inderdaad alleen maar in zijn eigen bucket te kijken. Met een slechte implementatie van de hashcode is dat natuurlijk nog steeds N^2, maar de 'gemiddelde' case is een stuk efficienter. Een SortedSet zoals TreeSet doet het iig in O log N.