[JAVA] Dubbelen uit Array halen van type String

[verytallman]

So simpel zou je denken....en toch lukt het me niet

Even de situatie: ik heb een Array van type String, ik wil daarin alleen unieke strings, dus de dubbelen eruit.

Dit heb ik nu, even wat toelichting:
tmpIdArray1: array dat gevuld is met strings, waarin mogelijk dubbelen zitten
tmpIdArray2: nieuwe array dat alleen unieke strings moet gaan bevatten
aantalIdentifiers: int van het aantal strings in het array tmpIdArray1
arrayIdIndexArray2: is in het begin op 0 gezet, daarna steeds met 1 verhoogd bij een invoer in tmpIdArray2

Dat tmpIdArray1 goed gevuld is met strings moet je maar even van me aannemen. Anders wordt het teveel code hier.

code:

int arrayIdIndexArray2 = 0;
String[] tmpIdArray1 = new String[aantalIdentifiers];
String[] tmpIdArray2 = new String[aantalIdentifiers]; 

for (int i=0 ; i < aantalIdentifiers ; i++) {
    for (int j=0 ; j < aantalIdentifiers ; j++) {
        if (!tmpIdArray1[i].equals(tmpIdArray2[j])) {
            tmpIdArray2[arrayIdIndexArray2] = tmpIdArray1[i];
            arrayIdIndexArray2++;
        }
    }
}

Mochten er dubbelen zijn, blijven slots open in het array tmpIdArray2. Is dit een probleem?


Edit: Ik krijg allemaal erg goede adviezen over nieuwe technieken, maar ik zou graag willen weten wat er mis is met mijn eigen code !

Ik krijg dus steeds deze foutmelding: ArrayIndexOutOfBoundsException. Het probleem zit hem in deze 2 regels code:

code:

tmpIdArray2[arrayIdIndexArray2] = tmpIdArray1[i];
arrayIdIndexArray2++;

Als ik van die twee regels code commentaar maak (of die regels weg haal) krijg ik die foutmelding niet meer. Maarja dan staat er ook niet meer in het array tmpIdArray2 en heb ik geen array met unieke strings....

[ Voor 20% gewijzigd door verytallman op 08-12-2005 01:10 ]

[Verwijderd]

Gaat het je echt om het algoritme of om de oplossing? Want als het je enkel om de oplossing gaat kun je natuurlijk alle waardes van de array toevoegen aan een Set.

[HeldereM]

Hey, heb ff geen tijd om het uit te leggen... maar kijk hier eens naar... dit hebben wij gebruikt op school

http://java.sun.com/j2se/...java/lang/Comparable.html

[verytallman]

Ik was vergeten om te zeggen welke foutmelding ik krijg:

ArrayIndexOutOfBoundsException: 3

Waarbij het nummer achter de exception altijd het aantal strings is dat in de array tmpIdArray1 zat...

Mark, ik wil altijd weten wat er fout is en niet zomaar doorgaan met een andere oplossing. Maar andere oplossingen sta ik altijd voor open. Maar een Set? Wat bedoel je?

[Jimbolino]

Als de array gesorteerd is kun je het performance technisch het beste met een "bubble sort" algoritme de dubbelen eruit halen

[DaCoTa]

I love oneliners

Java:

int arrayIdIndexArray2 = 0;
String[] tmpIdArray1 = new String[aantalIdentifiers];
String[] tmpIdArray2 = (String[])new TreeSet(Arrays.asList(tmpIdArray1)).toArray();

Tip van de dag: onderzoek Java Collections. Je kan er on-ge-lo-fe-lijk veel mee.

[ Voor 9% gewijzigd door DaCoTa op 08-12-2005 00:58 ]

[verytallman]

DaCoTa schreef op donderdag 08 december 2005 @ 00:57:
I love oneliners

Java:

int arrayIdIndexArray2 = 0;
String[] tmpIdArray1 = new String[aantalIdentifiers];
String[] tmpIdArray2 = (String[])new TreeSet(Arrays.asList(tmpIdArray1)).toArray();

Tip van de dag: onderzoek Java Collections. Je kan er on-ge-lo-fe-lijk veel mee.

Ik heb TreeSet nog niet helemaal doorgenomen maar moet ik niet eerst tmpIdArray1 vullen met strings ?

En na deze code zijn er in tmpIdArray2 alleen nog maar unieke strings uit tmpIdArray1 ?

[Gert]

Een set bevat alleen maar unieke waardes, dus ja die zijn er uit.

Maar als dit een opdracht voor school is, is dat niet de oplossing. Dan gaat het namelijk om sorteren en door datastructuren lopen, niet om zo handig mogelijk gebruik maken van de Java api.

[MetroidPrime]

Het probleem in je code is dat je kijkt of een element uit array A op een bepaalde positie in array B zit en als dit niet zo is voeg je dat element toe aan B en dit doe je voor iedere positie in B.

Je werkt kennelijk met een array met drie Strings. Bij het eerste element uit A controleer je of het gelijk is aan het eerste element uit B. Array B is dan nog leeg, dus je voegt het eerste element uit A toe aan B, waar het op de eerste positie komt te staan. Je controleert dan of het element op de eerste positie van A op de tweede positie van B staat, wat niet zo is en dus voeg je het element nog een keer toe. Zodra je bij het tweede element van A bent, is het aantal elementen in B gelijk aan aantalIdentifiers, wat het maximum is. Het tweede element van A vergelijk je dan met het eerste element van B en omdat die ongelijk zijn probeer je het tweede element van A toe te voegen aan B. Dit gaat mis omdat A vol zit en dus krijg je een ArrayIndexOutOfBoundsException.

Wat je beter kunt doen is een aparte methode maken die controleert of een bepaalde String in een bepaalde array zit. Deze methode zou dan een boolean teruggeven die aangeeft of een String nu wel of niet in een bepaald array van Strings zit. Je geeft als parameters de array en het element dat je wil controleren. Mocht deze methode false teruggeven, dan voeg je het element toe aan het array en anders doe je niets.

[verytallman]

MetroidPrime schreef op donderdag 08 december 2005 @ 01:41:
Wat je beter kunt doen is een aparte methode maken die controleert of een bepaalde String in een bepaalde array zit. Deze methode zou dan een boolean teruggeven die aangeeft of een String nu wel of niet in een bepaald array van Strings zit. Je geeft als parameters de array en het element dat je wil controleren. Mocht deze methode false teruggeven, dan voeg je het element toe aan het array en anders doe je niets.

Bedankt voor je uitleg !
Je oplossing heb ik ook toegepast, met wat hulp van Steven_NL !

code:

  for (int i=0 ; i < aantalIdentifiers ; i++) {
     if (!zitStringInArray(tmpIdArray2, aantalIdentifiers, tmpIdArray1[i])) {
        tmpIdArray2[indexArray2] = tmpIdArray1[i];
        indexArray2++;
        tmpIdentifiers += (tmpIdArray1[i] + " ");
     }
  }

   boolean zitStringInArray (String[] tmpArray, int aantalIdentifiers, String tmpStr) {
      for (int i=0 ; i < aantalIdentifiers ; i++) {
         if (tmpArray[i] != null && tmpArray[i].equals(tmpStr)) {
            return true;
         }
      }
      return false;
   }

[Confusion]

verytallman schreef op donderdag 08 december 2005 @ 00:35:
Mochten er dubbelen zijn, blijven slots open in het array tmpIdArray2. Is dit een probleem?

Wel als je verderop in de code nog een keer over tmpldArray2[0] t/m tmpldArray[aantalIdentifiers] gaat loopen. Als je geen performanceproblemen hebt of verwacht (more than likely) is het veel fijner om met Lists te werken. Zoals iemand hierboven al zegt: kijk eens naar de Java Collections API.

[Woy]

Confusion schreef op donderdag 08 december 2005 @ 08:22:
[...]

