Søke i ArrayList

[Woods]

Hei, 

 

lager en funksjon som leter etter likt ord i en ArrayList (bruker .equals() ). Jeg har lært å gjøre dette med vanlige arrayer, dvs. jeg kan eks. bruke en for/while loop hvor "minArray[ i ]" representerer hver celle, slik at jeg kan sammenlikne innholdet. 

 

Jeg er helt fersk med java, setter dermed pris på en forklaring hvordan jeg kan gjøre tilsvarende med ArrayList. 

 

Tusen takk for hjelp

[siDDis]

 

 
for(String item : myList){
    if(item.equals("truls")){
        return item;
    }
}

[Gavekort]

siDDis sitt forslag er riktig, men jeg vil tilføye at dette er en latterlig lite effektiv måte å gjøre et søk på, så hvis du vil ha smiskepoeng så bør du vurdere et HashMap.

[Matsemann]

Det er ikke en "latterlig lite effektiv måte" gitt at man faktisk skal søke i noe som er en liste, som er et veldig vanlig tilfelle.

 

siDDis sitt forslag bruker en iterator. Tilsvarende som for et vanlig array men med lister kan man gjøre sånn her:

for (int i = 0; i < myList.size(); i++) {
    String item = myList.get(i);
    if(item.equals("truls")){
        return item;
    }
}

Men anbefaler siDDis sitt forslag, da det er mye lettere å se hva intensjonen til koden er, da det i dette tilfellet er mye undøvendig rot sammenlignet med:

for(String item : myList){
    if(item.equals("truls")){
        return item;
    }
}

For å dra den enda lengre kan man i java8 skrive det funksjonelt:

return myList.stream().anyMatch(s -> s.equals("truls"));
// evt 
return myList.stream().anyMatch("truls"::equals);

[Gavekort]

Det er ikke en "latterlig lite effektiv måte" gitt at man faktisk skal søke i noe som er en liste, som er et veldig vanlig tilfelle.

 

Å gjøre en 1:1 match av strings i en ArrayList? Det gjør man ikke en O(n) lookup på når man heller kan hashe det man søker etter. Å gjøre en for-each er en naiv fremgang som skalerer ufattelig dårlig.

 

http://www.programcreek.com/2014/04/check-if-array-contains-a-value-java/

 

Litt off-topic, men hva er et nettforum uten at man har noen som kverulerer på detaljer?

[Matsemann]

 

Det er ikke en "latterlig lite effektiv måte" gitt at man faktisk skal søke i noe som er en liste, som er et veldig vanlig tilfelle.

 

Å gjøre en 1:1 match av strings i en ArrayList? Det gjør man ikke en O(n) lookup på når man heller kan hashe det man søker etter. Å gjøre en for-each er en naiv fremgang som skalerer ufattelig dårlig.

Men om du har en liste i utgangspunktet er det det mest effektive. Om du har en liste og skal gjøre en hash-lookup, må du først hashe alle elementene i listen for å bygge hashmapen, altså O(n). Mye overhead i forhold til å iterere over listen. Lenken din viser jo det, løsningen med HashSet er jo en order of magnitude tregere enn foreach.

[Gavekort]

Det er sant at du har en stor overhead når du konstruerer et HashMap, men det gjør du bare én gang, så med mindre det er spesifisert at listen skal endre seg eller at man bare skal gjøre én lookup, så er hashmap sin O(1) (med en stor O(n) første gang) skalering totalt overlegen over den naive for-each metoden som er O(n) hver gang.

 

Jeg tar jo utgangspunkt i at du vil formidle et optimalisert søk, og ikke at oppgaven bare er å dumpe ting i en ArrayList og så finne det igjen. I et real-world scenario så vil et HashMap nesten alltid gi best skalering.

Endret 4. oktober 2016 av Gavekort

[Matsemann]

Nettopp, så det var ikke en "latterlig lite effektiv måte" på generelt basis, da man ofte bare trenger en one-off sjekk.

[Gavekort]

Men det er ikke noe poeng i å la seg drive med vranglære til når man faktisk skal skrive effektiv kode, så det ble ikke poengtert fordi jeg skal være en besserwisser, men heller fordi jeg vil lære TS at det er en naiv metode. Jeg skal ta selvkritikk i at jeg droppet å legge til rette for at jeg snakket om 1:1 ordsøk på generell basis og ikke hva som er best i denne oppgave-settingen.

 

Frustrasjonen min kommer fra kurs som driver å lærer nybegynnere naive metoder fordi de tror det er bedre å gjøre det lett for de på bekostning av at de blir dratt inn i vranglære.

Endret 4. oktober 2016 av Gavekort

[siDDis]

Om vi snakker om kjappere søk av tekst så kan det brukes mange forskjellige teknikker og strategier.

 

Ein eg bruker ganske hyppig idag er XXHash.

 

F.eks så kan du hashe tekststrenger til long også kjøre kjappe lookups på disse tekststrengene i eit btree.

 

For større datamengder så fungerer dette helt ypperlig i databaser / SQL istadenfor å bruke dei mykje tyngre "LIKE" spørringane, samt indeksane blir betydelig mindre. Du mister wildcards då, men om du trenger fleksibilitet så er jo Lucene, Solr, Elasticsearch tingen uansett.