Avatar billede dennish Nybegynder
08. september 2009 - 10:59 Der er 11 kommentarer og
1 løsning

Hvilke datastruktur til at implementere en SQL, LIKE% søgning

Hej jeg står og skal implementre følgende:
Jeg har en String såsom aa. Jeg har en tabel indeholdende cirka 30.000 elementer. Jeg vil gerne finde alle forekomster der begynder med aa i tabellen. Jeg vil gerne loade tabellen op i memory (pga performance) og derefter søge efter alle strenge der begynder med aa. Men jeg kan ikke lige finde ud af hvordan jeg får implementeret den meste hensigtsmæssige søgning. Pt. looper jeg over alle elementer i tabellen(ligge pt i en ArrayListe) og hvis der er en match så tilføjer jeg elementet til den list jeg returnerer. Det betyder så at jeg skal loope igennem alle 30.000 elementer. Findes der ikke en god datastruktur der performer godt ? jeg tænker på noget a la et søgetræ, binærtsøgetræ eller ligende.
Avatar billede dennish Nybegynder
08. september 2009 - 12:41 #1
Jeg har nu følgende:


import java.util.Enumeration;
import java.util.Hashtable;

public class PartialSearcher {
    Hashtable hash;
    String[] sortedArray;
    /**
    * @param args
    */
    public static void main(String args[]){
    Hashtable h = new Hashtable();
    h.put("hello", new Integer(1));
    h.put("hell", new Integer(2));
    h.put("alpha", new Integer(3));
    h.put("bye", new Integer(4));
    h.put("hello2", new Integer(5));
    h.put("solly", new Integer(6));
    h.put("sally", new Integer(7));
    h.put("silly", new Integer(8));
    h.put("zorro", new Integer(9));
    h.put("hi", new Integer(10));
    PartialSearcher p = new PartialSearcher(h);
    String args1 = "h";
    Object[] objs = p.match(args1);
    for(int i = 0; i < objs.length; i++)
        System.out.println(objs[i]);
    }
//    if(args.length == 0){
//        System.out.println("Usage: Search string missing.");
//        return;
//    }
//    else{
//        Object[] objs = p.match(args[0]);
//        for(int i = 0; i < objs.length; i++)
//        System.out.println(objs[i]);
//    }
//    }

    public PartialSearcher(Hashtable h){
    hash = h;
    createSortedArray();
    }

    public Object[] match(String s){
    int startIdx = binarySearch(sortedArray, s, 0, sortedArray.length-1);
    int endIdx = binarySearch(sortedArray, s+ '\uFFFF', 0, sortedArray.length-1);
    Object[] objs = new Object[endIdx-startIdx];
    for (int i = startIdx ; i < endIdx; i++)
        objs[i-startIdx] = sortedArray[i];
    return objs;
    }

    public void createSortedArray(){
    sortedArray = new String[hash.size()];
    Enumeration e = hash.keys();
    for(int i = 0; e.hasMoreElements(); i++)
        sortedArray[i] = (String)e.nextElement();
    quicksort(sortedArray, 0, sortedArray.length-1);
    }
    /**
    *
    * Takes on average O(Log N). Requires sorted data.
    */
    public static int binarySearch(String[] arr, String elem, int fromIndex, int toIndex){
    int mid,cmp;
    while (fromIndex <= toIndex){
        mid =(fromIndex + toIndex)/2;
        if((cmp = arr[mid].compareTo(elem)) < 0)
        fromIndex = mid + 1;
        else if(cmp > 0)
        toIndex = mid - 1;
        else
        return mid;
    }
    return fromIndex;
    }
    /**
    * Take on average O(N log N). Worst case is O(N^2)
    *
    *
    */
    public void quicksort(String[] arr, int lo, int hi){
    if(lo >= hi)
        return;
    int mid = (lo + hi) / 2;
    String tmp;
    String middle = arr[mid];
    if(arr[lo].compareTo(middle) > 0){
        arr[mid] = arr[lo];
        arr[lo] = middle;
        middle = arr[mid];
    }
    if(middle.compareTo(arr[hi]) > 0){
        arr[mid] = arr[hi];
        arr[hi] = middle;
        middle = arr[mid];
        if(arr[lo].compareTo(middle) > 0){
        arr[mid] = arr[lo];
        arr[lo] = middle;
        middle = arr[mid];
        }
    }
    int left = lo + 1;
    int right = hi - 1;
    if(left >= right)
        return;
    for( ;; ){
        while(arr[right].compareTo(middle ) > 0){
        right--;
        }
        while(left < right && arr[left].compareTo(middle) <= 0){
        left++;
        }
        if(left < right){
        tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        right--;
        }
        else{
        break;
        }
    }
    quicksort(arr, lo, left);
    quicksort(arr, left + 1, hi);
    }
}

