On 16.09.2015 19:57, AK wrote:
> Użytkownik "M.M." <m...@g...com> napisał:
>
>> Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.
>> Przy perfect-hash ilość bitów * ( max_value - min_value + 1). Dla
>> małej rozpiętości można łatwo zrobić perfect-hash.
>>
>> Dróg jest wiele, a jaką wybrać, to zależy od konkretnych danych.
>
> Ano wlasnie, a to jest czesto omijana sprawa ana rzecz "generycznosci".
> Zawsze warto przeanalizowac dane (chocby tylko po min i max).
> Koszt maly. Tylko jeden przebieg.
> Zysk (niekiedy) ogromny


No właśnie, niekiedy. A w standardowym przypadku jesteśąmy do tyłu.
Jeden przebieg zajmie zauważalną cześć czasu proponowanych tu
rozwiązań.
To wydaje się zbyt lekki problem na wstępną analizę danych.

Za to jeśli wiemy coś o rozkładzie od początku, można dobrać
algorytm, choćby czy tworzyć zbiór dynamicznie zaczynając od
małej pamięći dla tej tablicy, powiększając, a więc realokując i
rehaszując w mairę potrzeby (jeśli liczba unikalnych wpisów jest
mała) czy budować od razu w tablicy hashującej wielkośći 2n (dla k=~=n).

Sprawdzanie min/max ma jedną neidogodność. Unikalnych wpisów może
być mało, a rozpiętość ich wartośći duża.


pzdr
bartekltg