[JAVA] Słownik na tablicy rozproszonej


(Rdrfear) #1

Mam małe pytanie w związku z wyznaczaniem hashCode dla konkretnych słów dodawanych do słownika.

Jeśli mamy małe, duże litery oraz spacje w słowach (ciąg znaków) to jak zrobić by litery od a do z były interpretowane jako liczby od 1 do 26, od A do Z 27 do 52, a spacja 53?

Próbowałem znaleźć odpowiednia komendę, ale nie widzę takowej.

Ponadto mam problem z samą funkcją mieszającą. Ma ona:

  1. Zamiana słowo key na liczbę naturalną - num,

np.

niech key = ‘cats’,

litery występujące mają następujące kody: c=3, a=1, t=20, s=19

Dla słowa ‘cats’ wyznacz liczbę num = 3*27^3+1*27^2+20*27^1+19*27^0

(mnożymy kody poszczególnych znaków przez odpowiednią potęgę 27,

a następnie dodajemy wyniki mnożenia)

  1. Oblicz

h(key) = num % m ;

przy czym: m = liczba pierwsza odległa od potęgi dwójki, oraz

m w przybliżeniu 2 * n ,

gdzie: n – jest przewidywaną liczbą przechowanych elementów.

Tak wygląda:

public int hash(String key)

        {

            int wartosc = 0;

            int len = key.length() - 1;


            for(int j = 0; j < key.length(); j++ ) 

            {

                wartosc += toDig(key.charAt(j)) * Math.pow(53, len);

                len--;

            }


            // 2.


            return wartosc;

        }

(kostek135) #2

Prawdopodobnie niema, algorytm to:

Rozbij na tablice char

dla małych

od każdego znaku w tablicy odejmij -('a' -1)

dla dużej

od każdego znaku w tablicy odejmij -('A' - 27)

dla spacji daje else if-a.

Czego nie rozumiesz w punkcie 2?


(Rdrfear) #3

NIe rozumiem jak mam określić m. Rozumiem, że n jest równe ilości przechowywanych elementów, ale nawet wtedy kiedy duplikaty zostają odrzucone? Tzn. mogę ustalić na początku ilość elementów włącznie z duplikatami, ale duplikatów nie zapisuję. Czy wtedy n = wszystkie słowa włącznie z duplikatami?

Tak wygląda funkcja zamieniająca litery na liczby:

private int toDig(char a)

        {

            int ile = 0;

            if(Character.isLowerCase(a))

            {

                ile = a - ('a' - 1);

            } else if(Character.isUpperCase(a)) {

                ile = a - ('A' - 27);

            } else if(a == ' '){

                ile = 53;

            }

            return ile;

        }

Dla 'a' nie sypnie się? Zdaje się, że powinno być -('a' +1) i -('A' + 27).


(kostek135) #4

Nie jestem pewny co ty rozumiesz przez duplikat, jeśli ABC, ABC, to takich duplikatów nie liczysz, jeśli natomiast znajdziesz dwa różne słowa będące tym samym to je rehashujesz przykład słowo aa = 1*27^1 + 1*27^0 = 28, słowo B 28*27^0 = 28, przy dodaniu B musisz użyć funkcji rehashującej, żeby trafiło w inne miejsce. n = wszystkie elementy wyłączając duplikaty pierwszego typu, to jest nie dodajemy do słownika 2 razy tego samego słowa, ale dodajemy dwa różne słowa mające ten sam hash.

'a' - ('a' + 1) = 'a' -'a' - 1 = 0 - 1 = -1 twój się sypnął, mój nie.

'a' - ('a' - 1) = 'a' - 'a' + 1 = 0 + 1 = 1;


(Rdrfear) #5

Witam. Program udało mi się napisać i po wielu testach stwierdzam, że działa. Tworzy on narzuconą przez użytkownika ilość drzew BST i tam przechowuje kolejne słowa. Posiada operacje: Insert, Search, Delete. Mam z nim natomiast inny problem i zarazem pytanie do was: jak usprawnić kod, by działał szybciej? Co można pozamieniać, co usunąć, itd.? Zrezygnowałem z własnej funkcji hashującej na rzecz wbudowanej funkcji hashCode. Program przyjmuje: ilość zestawów, ilość drzew, słowa w ilości narzuconej przez użytkownika (przyjmowanie słów kończy się po wpisaniu znaku "#"), ilość operacji, operacje w formie: INSERT x, SEARCH x, DELETE x.

import java.util.Scanner;


public class Source 

{

    public static Scanner scan = new Scanner(System.in);    


    public static void main(String[] args) 

    {

        int l = scan.nextInt();


        for(int i = 0; i < l; i++)

        {

            int n = scan.nextInt();

            BST[] slownik = new BST[n];


            for(int o = 0; o < n; o++)

            {

                slownik[o] = new BST();

            }


            String s = scan.next();


            int m = 0;

            while(!"#".equals(s))

            {

                slownik[hash(s, n)].insert(s);

                m++;

                s = scan.next();

            }


            System.out.println("n= " + m);


            int k = scan.nextInt();

            String polecenie;


            for(int j = 0; j < k; j++)

            {

                polecenie = scan.next();


                if(polecenie.charAt(0) == 'S')

                {

                    String info = scan.next();

                    System.out.println(info + ": " + slownik[hash(info, n)].find(info));

                } else if(polecenie.charAt(0) == 'I') {

                    String info = scan.next();

                    System.out.println(info + ": " + slownik[hash(info, n)].insert(info));

                } else {

                    String info = scan.next();


                    if(slownik[hash(info, n)].find(info) == 0)

                    {

                        System.out.println(info + ": " + 0);

                    } else {

                        System.out.println(info + ": " + slownik[hash(info, n)].remove(info));

                    }

                }

            }

        }

    }


