On 18.09.2015 18:07, M.M. wrote:
> On Friday, September 18, 2015 at 12:18:57 AM UTC+2, bartekltg wrote:

>>> 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?
> Właśnie nie pamiętam ile to było.

std::sort w gcc przełącza przerywa rekunrencję qsorta
na rzecz sortowania przez wstawianie dla podtablic
mniejszych niż 16 elementów.

> Oryginalny pytacz będzie
> testował, to pewnie nam powie jakie miał benchmarki :) Ja
> strzelam że pomiędzy 500-1000.

Na pewno nie aż tyle.

pzdr
bartekltg