BST optymalizacja

0

Mam problem z przyspieszeniem wyszukiwania i dodawania elementow do drzewa, juz nie mam pomyslu jak to usprawnic. Prosze o pomoc.
funkcja dodajaca elementy

void dodaj(NODE *n, char *pol, char *eng) {
        NODE *new, *p = n; int t;

        while(n != NULL) {
                p = n; t = strcmp(pol, n->slowo_pl);
                if(t == -1)
                        n = n->left;
                else if(t == 1)
                        n = n->right;
        }

        if(n != NULL)
                t = strcmp(p->slowo_pl, pol);

        new = (NODE*)malloc(sizeof(NODE));
        strcpy(new->slowo_pl, pol);
        strcpy(new->slowo_en, eng);
        new->left = NULL;
        new->right = NULL;

        if(p == NULL) {
                new->parent = NULL;
                root = new;
        } else if(t == -1){
                new->parent = p;
                p->left = new;
        } else {
                new->parent = p;
                p->right = new;
        }
}

funkcja wyszukujaca elementy

void szukaj(NODE *n, char *pol, int licznik) {
        while(n != NULL && strcmp(n->slowo_pl, pol)){
                if(strcmp(n->slowo_pl, pol) == 1)
                        n = n->left;
                else
                        n = n->right;
        }

        if(n == NULL) {
                printf("nie ma :D :D\n");
                return;
        } else
                printf("%s\n", n->slowo_en);
}

drzewo

typedef struct node {
        char slowo_pl[12];
        char slowo_en[12];
        struct node *left, *right, *parent;
} NODE;

NODE *root = NULL;

Bede wdzieczny za nakierowania na jakas metode usprawniajaca te dwie powyzsze funkcje.

0

Zastanawiam się, czy kompilujesz z optymalizacją. Odnośnie wyszukiwania i dodawania to widzę, że dużo razy porównujesz napisy, mógłbyś postarać się zrobić hashowanie, tylko musiało by być dość dobrze przemyślane. Jeżeli masz dużo elementów to mógłbyś się zastanowić nad jakimś zrównoważonym drzewem. Myślę, że gdybyś użył hashowania to drzewo było by bardziej zrównoważone.

0

Dziekuje za odpowiedz. Nie kompiluje z optymalizacja zadna, poniewaz musze to na razie usprawnic.
Wlasnie problemem jest oprocz zrownowazenia, ze duzo razy porownuje te elementy.
Sprobuje hashowanie dodac, ale pozostaje problem tego nieszczesnego porownywania, z ktorym niewiem jak sobie poradzic.
Moze ktos ma jakis pomysl jak w tym przypadku zmniejszyc liczbe porownan ?

0

Ogólnie nie przyspieszysz porównywania, jedynie tak jak Ci mówię, że dla napisu liczysz sobie hasha, który jest typu int i wtedy znacznie szybciej porównujesz. Jeżeli prace robisz tylko i wyłącznie dla siebie to zamiast samemu pisać BST możesz użyć np. map z STL.

0

Dobra dzieki, a co do tego STL to nie korzystam z niego w ogóle, jak rowniez w c++ nie pisze. Troche utrudnienie, ze sam musze wszystkie struktury implementowac, ale na pewno na dobre mi to wyjdzie ;p
Jak ogarne te funkcje jutro to wrzuce tu kod moze komus sie przyda.

0

Jeszcze raz dzieki za rade z tymi hashami, zrobilem tablice wskaznikow i funkcje liczaca indeksy do niej na podstawie slow. Kazdy wskaznik tej tablicy wskazuje na odpowiedni wezel drzewa. Czas zmalal dzieki temu z okolo 1s dla mniej wiecej 200 slow na setne sekundy :)
funkcja dodajaca do drzewa

void insert(NODE *ptr, char *pol, char *eng, int key)
{
        NODE *new, *p; int ret, count = 1;

        new = (NODE*)malloc(sizeof(NODE));              // rezerwacja pamieci na nowy wezel
        strcpy(new->word_pl, pol);                      // wypelnienie struktury wezla
        strcpy(new->word_en, eng);
        new->left = NULL;
        new->right = NULL;

        if(ptr == NULL)                                 // jesli nie ma zadnego wezla to dodaje korzen
        {
                new->count = count;
                new->parent = NULL;                     // tylko korzen nie ma rodzica
                hashtable[key] = new;                           // przypisanie adresu wezla do tej tablicy
                root = new;

                return;
        } else  {                                       // jesli sa wezly to szukam miejsca dla nowego
                while(ptr != NULL)
                {
                        p = ptr; ret = strcmp(ptr->word_pl, pol);

                        if(ret == -1)
                                ptr = ptr->left;
                        else
                                ptr = ptr->right;

                        count++;
                }

                ret = strcmp(p->word_pl, pol);

                new->count = count;
                new->parent = p;

                if(hashtable[key] == NULL)              // malutkie zabezpieczenie na wypadek kolizji
                        hashtable[key] = new;
                else {
                        while(hashtable[key++] != NULL);
                        hashtable[key] = new;
                }

                if(ret == -1)
                        p->left = new;
                else
                        p->right = new;
        }
}

funkcja powiedzmy, ze hashujaca - wyliczam indeks na podstawie kodow ASCII oraz elastycznie dopasowuje do wielkosci tablicy, jak tablica ma byc wieksza wystarczy wtedy zmienic wartosc SIZE i wszedzie beda zmiany

int hash(char *str)                                     // funkcja skrotu liczaca indeks tablicy wskaznikow na wezly
{
        int i = 0, key = 0;

        while(str[i]) {
                key += str[i];
                i++;
        }

        return key % SIZE;
}

Funkcji wyszukujacej nie wrzucam, poniewaz jej zadaniem jest tylko sprawdzic na podstawie podanego klucza, czy owy wskaznik tablicy pod tym indeksem wskazuje na NULL, czy na cos konkretnego.

0

Powiedz mi dlaczego jeszcze zrobiłeś tak:

                        if(ret == -1)
                                ptr = ptr->left;
                        else
                                ptr = ptr->right;

Przy przechodzeniu po drzewie. Wydaje mi się, że lepiej by było gdybyś dał ret < 0. Odnośnie hashowania to można jeszcze zrobić tak, że w węźle trzymasz jego hasha i przy przechodzeniu nie porównujesz napisów tylko hashe, wtedy musiałbyś zrobić lepsze hashowanie. Przyspieszyło by to znacznie, gdyż porównanie hashy jest w czasie stałym a napisów liniowym.

0

Dodalem, zeby okreslic w ktora strone dodawac, czy do lewego, czy prawego, poniewaz ptr w tym momencie wskazuje na NULL, a p na wezel do ktorego bede dodawal.

0

A tak swoją drogą to warto się nauczyć c++ i STLa. Implementacja słownika jest wtedy natychmiastowa.

#include <iostream>
#include <string>
#include <map>

using namespace std;

map<string,string> slownik;

void dodaj(string pl, string en)
{
    slownik[en]=pl;
}
string szukaj(string en)
{
    if(slownik.find(en)!=slownik.end())
            return slownik[en];
    else
            return string("brak");
}
int main()
{
    ios_base::sync_with_stdio(0);
    string pl,en;
    int c;
    cout << "1. dodaj slowo" << endl;
    cout << "2. wyszukaj slowo" << endl;
    cout << "3. zakoncz" << endl;
    while(true)
    {
        cin >> c;
        if(c==1)
        {
            cin >> pl >> en;
            dodaj(pl,en);
        }
        if(c==2)
        {
            cin >> en;
            cout << szukaj(en) << endl;
        }
        if(c==3)
            break;
    }
    return 0;
}

Chodziło mi o ten fragment:

                while(ptr != NULL)
                {
                        p = ptr; ret = strcmp(ptr->word_pl, pol);

                        if(ret == -1)
                                ptr = ptr->left;
                        else
                                ptr = ptr->right;

                        count++;
                }
0

Samo c++ mi nie przeszkadza, ostatnio zaczalem przypominac sobie wszystkie te klasy itd, jesli chodzi o c++, wiec i klase szablonowa do obslugi slownika moge sobie napisac, ale bardziej mi c podchodzi, niz te jezyki obiektowe, a mimo to wole pythona niz c++ i tak :D Taki paradoks.
Co do STL to niewiem dlaczego ale z trudem mi przychodzi korzystanie z dodatkowych bibliotek, jesli moge sobie to sam napisac, podobnie jest z boost, curl i wieloma innymi ktorych nie uzywam, a w sumie przyspieszyloby to proces pisania kodu.
Natomiast, jesli nie ma wyjscia i trzeba skorzystac z gotowej biblioteki to jej uzywam, ale to dotyczy bibliotek typu sdl, libc, kernel32 :D Tak to wole sam wszystko pisac.

0

Nie rozumiem tego pytania, przeciez bez tego kawalka drzewo nie bylo by drzewem.
Ten fragment jest po to zeby okreslic, w ktora strone isc drzewa, a to -1 mowi, ze pierwszy parametr strcmp jest alfabetycznie pierwszy.

0

Wydaje mi się, że strcmp zwraca wartość większą od zera, gdy pierwszy string jest większy, a mniejszą od zera gdy pierwszy string jest mniejszy(niekoniecznie -1, wartość bezwzględna to indeks znaku na którym się różnią), ale pewny nie jestem.

1 użytkowników online, w tym zalogowanych: 0, gości: 1