eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingzadanie z netuRe: zadanie z netu
  • Data: 2013-03-28 12:13:42
    Temat: Re: zadanie z netu
    Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    W dniu czwartek, 28 marca 2013 11:53:31 UTC+1 użytkownik firr kenobi napisał:

    > nigdy nie uzywalem hashowania ani nawet
    > o tym nie czytalem ;o (nigdy nie bylo
    > mi potrzebne)



    > prosta kwestia: o ile wstawiac te wyrazy do drzewa
    > to jego 'posortowanie'/upozadkowanie jest
    > potrzebne bo przeciez chodzi o to by szybko znalezc czy nie ma w
    > nim juz tego elementu ,i
    > jak jest to zrobic ++ na tym wyrazie
    Trzeba pracowac na parach
    struct {
    char *nazwa;
    int czestosc;
    }

    Algorytm wstawiania do drzewka automatycznie sortuje po nazwie,
    nie trzeba nic sortowac. Na koniec trzeba przejrzec wszystkie
    wyrazy i 10 najczestszych zapamietac w kolejce priorytetowej.

    Mozna tez od razu przechowywac i w kolejcie i w drzewie, wtedy
    na koniec nie bedzie potrzeby przegladania wszystkiego - nie
    wiem co szybsze.


    > moje pytanie jest czy wstawianie do tego
    > drzewa (?) hashy jest szybsze i dlaczego
    Dokladna analiza szybkosci nie jest taka prosta. Do tego
    celu trzeba znac sredni koszt kazdej operacji i prawdopodobienstwo
    ze do danej operacji dojdzie. W drzewku mamy operacje:
    a1) wyszukiwaie
    b1) wstawianie
    c1) rownowazenie


    W hash-table tez mamy:
    a2) wyszukiwanie
    b2) wstawianie
    c2) zwiekszanie rozmiaru hash-table.

    P to funkcja prawdopodobienstwa, K to funkcja kosztu. Trzeba miec
    dane do takich wzorow:

    drzwko = P(a1)*K(a1) + P(b1)*K(b1) + P(c1)*K(c1)
    hash-table = P(a2)*K(a2) + P(b2)*K(b2) + P(c2)*K(c2)

    Dla kazdej implementacji te dane sa inne, dla kazdego rozmiaru
    danych tez sa inne, bo dane inaczej sie cash-uja.



    Pozdrawiam

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: