eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingw poszukiwaniu funkcji hash
Ilość wypowiedzi w tym wątku: 5

  • 1. Data: 2013-03-08 04:10:04
    Temat: w poszukiwaniu funkcji hash
    Od: "M.M." <m...@g...com>


    Zastanawiam się, czy istnieje wydajny algorytm, albo może
    wręcz jakaś metoda analityczna, do budowy różnowartościowych
    funkcji hash.

    Mamy zbiór X, elementami zbioru X jest N liczb
    całkowitych x_i. Zwykle N jest większe od 10 i mniejsze
    od 10tys. Liczby całkowite x_i zwykle należą do przedziału
    od -10^6 do +10^6. Trzeba znaleźć różnowartościową
    funkcję h, która odwzoruje wszystkie elementy X w ciąg
    liczb naturalnych od 1 do M. Idealnie jakby M było
    równe N, ale jeśli M < N*3 to też nie będzie źle.

    Chodzi o to, aby funkcja h była możliwie prosta i
    żeby dało się ją wydajnie zaimplementować. Przykładem
    funkcji h może być:
    h( x_i ) = ( (x_i + a_1 ) * (x_i + a_2) * ... * (x_i + a_n) ) % M;
    gdzie n jest możliwe małe, najlepiej gdy 2<=n<=3.

    Moje pytanie sprowadza się do tego, czy istnieje efektywny
    algorytm, który na wejście otrzyma parę: zbiór X i M, a
    na wyjściu poda a_1, a_2, a_n.

    Oczywiście funkcja h nie musi być taka jak podałem w
    przykładzie, może lepiej sprawdzi się operacja xor:
    h( x_i ) = ( (x_i xor a_1 ) * (x_i xor a_2) * ... * (x_i xor a_n) ) % M;

    Trzeba przeiterować po wszystkich a_i żeby dowiedzieć się
    czy dla danego X i M istnieje różnowartościowa funkcja H,
    czy można to jakoś sprawniej osiągnąć?

    Pozdrawiam


  • 2. Data: 2013-03-08 23:38:08
    Temat: Re: w poszukiwaniu funkcji hash
    Od: Wojciech Muła <w...@g...com>

    W dniu piątek, 8 marca 2013 04:10:04 UTC+1 użytkownik M.M. napisał:
    > Zastanawiam się, czy istnieje wydajny algorytm, albo może
    > wręcz jakaś metoda analityczna, do budowy różnowartościowych
    > funkcji hash.

    Takie funkcje mieszające nazywają się "doskonałymi" (perfect) --
    piszę to jedynie dla ułatwienia dalszego googlania.

    Tu masz uniwersalny algorytm:
    http://stevehanov.ca/blog/index.php?id=119

    w.


  • 3. Data: 2013-03-09 00:25:44
    Temat: Re: w poszukiwaniu funkcji hash
    Od: "M.M." <m...@g...com>

    W dniu piątek, 8 marca 2013 23:38:08 UTC+1 użytkownik Wojciech Muła napisał:
    > W dniu piątek, 8 marca 2013 04:10:04 UTC+1 użytkownik M.M. napisał:
    >
    > > Zastanawiam się, czy istnieje wydajny algorytm, albo może
    > > wręcz jakaś metoda analityczna, do budowy różnowartościowych
    > > funkcji hash.
    > Takie funkcje mieszające nazywają się "doskonałymi" (perfect) --
    > piszę to jedynie dla ułatwienia dalszego googlania.
    > Tu masz uniwersalny algorytm:
    > http://stevehanov.ca/blog/index.php?id=119
    Tamten, o ile dobrze zrozumiałem, wymaga dużo pamięci na jakąś tabelę
    pośrednią.

    Algorytm CHD
    http://cmph.sourceforge.net/
    wymaga tylko 2.07 bita na klucz, ale jak na razie nie rozumiem jak
    on działa.

    Pozdrawiam



  • 4. Data: 2013-03-10 15:33:23
    Temat: Re: w poszukiwaniu funkcji hash
    Od: Wojciech Muła <w...@g...com>

    W dniu sobota, 9 marca 2013 00:25:44 UTC+1 użytkownik M.M. napisał:
    > > Tu masz uniwersalny algorytm:
    > > http://stevehanov.ca/blog/index.php?id=119
    >
    > Tamten, o ile dobrze zrozumiałem, wymaga dużo pamięci na jakąś tabelę
    > pośrednią.
    >
    > Algorytm CHD
    > http://cmph.sourceforge.net/
    > wymaga tylko 2.07 bita na klucz, ale jak na razie nie rozumiem jak
    > on działa.

    Hanov opisuje właśnie CHD; autorzy CHD kompresują tablice pośrednie, stąd
    niska średnia bitowa. Metoda kompresji jest opisana w "Simple Random Access
    Compression" K.Fredriksson, F.Nikitin.

    w.


  • 5. Data: 2013-03-10 23:42:01
    Temat: Re: w poszukiwaniu funkcji hash
    Od: "M.M." <m...@g...com>

    W dniu niedziela, 10 marca 2013 15:33:23 UTC+1 użytkownik Wojciech Muła napisał:
    > Hanov opisuje właśnie CHD; autorzy CHD kompresują tablice pośrednie, stąd
    > niska średnia bitowa. Metoda kompresji jest opisana w "Simple Random Access
    Compression" K.Fredriksson, F.Nikitin.
    Ok, dzięki.

strony : [ 1 ]


Szukaj w grupach

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: