On 17.09.2015 14:37, M.M. wrote:
> 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.

Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
elementów.
Z tablicą hashującą jeszcze mniejsza. Kilka?

pzdr
bartyekltg