The attached file contains tests for the lib.alg.sort,
lib.alg.stable_sort, lib.alg.partitial_sort and
lib.alg.partitial_sort_copy algorithms.
Here I check the algotithms correctness using the hardcoded sequences
and verify the complexity using the randomgenerated sequences.
The upper estimated value for algorithms was left without changes, but
may be we should open a jira issue about the complexity checks.
Martin Sebor wrote:
[...]
>Be sure to verify this in the test itself (i.e., the test should issue
>an error when it can't force the algorithm to use dynamically allocated
>memory.
[...]
I am not sure that I understand your completely, but I added the test
with forced dynamically memory allocation for stable_sort.
With best wishes,
Anton Pevtsov
Original Message
From: Martin Sebor [mailto:sebor@roguewave.com]
Sent: Wednesday, February 01, 2006 05:04
To: stdcxxdev@incubator.apache.org
Subject: Re: test for lib.alg.sort
Anton Pevtsov wrote:
>> I am porting tests for lib.alg.sort algorithms (sort, stable_sort,
>> partial_sort and partial_copy_sort) and I have several questions about
>> these tests:
>>
>> 1. Current test version contains code for some tracing:
>> ...
>> if (!(i % 20))
>> TRACE
>> ("++++++++\n"
>> " N  COMP  COPY N lg N X  max X
min
>> X\n"
>>
>> "+======+======+======+======+======+======+======+\n");
>>
>> // #  comp  assign  exp. complexity  X  max X 
>> TRACE ("%6d%6d%6d%6d%6.2f%6.2f%6.2f\n",
>> i + 1, ops, cpy, cmplx, x, x_max, x_min); ...
>>
>> Do we need to keep this trace in new version ?
Feel free to disable it but please leave the code in so that it can be
enabled if need be.
>>
>> 2. Current test version doesn't exercise stable_sort, partial_sort and
>> partial_copy_sort at all. I'll add tests for these algorithms.
That'll be great!
>> As a part
>> of them I'll need to verify their complexity. For the sort algorithm I
>> found the upper estimate value in the code (3.33 * N * log N). Is this
>> the correct upper estimate value for stable_sort, partial_sort and
>> partial_sort_copy too?
Not really, it's just something that happened to work for the test as
well as our implementation. I never did like it. I don't think we can
use a general formula to test the complexity.
>> The standard talks about O(N * log M), M <= N
>> for these algorithms, but this is not enough for strict tests.
I see O(N * log N) for sort() but I don't see how we can reliably test
the complexity requirements. The original sort implementation used the
quicksort algorithm which has quadratic worst case behavior. The only
semireliable way to verify the implementation performs in log time on
average is to do a whole bunch of runs on random data and check we're in
the ballpark.
We've been using the introsort algorithm which has a guaranteed
logarithmic complexity but even with this algorithm the only way to test
the complexity is over a large number of runs.
>> (Of
>> course, I suppose here that stable_sort uses additional memory).
>>
>> 3. I think it is necessary to verify the complexity of stable_sort in
>> case then no additional memory is available. Is it possible to disable
>> the memory allocation in this algorithm? (I think that the using of
>> huge arrays is not a right way to do it).
AFAIK, the algorithm uses the std::get_temporary_buffer() function
template. While it's not guaranteed, in our implementation, each
specialization of the template manages just one buffer (or maybe all of
them share the same buffer, either way). So if you grab the buffer by
calling std::get_temporary_buffer() before invoking the algorithm you
should prevent it from using it too and force get_temporary_buffer to
dynamically allocate the memory requested by the algorithm. Be sure to
verify this in the test itself (i.e., the test should issue an error
when it can't force the algorithm to use dynamically allocated memory.
You might want to look at rw_new.h and new.cpp to see if you could
exploit the replacement operator new for this purpose. Be aware that the
replacement operator new doesn't work across shared library boundaries
on AIX and Windows.
>>
>> 4. I assume to use randomgenerated sequences for these algorithms
>> tests. Of course, it is possible to use hardcoded sequences like it is
>> done in almost all other tests, but this will result in difficulties
>> with the complexity tests (to test the complexity correctly we are
>> needed in large sequences). May be, it would be good to verify the
>> algorithms correctness on the hardcoded sequences and use
>> randomgenerated arrays to verify the complexity. What do you think
>> about it?
That sounds like a very reasonable approach.
Martin
