On Thursday, September 17, 2015 at 12:23:43 AM UTC+2, bartekltg wrote:
> On 16.09.2015 23:27, AK wrote:
> > Użytkownik "bartekltg" 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ć.

Jak już przeciągamy, to ja ciekawy jestem, dla jakich danych najszybszy
będzie będzie algorytm O(N^2). Jakie N, jaki procent duplikatów i jaki
rozstęp, aby był najszybszy. Coś w ten deseń (z góry sory za błędy):

bool exists( int t[] , int N, int v ) {
for( i=0 ; i<N ; i++ )
if( t[i] == v )
return true;
return false;
}

int uniq( int t[] , int N ) {
for( i=j=0 ; i<N ; i++ ) {
if( ! exist( t , j , t[i] ) )
t[j++] = t[i];
}
return j;
}

Dla N=100 mamy około 2500 operacji. Przy N*LogN mamy
tylko 600, ale implementacja algorytmu kwadratowego
jest zabójczo wydajna.

Pozdrawiam

>
>
> > 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