Hvilken datastruktur bør jeg anvende?

Du skal have bruge en sorteret liste af en slags.

Du kunne bruge java.util.TreeSet, men hvis du ved hvor mange ord du
skal loade inden du loader, så vil et godt gammeldags simpelt array
nok være lige så godt.

Der skal aldrig fjernes noget og kun indsættes ting een enkelt gang. Det din struktur først og fremmest skal bruges til er at slå op. så den del skal prioriteres.

Noget andet der skal prioriteres er plads. en mobilos har ikke for meget.
så jeg ville nok vælge et hashmap. eller måske sågar noget så simpelt som en perfekt heap, implementeret i 2 arrays som du så sifter dine entries ned i. (den er tung at bygge, men når den først er bygget er den hurtig at søge i og fylder endnu mindre end den der hashtabel).

mvh JakobA

Men pointen er at det skal være sorteret og relativt nemt at finde
alle der starter med "int".

Og det er eget nemt at finde i et sorteret simpelt array.

Jakob>

Det er ikke særligt nemt at finde alle der starter med "int" i en
HashMap.

Helt enig. dit sorterede array er faktisk bedre her

Det er faktisk et kendt tradeoff.

                eksakt find          starter med find
hash              O(1)                    O(n)
binær            O(log(n))            O(log(n))

Kunne man forestille sig at lave en form for hashmap med arrays som buckets...? Er det der i vil hen?

Du mener key=første bogstav og value=simpelt array med alle med det forbogstav ?

Det kunne man godt.

Ja det var precis det jeg tænkte...Ville du gøre det på en anden måde?

Jeg tror at jeg ville gå efter et simpelt array.

Gevindsten i hastighed ved HashMap + array vil ikke være så stor
og det vil give mere kode.

Men forskellen er ikke stor.

Hvis jeg lige var i hash map humøret, så kunne det også blive den
løsning.

Ét enkelt array? Jeg synes at det lyder vildt...Kan du ikke sætte en ca værdi på hvor mange ord du mener at dette array kunne indeholde og stadig være nogenlunde hurtigt?

Husk du laver binær søgning !

1 ord = 1 sammenligning
2 ord = 2 sammenligninger
4 ord = 3 sammenligninger
8 ord = 4 sammenligninger
16 ord = 5 sammenligninger
...
1024 ord = 11 sammenligninger
...
4 milliarder ord = 33 sammenligninger

En ordbog vil vel typisk indeholde 10000-100000 ord - det giver
15-18 sammenligninger.

Det er ikke noget problem.

Jeg har netop færdiggjort det...Jeg lavede hashmap med første bogstav som key og en arraylist som værdi.. Pænt?? Måske ikke, men den søger på max 1/100 af et sekund med 60.000 ord i sin map....Det er godt nok til mig...BTW er der nogen der har et link til en fil med alle danske ord??

Arne>> Smid et svar

Jeg kan ikke vurdere om det er hurtigt eller langsomt i frohold til
problem-stilline, så måtte jeg teste forskellige løsninger og
sammenligne.

Men det betyder heller ikke så meget. Det relevante er at 1/100 sekund er
mere end tilstrækkeligt til at løse opgaven til brugerens tilfredshed.

>>BTW er der nogen der har et link til en fil med alle danske ord??
http://da.speling.org/filer/dsdo-1.4.26.zip

Noget kunne tyde på denne var nyere:
http://da.speling.org/filer/dsdo-1.4.27.zip

:=)

Tak til alle Arne, soreno og jakoba ... Så mangler jeg bare lige at høre om en sidste ting... Filen jeg henter med alle de danske ord er en flad fil med alle ord adskildt af små firkanter...Representerer disse firkanter et linieskift når teksten formateres?
Hvordan fanges disse af java´en? indtil videre har jeg brugt en filereader der læser en linie ad gangen og fyrer det hele ind i en Stringtokenizer for at kunne skille ordene ad...Hvordan får jeg fanget og individualliseret de nye ord?

Soreno>> læg lige et svar

Også Jacoba..Læg et svar...

Jeg har forhøjet pointantallet så der er nok til alle

Hvis jeg skulle gætte:

så kører du Windows, bruger en editor som kun genkender <CR><LF> som
linieskift og filen bruger <LF>.

Løsning hvis rigtigt gæt:

hiv filen ind i en edtor som genkender <LF> og få den til at gemme
som <CR><LF>.

NB: Laver du binær eller sekventiel søgning i arrayet du henter ud ?

Sekventiel... for(i=0;i<al.size;i++)

Binær ville nok hjælpe en del når nu jeg kommer op over 300.000 ord

Kan ultraedit klare den tror du...Jeg prøver...

Ja.

Lad os sige at det mest hyppige bogstav har 15000 ord.

Linær worst case er 15000 sammelgninger.

Binær worst case er 15 sammenligninger.

Det kan muligvis mærkes.

Jeg vil tror at UE kan læse begge og gemme i eksplicit format.

Det kan jeg slet ikke overskue i UE...Har du et tip til en editor der kan køre i windows og tager 2 sek. at hente?

Ikke 2 sekunder.

JEdit fra www.jedit.org bruger jeg selv en hel del (jeg kan nemlig bruge
den på Windows, Linux, VMS etc.)

I den er det:
  utilities
  buffer options
  line separator

Svar

Binær søgning er det med at vælge midten og derefter se om objektet er størrer eller mindre end det man leder efter, og derefter dele op igen osv...?
Og hvorfor hedder det egentlig binær søgning?

Ja.

bi=2 og man deler op i 2 dele.

Ok selvfølgelig :)

Der er stadig lidt af et problem...Jeg skal jo ikke søge efter ét ord i min hashmap. Den skal returnere en liste af ord der starter med de indtastede bogstaver.. Kan man stadig anvende binær søgning til det??
på nuværende tidspunkt returnerer mit hashmap en arraylist af Strings som starter med de bogstaver man spørger efter...

Måske skulle jeg lave et hasmap med et bogstav som nøgle og et nyt hashmap som værdi hvori dette ordets 2.bogstav var nøgle en arraylist var værdien?

Det troede jeg at du havde lavet.

HashMap til at finde array med alle ord der starter med bogstav og så
søgning i det array efter ord.

Og at du kun skulle skifte fra sekventiel søgning til binær søgning indenfor
det array.

Og selvfølgelig kan man anvende binær søgning i det array.

Eneste krav er at data er sorteret.

Hvordan vil du håndtere ord på 1 bogstav ?

Det havde jeg også lavet...Jeg har et hashmap med forbogstavet som nøgle og en arraylist med stringobjekter som værdi..Det virker fint der er 380000 ord i. Men jeg vil nu ændre det fra sekventiel til binær søgning. Jeg har konstrueret det således at man tilgår mit hashmap via en metode der får en String med som parameter. Denne metode returnerer en arraylist med de stringobjekter fra hashmappen der starter med den string man sendte med som parameter.

Alt dette foregår sekventielt, det vil sige via. en forlykke der kører igennem en af hashmappens arraylister (alt efter forbogstav) og hiver matchende resultater(sammenlignet på forbogstaver) ind i en ny arraylist som den returnerer...Det er dette jeg gerne ville have gjort binært...

Jeg har valgt ikke at ville håndtere ord på 1 bogstav.

Man søger aldrig på 1 ord...Man søger på ord der starter med xxx...

Det er vel bare at implementere din binære søgning i det array du står med !?

Eller vil du gerne se et eksempel på binær søgning ?

Det kan godt være at jeg ikke fatter det helt, men er binær søgning ikke kun ideélt hvis jeg vil søge på et aksakt ord, det jeg søger efter er jo alle ord der starter med xxx, altså skulle den binære søgning jo resultere mere end et match...Bliver den så ikke sekventiel alligevel??
jeg søger efter 'and'...Den binære søgning halverer indtil den står med 'andalusien'...Hvad herefter??? Skal den søge igen for at finde 'andedam', 'anders' og 'andres'??

Det er meget muligt at jeg ikke kan se skoven for bare træer.. :)

(for points selvfølgelig)

Der manglede lige noget i tråden:

Du må da meget gerne komme med et eksempel på en binær søgning der returnerer en række resultater baseret på forbogstaver fra et array (for points selvfølgelig)

Jeg prøver lige at lave et simpelt eksempel (simpelt = færre end 380000 ord).

Hehe...Fedt tak :)

cas  >> er også igang med at lave et eksempel (også for min egen fornøjelse) ...  Men jeg tænkte på... skal det være en "nummer-styret" opslagsmetode, dvs. tasten "2" dækker over A, B og C ; "3" dækker over D E og F lige som når man skriver "hurtige" sms'er på nokia-telefoner...


mvh
/23274849 (bearhugx)

bearhugx >> Nej den kører direkte på tasterne på tastaturet :)

ok..

import java.util.Arrays;
import java.util.HashMap;

public class NameLookup {
    private HashMap data = null;
    public NameLookup() {
        data = new HashMap();
        String[] as = { "Arne", "Anders", "Asger", "Allan" };
        String[] bs = { "Børge", "Benny", "Brian", "Billy", "Bastian", "Bo", "Benjamin", "Be" };
        String[] cs = { };
        Arrays.sort(as);
        Arrays.sort(bs);
        Arrays.sort(cs);
        data.put("A", as);
        data.put("B", bs);
        data.put("C", cs);
    }
    public String matches(String s) {
        if(s.length() < 1) {
            return "";
        }
        String[] a = (String[])data.get(s.substring(0,1));
        if(a == null) {
            return "";
        }
        if(a.length <= 0) {
            return "";
        }
        StringBuffer sb = new StringBuffer("");
        int l = 0;
        int lmax = a.length - 1;
        while(lmax > l) {
            int med = (l + lmax) / 2;
            int cmp = s.compareTo(a[med]);
            if(cmp <= 0) {
                lmax = med;
            } else if(cmp > 0) {
                l = med + 1;
            }
        }
        if(a[l].indexOf(s) != 0) {
            return "";
        }
        int r = l;
        while((r < a.length) && (a[r].indexOf(s) == 0)) {
            r++;
        }
        for(int i = l; i < r; i++) {
            if(i > l) {
                sb.append(" ");
            }
            sb.append(a[i]);
        }
        return sb.toString();
    }
    private static NameLookup wl;
    public static void main(String[] args) {
        wl = new NameLookup();
        test("As");
        test("Ax");
        test("Be");
        test("Ba");
        test("Bø");
        test("B");
        test("Ca");
        test("De");
    }
    public static void test(String s) {
        System.out.println(s + " : " + wl.matches(s));
    }
}

Koden blev ikke så pæn.

Men output ser korrekt ud:

As : Asger
Ax :
Be : Be Benjamin Benny
Ba : Bastian
Bø : Børge
B : Bastian Be Benjamin Benny Billy Bo Brian Børge
Ca :
De :

Man kunne naturligvis også finde r med en binær søgning, men det er næppe
umagen værd.

Ok...Jeg ser ideen, tak for koden...Den virker men kommer engangimellem med et ukorrekt output..Jeg kigger selv på det og finder fejlen :)

Hvor mange points synes du at dit 2. svar er værd?? Så opretter jeg et nyt spørgsmål.... :)

Ukorrekt output ? Det lyder ikke godt !

Kan du sige i hvilke tilfælde det går galt ?

Point ?

Det vil jeg helt overlade til dig !

Hej...Jeg har lavet et nyt spørgsmål med points i til dig(http://www.eksperten.dk/spm/408016). Angående fejlen så skal jeg nok vende tilbage...jeg ved ikke endnu hvornår men tiden er lidt knap...Tak for Hjælpen.

Mvh Casualty