On 16.09.2015 23:27, AK wrote:
> Użytkownik "bartekltg" <b...@g...com> napisał:
>
>> 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.
>
> Zalezy. Zalkezy co sie rozumie pod terminem "przypadek standardowy".
> IMHO standardowy przypadek do dane "merytoryczne"/dziedzinowe.

Przecież o tym piszę. Coś można wyciagnać i wykalibrować
algorytm, jeśli wiadoom, jakich danych statystycznie się spodziewać.


> Jesli to sa dane "merytoryczne" to max -min << MAX_UINT


Bardzo dziwne załozenie. Pewnie prawdziwe, w _neiktórych_
dziedzinach.

> a wtedy mozna "zjechac" zznacznie z pamiecia gdyz zamiast hasha pelnego
> uinta mozna uzyc bitseta na rzeczywiscie uzywawanej maxymalnej ilosci bitow
> /czyli bits(max - min)/.

Główny spadek zapotrzebowania pamięciowego bierze się stąd,
że tablica będzie nie większa niż O(max-min).
Jak max-min zejdzie do zakresu bajta-dwóch, to w ogole
nie bawiłbym się w hashowanie, tylko zliczał. A to było
opisane jako pierwsza metoda w tym wątku.
Jest to jednak bardzo sztuczny przypadek (tak, tak, są
"dziedziny" gdzie to przypadek standardowy).



pzdr
bartekltg