So far so good. Jeg benytter binarySearch, der jo kræver at ens data er sorteret. Så derfor pre steppet quicksort, der sorterer data inden der søges i data. Hvad er så fordelen ved binarySearch ? da jeg jo alligevel i quicksort skal traverser alle elementer. Kan jeg så ikke i stedet for lave en ganske almindelig lineær søgning (for løkke) der loop igennem alle ikke sorterede elementer ? En anden ting er at den mængde data jeg gerne vil søge i ændre sig hele tiden(insert). Så er det måske mere hensigtsmæssigt at implementere et B+Træ ? og så lave en partial søgning i B+ træet ?
Avatar billede arne_v Ekspert
09. september 2009 - 01:43 #2
Prøv og kig på:

TreeMap<String,Integer>
Avatar billede arne_v Ekspert
09. september 2009 - 01:52 #3
Kode eksempel:

package september;

import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Searching {
    public static void main(String[] args) {
        TreeMap<String,Integer> h = new TreeMap<String,Integer>();
        h.put("hello", new Integer(1));
        h.put("hell", new Integer(2));
        h.put("alpha", new Integer(3));
        h.put("bye", new Integer(4));
        h.put("hello2", new Integer(5));
        h.put("solly", new Integer(6));
        h.put("sally", new Integer(7));
        h.put("silly", new Integer(8));
        h.put("zorro", new Integer(9));
        h.put("hi", new Integer(10));
        SortedMap<String, Integer> h2 = h.subMap("h", "i");
        for(Entry<String,Integer> e : h2.entrySet()) {
            System.out.println(e.getKey() + " " + e.getValue());
        }
  }
}
Avatar billede dennish Nybegynder
09. september 2009 - 12:42 #4
arne>> super. Fandt ud af at fromKey < toKey så jeg kan f.eks. ikke skrive "i","h". Men hvordan får jeg den til at returnere alle forekomster startende med h. Jeg kan nemlig ikke skrive "h","h"
Avatar billede arne_v Ekspert
09. september 2009 - 14:07 #5
h.subMap("h", "i");

returnerer alle som starter med h

den finder nemlig alle key hvor "h" <= key < "i"
Avatar billede dennish Nybegynder
09. september 2009 - 15:02 #6
Arne>> Super Arne. Smider du et svar
Avatar billede dennish Nybegynder
09. september 2009 - 15:05 #7
Ups lige et lille spørgsmål. Hvis jeg nu vil søge på alle forekomster af hi, skal det så ikke være "hi", "hij" ?
Avatar billede dennish Nybegynder
09. september 2009 - 15:07 #8
Hov det skulle være "hi", "hj"
Avatar billede arne_v Ekspert
09. september 2009 - 15:09 #9
Jeps.

Og svar.
Avatar billede arne_v Ekspert
09. september 2009 - 15:10 #10
Strukturen skulle have nogle paene big O egenskaber.
Avatar billede dennish Nybegynder
11. september 2009 - 09:15 #11
TreeMap er implementeret som et Red-Black tree (binært søgetræ). Store O er O(log n).

Jeg er nu mere tilhængere af et B+ træ hvor store O (worst case) er ved:
Insert: O(logbn)
Search: O(logbn)
Delete: O(logbn)

Jeg kan godt lide at et B+ træ aldrig bliver særlige højt. Men fremfor selv at kode et B+ træ vil jeg benyttet mig af TreeMap der jo har en acceptabel store O.
Avatar billede arne_v Ekspert
11. september 2009 - 17:19 #12
Man bruger ikke B+ traer til in memory strukturer kun til on disk strukturer.

Binaere traer er hurtigere end multi traerer naar det er in memory strukturer.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester