incubator-stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Anton Pevtsov" <Ant...@moscow.vdiweb.com>
Subject Re: Re: test for lib.alg.nth.element
Date Tue, 07 Feb 2006 16:37:49 GMT
Martin Sebor wrote:
> Sounds good. Could you please go ahead and file the issue?

New jira issue is created:
http://issues.apache.org/jira/browse/STDCXX-138


With best wishes,
Anton Pevtsov.


-----Original Message-----
From: Martin Sebor [mailto:sebor@roguewave.com] 
Sent: Sunday, February 05, 2006 04:09
To: stdcxx-dev@incubator.apache.org
Subject: Re: test for lib.alg.nth.element


Anton Pevtsov wrote:
> Martin Sebor wrote:
>  > That's definitely not strict enough for a linear algorithm  > 
> (i.e., O(K * N) with K << N) [...]
> 
> I exercised the nth_element algorithm with large random-generated 
> sequnces and found that K is not great than 8. The attached patch sets

> the upper bound to 8 * N to avoid function of N there.

Okay, that's better. Applied thus:
http://svn.apache.org/viewcvs.cgi?rev=374954&view=rev

> The better way is to avoid such "magic"
> numbers at all, but for this purpose it is necessary to found the 
> worst sequence for an algorithm. So I suggest to open the jira issue 
> as a reminder that we need to investigate each algorithm to find the 
> worst case for it and use the complexity on this worst sequence as the

> upper bound in tests.

Sounds good. Could you please go ahead and file the issue?

Thanks
Martin

Mime
View raw message