Wel als je verderop in de code nog een keer over tmpldArray2[0] t/m tmpldArray[aantalIdentifiers] gaat loopen. Als je geen performanceproblemen hebt of verwacht (more than likely) is het veel fijner om met Lists te werken. Zoals iemand hierboven al zegt: kijk eens naar de Java Collections API.

Het is idd zeker makkelijker om met lijsten te werken aangezien je in lijsten makkelijk elementen kan toevoegen en verwijderen zonder dat je de hele structuur hoeft te kopieren.
Confusius merkt hier al op dat je bij applicaties waar de performace een probleem is/gaat worden je op moet letten dat het opzoeken van een element aan de hand van een index in een lijst een stuk duurder is als bij een array.

Bij een array kan je namenlijk meteen het goede element pakken en bij lijsten moet je vooraf beginnen met de lijst doorlopen om het goede element te vinden. Als je alleen bewerkingen doet waar je over alle elementen itereert en waar je vaak elementen toevoegt/verwijderd dan is een lijst zelfs stukken beter voor de performance.

[Janoz]

rwb schreef op donderdag 08 december 2005 @ 09:15:
Confusius merkt hier al op dat je bij applicaties waar de performace een probleem is/gaat worden je op moet letten dat het opzoeken van een element aan de hand van een index in een lijst een stuk duurder is als bij een array.

Dat is geheel afhankelijk van welke implementatie je kiest. Voor een LinkedList zal het opzoeken dmv een index inderdaad relatief duur zijn, maar het verschil tussen een ArrayList en een primitive array is nihil. Afhankelijk van je behoeftes kun je bepalen welke implementatie het beste bij jouw situatie past.

[.oisyn]

Jimbolino schreef op donderdag 08 december 2005 @ 00:51:
Als de array gesorteerd is kun je het performance technisch het beste met een "bubble sort" algoritme de dubbelen eruit halen

Als de array gesorteerd is hoef je alleen maar van voor naar achter te doorlopen, aangezien alle dubbelen op elkaar volgen (wat O(n) is, ipv de O(n²) van een bubble sort)

[Woy]

Janoz schreef op donderdag 08 december 2005 @ 09:32:
[...]


Dat is geheel afhankelijk van welke implementatie je kiest. Voor een LinkedList zal het opzoeken dmv een index inderdaad relatief duur zijn, maar het verschil tussen een ArrayList en een primitive array is nihil. Afhankelijk van je behoeftes kun je bepalen welke implementatie het beste bij jouw situatie past.

Klopt ik had het idd over een LinkedList. Bij een ArrayList heb je natuurlijk weer het nadeel dat elementen verwijderen/tussenvoegen weer duurder is.
Maar je moet idd per geval bekijken welke structuur het beste voor dat geval is.

[Janoz]

Datzelfde nadeel heb je bij 'primitive' arrays natuurlijk ook

[.oisyn]

Wat overigens nogal betrekkelijk is. Bij een linked list bevinden alle nodes zich kriskras door het geheugen, dit levert nogal veel cachemisses op. En aangezien een ArrayList gewoon een array van Objecten is (typisch 4 bytes per referentie), hoeft er niet eens zoveel rondgekopiëerd te worden, zeker niet als het te verwijderen/inserten element vlakbij het einde van de array ligt. En bij een insert moet natuurlijk evt. de array groter worden gemaakt, maar dat is meestal ook maar ²log n keer, daarnaast zou je van tevoren ruimte kunnen reserveren als je ongeveer weet hoeveel elementen erin komen te staan.

[ Voor 11% gewijzigd door .oisyn op 08-12-2005 13:17 ]

[MetroidPrime]

verytallman schreef op donderdag 08 december 2005 @ 02:40:
[...]

Bedankt voor je uitleg !
Je oplossing heb ik ook toegepast, met wat hulp van Steven_NL !

Aangezien aantalIdentifiers gelijk is aan de grootte van de array, kun je aantalIdentifiers op een aantal plekken vervangen door tmpIdArray.length(). Dan hoef je aantalIdentifiers ook niet meer als parameter door te geven aan zitStringInArray.