    public static class Slowo

    {

        public String info;

        public Slowo lewy;

        public Slowo prawy;

        public int ilosc;


        Slowo(String value) 

        {

            info = value;

            lewy = prawy = null;

            ilosc = 1;

        }

    }


    public static class BST

    {

        protected Slowo korzen;


        public BST() 

        {

            korzen = null;

        }


        public int insert(String x)

        {

            Slowo s, p = null, prev;

            s = new Slowo(x);

            boolean t = false;


            if(korzen == null)

            {

                korzen = s;

            } else {

                p = korzen; prev = null;

                while(p != null)

                {

                    prev = p;


                    if(s.info.equals(p.info))

                    {

                        p.ilosc++;

                        t = true;

                        break;

                    } else if(s.info.compareTo(p.info) < 0) {

                        p = p.lewy;

                    } else {

                        p = p.prawy;

                    }

                }


                if(t == false && s.info.compareTo(prev.info) < 0)

                {

                    prev.lewy = s;

                } else if(t == false) {

                    prev.prawy = s;

                }

            }


            if(t)

            {

                return p.ilosc;

            } else {

                return s.ilosc;

            }

        }


        public int remove(String x) 

        {

            Slowo p = korzen;

            Slowo ds = null;

            int lp = 0;


            if(x.equals(korzen.info))

            {

                ds = korzen;

            } else {

                while(p != null) // znajdowanie ojca

                {

                    if(p.lewy != null && x.compareTo(p.lewy.info) < 0)

                    {

                        p = p.lewy;

                    } else if(p.prawy != null && p.prawy.info.equals(x)) {

                        ds = p.prawy;

                        lp = 1;

                        break;

                    } else if(p.lewy != null && p.lewy.info.equals(x)) {

                        ds = p.lewy;

                        lp = 2;

                        break;

                    } else if(p.prawy != null) {

                        p = p.prawy;

                    }

                }

            }


            boolean g = false;


            if(ds.ilosc > 1) // usuwanie

            {

                ds.ilosc--;

            } else {

                g = true;


                if(lp == 2) // lewy potomek

                {   

                    while(true)

                    {

                        if(ds.lewy == null && ds.prawy == null)

                        {

                            p.lewy = null;

                            break;

                        } else if(ds.lewy != null && ds.prawy == null) {

                            p.lewy = ds.lewy;

                            break;

                        } else if(ds.prawy != null && ds.lewy == null) {

                            p.lewy = ds.prawy;

                            break;

                        } else {

                            Slowo temp = ds.prawy;


                            while(temp.lewy != null && temp.lewy.lewy != null)

                            {

                                temp = temp.lewy;

                            }


                            ds.info = temp.lewy.info;

                            p = temp;

                            ds = temp.lewy;

                        }

                    }

                } else if(lp == 1){

                    while(true) // prawy potomek

                    {

                        if(ds.lewy == null && ds.prawy == null)

                        {

                            p.prawy = null;

                            break;

                        } else if(ds.lewy != null && ds.prawy == null) {

                            p.prawy = ds.lewy;

                            break;

                        } else if(ds.prawy != null && ds.lewy == null) {

                            p.prawy = ds.prawy;

                            break;

                        } else {

                            Slowo temp = ds.prawy;


                            while(temp.lewy != null && temp.lewy.lewy != null)

                            {

                                temp = temp.lewy;

                            }


                            ds.info = temp.lewy.info;

                            p = temp;

                            ds = temp.lewy;

                        }

                    }

                } else { // korzen

                    while(true)

                    {

                        if(korzen.lewy == null && korzen.prawy == null)

                        {

                            korzen = null;

                            break;

                        } else if(korzen.lewy != null && korzen.prawy == null) {

                            korzen = korzen.lewy;

                            break;

                        } else if(korzen.prawy != null && korzen.lewy == null) {

                            korzen = korzen.prawy;

                            break;

                        } else {

                            Slowo temp = korzen.prawy;


                            if(temp.lewy == null)

                            {

                                korzen.info = temp.info;

                                korzen.ilosc = temp.ilosc;

                                korzen.prawy = null;

                                break;

                            } else {

                                while(temp.lewy != null && temp.lewy.lewy != null)

                                {

                                    temp = temp.lewy;

                                }


                                korzen.info = temp.lewy.info;

                                korzen.ilosc = temp.lewy.ilosc;

                                temp.lewy = null;

                                break;

                            }

                        }

                    }

                }

            }


            if(g)

            {

                return 0 ;

            } else {

                return ds.ilosc;

            }

        }


        public int find(String x) 

        {

            Slowo p = korzen;

            boolean i = false;


            while(p != null)

            {

                if(p.lewy != null && x.compareTo(p.info) < 0)

                {

                    p = p.lewy;

                } else if(x.equals(p.info)) {

                    i = true;

                    break;

                } else if(p.prawy != null) {

                    p = p.prawy;

                } else {

                    break;

                }

            }


            if(i)

            {

                return p.ilosc;

            } else {

                return 0;

            }

        }

    }


    public static int hash(String key, int l)

    {

        return Math.abs(key.hashCode() % l);

    }

}

Proszę o podpowiedzi.