/ Forside / Teknologi / Udvikling / Java / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Java
#NavnPoint
molokyle 3688
Klaudi 855
strarup 740
Forvirret 660
gøgeungen 500
Teil 373
Stouenberg 360
vnc 360
pmbruun 341
10  mccracken 320
Binær søgning og suffix
Fra : Aggeboe


Dato : 23-05-01 16:53

Hej.

Jeg skal søge binært i et array af Ordliste objekter og disse har et String felt.
Metoden skal returnere et index, til det sted i aray'et, hvor string'en findes (ja,
det er en søgemaskine :-] )

x er det ord der søges efter. arr[i].str er string feltet i Ordliste objektet på
plads i, i array arr!

De 3 første if sætninger er standard binær søgning, hvor der hele tiden "indsnævres",
til man er på den rigtige indgang i array'et!

Hvis der ikke er nogen eksakt match træder de tre sidste i brug!
De skulle så gerne sikre, at hvis man så søger på fx. "abe" og abe ikke findes i
array'et, så finder man istedet "abekat", hvis det nu er det første med "abe"... Men
det virker ikke?

Er der nogen der kan se hvorfor dette går galt?

static int binsearch(String x, Ordliste [] arr, int n) {
int a = 0, b = n-1, i;
boolean found = false;

while (!found && a <= b) {
   i = (a+b) / 2;
   System.out.println("1. arr[i].str "+arr[i].str+" x "+x);
      
   if (x.compareTo(arr[i].str) < 0) {
      System.out.println("2. arr[i].str "+arr[i].str+" x "+x);
      b = i-1;
   }
   else if(arr[i].str.compareTo(x) < 0) {
      System.out.println("3. arr[i].str "+arr[i].str+" x "+x);
      a = i+1;
   }
   else if(arr[i].str.compareTo(x) == 0) {
      System.out.println("4. arr[i].str "+arr[i].str+" x "+x);
      return i;
   }
   else if(arr[i-1] != null && arr[i-1].str.startsWith(x)) {
      System.out.println("5. arr[i].str "+arr[i].str+" x "+x);
      return i-1;
   }
   else if(arr[i].str.startsWith(x)) {
      System.out.println("6. arr[i].str "+arr[i].str+" x "+x);
      return i;
   }
   else if(arr[i+1] != null && arr[i+1].str.startsWith(x)) {
      System.out.println("7. arr[i].str "+arr[i].str+" x "+x);
      return i+1;
   }
}
System.out.println("8!");
return -1;
}

/Aggeboe
--
Remove XXX when replying

 
 
Steffen Enni (23-05-2001)
Kommentar
Fra : Steffen Enni


Dato : 23-05-01 20:45


"Aggeboe" <XXXaggeboe@bigfoot.com> wrote in message
news:3B0BDCC2.BF782EEE@bigfoot.com...
>
> Hvis der ikke er nogen eksakt match træder de tre sidste i brug!
> De skulle så gerne sikre, at hvis man så søger på fx. "abe" og abe ikke
findes i
> array'et, så finder man istedet "abekat", hvis det nu er det første med
"abe"... Men
> det virker ikke?

Det vil jeg kalde for en partiel match i denne mail.

> Er der nogen der kan se hvorfor dette går galt?

Ja, du skal vente med at kontrollere for en partiel match til efter du har
afgjort at der ikke er en eksakt match.

Altså: Først binær søgning. Når den er slut, ved du at den søgte streng
ikke er i arrayet. Og så kikker du efter om den plads din søgning endte
ved, er et partielt match.

Du kan se hvordan i nedenstående kode.

---
Steffen Enni
http://www.zachosw.dk


public class Search
{
public String search(String x, String arr[]) {
int n = arr.length;
int a = 0;
int b = n - 1;
while (a <= b) {
file://Invariant: arr[a] ... <=b" + i + "b" + i + " x <= ... arr[b]
int i = (a+b)/2;
int cmp = x.compareTo(arr[i]);
if (cmp < 0) {
b = i - 1;
} else if (cmp > 0) {
a = i + 1;
} else {
return arr[i];
}
}
file://Invariant: a == b+1 hvilket betyder, at
file://man kan være løbet ovenud af arrayet.
file://Ellers check om x er præfix til arr[a]
if (a > (n-1)) {
return null;
} else if (arr[a].startsWith(x)) {
return arr[a];
} else {
return null;
}
}


file://Test driver
public static void main(String args[]) {
String array[] = new String[9];
for(int i = 0; i < array.length; i++)
array[i] = "b" + i + "b";

boolean passed = true;
for(int j = 1; j < array.length; j++) {
passed &= test(array, j);
}
System.out.println(passed ? "OK" : "FAILED");
}


private static boolean test(String arr[], int len) {
String array[] = new String[len];
System.arraycopy(arr, 0, array, 0, len);

Search test = new Search();
boolean passed = true;
for(int i = 0; i < array.length; i++) {
String x = "";
String y = "";

try {
y = "a";
x = test.search(y, array);
if (x != null) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}

y = "b" + i;
x = test.search(y, array);
if (!x.equals("b"+i+"b")) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}

y = "b" + i;
x = test.search(y, array);
if (!x.equals("b"+i+"b")) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}

y = "b" + i + "b";
x = test.search(y, array);
if (!x.equals("b"+i+"b")) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}

y = "b" + i + "c";
x = test.search(y, array);
if (x != null) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}

y = "c";
x = test.search(y, array);
if (x != null) {
System.out.println("Bummer: " + y + ", " + x);
passed = false;
}

} catch (NullPointerException e) {
System.out.println("Bummer " + y + ", null");
passed = false;
}
}
return passed;
}
}









Thorbjørn Ravn Ander~ (23-05-2001)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 23-05-01 21:49

Steffen Enni wrote:

> file://Invariant: a == b+1 hvilket betyder, at
> file://man kan være løbet ovenud af arrayet.
> file://Ellers check om x er præfix til arr[a]
> file://Test driver

Hvor kommer de lidt ... utraditionelle kommentartegn fra?

--
Thorbjørn Ravn Andersen "...plus... Tubular Bells!"
http://bigfoot.com/~thunderbear

Aggeboe (23-05-2001)
Kommentar
Fra : Aggeboe


Dato : 23-05-01 23:01

Steffen Enni wrote:
>
> "Aggeboe" <XXXaggeboe@bigfoot.com> wrote in message
> news:3B0BDCC2.BF782EEE@bigfoot.com...
> >
> > Hvis der ikke er nogen eksakt match træder de tre sidste i brug!
> > De skulle så gerne sikre, at hvis man så søger på fx. "abe" og abe ikke
> findes i
> > array'et, så finder man istedet "abekat", hvis det nu er det første med
> "abe"... Men
> > det virker ikke?
>
> Det vil jeg kalde for en partiel match i denne mail.
>
> > Er der nogen der kan se hvorfor dette går galt?
>
> Ja, du skal vente med at kontrollere for en partiel match til efter du har
> afgjort at der ikke er en eksakt match.
>
> Altså: Først binær søgning. Når den er slut, ved du at den søgte streng
> ikke er i arrayet. Og så kikker du efter om den plads din søgning endte
> ved, er et partielt match.
>
> Du kan se hvordan i nedenstående kode.

Ja, det fandt jeg ud af, øv.
Rykkede de sidste 3 if sætninger uden for while løkken og så virkede det nogenlunde.
Så er der lige lidt gymnastik, hvis man kun vil have binær søgning eller binær med
suffix, men det skulle kunne klares...

/Aggeboe
--
Remove XXX when replying

Ulrik Magnusson (24-05-2001)
Kommentar
Fra : Ulrik Magnusson


Dato : 24-05-01 00:09

Aggeboe wrote:

> Hvis der ikke er nogen eksakt match træder de tre sidste i brug!
> De skulle så gerne sikre, at hvis man så søger på fx. "abe" og abe ikke findes i
> array'et, så finder man istedet "abekat", hvis det nu er det første med "abe"... Men
> det virker ikke?
>
> Er der nogen der kan se hvorfor dette går galt?

Så vidt jeg kan se, fordi du aldrig kommer forbi de 3 compare "cases".
Mit forslag til en løsning er:

suffix = -1;
for()
{
if( startsWith )
{
suffix = index
}
if( equals )
{
return index
}
else if( lessThan ) // gå til venstre
else if( biggerThan ) // gå til højre
}
return suffix

hvis search( ar, s ) giver -1 blev hverken suffix eller præcist match fundet.
hvis ar[search( ar, s )].length() == s.length() blev et præcist match fundet.
ellers blev der fundet et suffix match

Ulrik Magnusson

--
"Less we love and know how we're just morter filling holes"
Skinny Puppy - 'Morter', The Process 1996
Visit my home page: http://www.geocities.com/ulrikm




Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste