On Friday, September 18, 2015 at 12:18:57 AM UTC+2, bartekltg wrote:
> 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?
Właśnie nie pamiętam ile to było. Oryginalny pytacz będzie
testował, to pewnie nam powie jakie miał benchmarki :) Ja
strzelam że pomiędzy 500-1000.
Pozdrawiam