eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Hasz dla permutacji
Ilość wypowiedzi w tym wątku: 8

  • 1. Data: 2020-08-24 08:37:29
    Temat: Hasz dla permutacji
    Od: Borneq <b...@a...hidden.pl>

    Mam permutację np. 5 7 1 2 8 ..4
    chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji 32
    bitów choć ostatecznie 32 bity to też male prawdopodobieństwo kolizji.
    Ma mieć własności:
    - nie działam na bitach ale na liczbach, np. 1204 999 451 1021...
    nieduże liczby

    - prosty hasz z możliwością generowania przyrostowego:
    jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy hasz,
    najlepiej nie z całej tablicy, tak działa prosty XOR, tylko problem: ma
    być conajmniej 32 bity a nie tyle bitów ile mają liczby


  • 2. Data: 2020-08-24 10:10:39
    Temat: Re: Hasz dla permutacji
    Od: Borneq <b...@a...hidden.pl>

    On 8/24/20 8:37 AM, Borneq wrote:
    > Mam permutację np. 5 7 1 2 8 ..4
    > chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji 32
    > bitów choć ostatecznie 32 bity to też male prawdopodobieństwo kolizji.
    > Ma mieć własności:
    > - nie działam na bitach ale na liczbach, np. 1204 999 451 1021...
    > nieduże liczby
    >
    > - prosty hasz z możliwością generowania przyrostowego:
    > jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy hasz,
    > najlepiej nie z całej tablicy, tak działa prosty XOR, tylko problem: ma
    > być conajmniej 32 bity a nie tyle bitów ile mają liczby

    XOR jest nieczuły na kolejność, więc xor wraz z numerem pozycji:
    0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor...
    wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc
    byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash.


  • 3. Data: 2020-08-24 10:20:34
    Temat: Re: Hasz dla permutacji
    Od: Mateusz Viste <m...@x...invalid>

    2020-08-24 o 10:10 +0200, Borneq napisał:
    > On 8/24/20 8:37 AM, Borneq wrote:
    > > Mam permutację np. 5 7 1 2 8 ..4
    > > chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji
    > > 32 bitów choć ostatecznie 32 bity to też male prawdopodobieństwo
    > > kolizji. Ma mieć własności:
    > > - nie działam na bitach ale na liczbach, np. 1204 999 451 1021...
    > > nieduże liczby
    > >
    > > - prosty hasz z możliwością generowania przyrostowego:
    > > jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy
    > > hasz, najlepiej nie z całej tablicy, tak działa prosty XOR, tylko
    > > problem: ma być conajmniej 32 bity a nie tyle bitów ile mają
    > > liczby
    >
    > XOR jest nieczuły na kolejność, więc xor wraz z numerem pozycji:
    > 0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor...
    > wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc
    > byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash.

    Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD sum.
    Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
    wartości. Szerokość takiego hashu sobie możesz dopasować sam, wystarczy
    użyć innego clampingu.

    3 lata temu popełniłem tego implementację:
    https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/
    bsum.asm

    Mateusz


  • 4. Data: 2020-08-24 10:46:48
    Temat: Re: Hasz dla permutacji
    Od: Borneq <b...@a...hidden.pl>

    On 8/24/20 10:10 AM, Borneq wrote:
    > On 8/24/20 8:37 AM, Borneq wrote:
    > XOR jest nieczuły na kolejność, więc xor wraz z numerem pozycji:
    > 0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor...
    > wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc
    > byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash.

    Fletcher sum?


  • 5. Data: 2020-08-24 13:31:34
    Temat: Re: Hasz dla permutacji
    Od: Borneq <b...@a...hidden.pl>

    On 8/24/20 10:20 AM, Mateusz Viste wrote:
    > Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD sum.
    > Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
    > wartości. Szerokość takiego hashu sobie możesz dopasować sam, wystarczy
    > użyć innego clampingu.
    >
    > 3 lata temu popełniłem tego implementację:
    > https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/
    bsum.asm

    Zastanwiam się, bo taki hasz ma okreśłoną "pojemność" po 32 takich
    przeunięciach wcześniejsze wartości nie będą miały żadnego wpływu na sumę.
    Sam crc można lokalnie modyfikować:
    https://github.com/drmikehenry/crc_incremental, metoda testIncrFile i
    zmienna fastNewCrc. ALE
    zmiana to pętla w pętli w calcCrcZeros

    mi chodzi o prostą sumę.
    Może tak (pomijając obcinanie do długości słowa):
    checkusm = SUMA (data[i] * (i+1))

    mnożenie na dzisiejszych kompach jest bardzo szybkie
    jest wrażliwy na kolejność
    czy to byłoby dobre?


  • 6. Data: 2020-08-24 13:48:41
    Temat: Re: Hasz dla permutacji
    Od: Mateusz Viste <m...@x...invalid>

    2020-08-24 o 13:31 +0200, Borneq napisał:
    > On 8/24/20 10:20 AM, Mateusz Viste wrote:
    > > Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD
    > > sum. Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
    > > wartości. Szerokość takiego hashu sobie możesz dopasować sam,
    > > wystarczy użyć innego clampingu.
    > >
    > > 3 lata temu popełniłem tego implementację:
    > > https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/
    bsum.asm
    >
    > Zastanwiam się, bo taki hasz ma okreśłoną "pojemność" po 32 takich
    > przeunięciach wcześniejsze wartości nie będą miały żadnego wpływu na
    > sumę.

    Mój błąd, z rozpędu i przyzwyczajenia napisałem "shift", a powinno być
    "rotate". W kodzie który podlinkowałem zobaczysz "ror".

    Mateusz


  • 7. Data: 2020-08-24 13:52:37
    Temat: Re: Hasz dla permutacji
    Od: Borneq <b...@a...hidden.pl>

    On 8/24/20 1:48 PM, Mateusz Viste wrote:
    > 2020-08-24 o 13:31 +0200, Borneq napisał:
    >> On 8/24/20 10:20 AM, Mateusz Viste wrote:
    >>> Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD
    >>> sum. Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję
    >>> wartości. Szerokość takiego hashu sobie możesz dopasować sam,
    >>> wystarczy użyć innego clampingu.
    >>>
    >>> 3 lata temu popełniłem tego implementację:
    >>> https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/
    bsum.asm
    >>
    >> Zastanwiam się, bo taki hasz ma okreśłoną "pojemność" po 32 takich
    >> przeunięciach wcześniejsze wartości nie będą miały żadnego wpływu na
    >> sumę.
    >
    > Mój błąd, z rozpędu i przyzwyczajenia napisałem "shift", a powinno być
    > "rotate". W kodzie który podlinkowałem zobaczysz "ror".
    >
    > Mateusz
    >

    No tak, ale jak potem zamienić jeden bajt na inny?
    Z mnożeniem świetnie wychodzi, kod w c++

    #include <iostream>
    #include <vector>

    using namespace std;

    int sum1 (vector<int8_t> &v) {
    int res = 1;
    for (int i=0; i<v.size();i++){
    res += v[i]*(i+1);
    }
    return res;
    }


    int main() {
    vector<int8_t> v;
    v.clear();
    v.push_back(1);
    v.push_back(3);
    v.push_back(32);
    v.push_back(2);
    int sum = sum1(v);
    std::cout << sum << std::endl;
    v[2]=127;
    int fastsum = sum + 3*(127-32);
    std::cout << fastsum << " " << sum1(v) << std::endl;
    return 0;
    }


  • 8. Data: 2020-08-24 13:57:54
    Temat: Re: Hasz dla permutacji
    Od: Mateusz Viste <m...@x...invalid>

    2020-08-24 o 13:52 +0200, Borneq napisał:
    > No tak, ale jak potem zamienić jeden bajt na inny?

    Nie znam prostej metody.

    > Z mnożeniem świetnie wychodzi, kod w c++

    No to pozostaje ci już tylko zaimplementować obie wersje i sprawdzić w
    warunkach rzeczywistych dla każdego:
    - czas wykonania
    - statystyczny rozkład
    - częstotliwość kolizji

    Mateusz

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: