Breakthrough

[jacob navia]

Hi

In a recent discussion ("Open letter to Ian Collins") we found out that
the main problem in the C containers library was the time taken by the
Sort function.

The reasons for that is that it was a general sort function calling a
general comparison function that uses memcmp...

The first step to improve performance was to write data type specific
functions using a data type generic file. As a bonus, we get compile
time checking and better syntax.

Still, the generic sort function was taking a lot of time.

I have written then a data type generic quick sort function that
receives as a parameter a macro that is used to compare two elements.
This vastly improves performance.

The times are:

Generic sort function without any specialized heap
(using malloc)
real 0m17.029s
user 0m16.654s
sys 0m0.368s

Generic sort function using a specialized heap
(reduces the malloc overhead)
real 0m11.759s
user 0m11.500s
sys 0m0.252s

"Templated" sort function using a macro parameter
(reduces comparisons to a simple expression)
real 0m6.453s
user 0m6.165s
sys 0m0.281s

The expression used to compare two list elements is:
#define COMPARE_EXPRESSION(A, B) \
((*B)->Data > (*A)->Data ? -1 : (*B)->Data != (*A)->Data)

I thank Pete for that proposal, I wouldn't have come to it
alone :-)

I would like to have the corresponding C++ times but I fear that
if I write it it would be unfair since I am not a C++ wizard...
Here is the C code for the example:

#include <stdlib.h>
#include "containers.h"
#include "intlist.h"
#define N 10000000
int main(void)
{
intList *L1;
size_t i;
int d;
long long sum=0,newSum=0;
Iterator *it;
int *pint;

L1 = iintList.Create(sizeof(int));
iintList.UseHeap(L1,NULL); // Use specialized Heap
// Add N random numbers to the integer list
for (i=0; i<N;i++) {
d = rand();
sum += d;
iintList.Add(L1,d);
}
// Sort it
iintList.Sort(L1);
// Go through the sorted list using an iterator
it = iintList.NewIterator(L1);
i=0;
for (pint = it->GetFirst(it); pint; pint = it->GetNext(it)) {
newSum += *pint;
}
// Verify that both sums are identical
if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);
// Destroy the list
iintList.Finalize(L1);
}

I have uploaded the latest code to:

http://code.google.com/p/ccl/

There you will find (in listgen.c) the "templated" version of quick sort
in C.

[MelissA]

Here are timings on mu computer.

bmaxa@maxa:~/jacob/ccl$ time ./cppvec
Sum = 10738138201479754

real 0m0.899s
user 0m0.832s
sys 0m0.064s
bmaxa@maxa:~/jacob/ccl$ time ./cpplist
Sum = 10738138201479754

real 0m7.493s
user 0m7.344s
sys 0m0.136s
bmaxa@maxa:~/jacob/ccl$ time ./testlist
Sum = 10738138201479754

real 0m4.320s
user 0m4.180s
sys 0m0.140s

Sources:
---- cppvec.cpp

#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

#define N 10000000

int main()
{
std::vector<int> L1;
long long sum=0,newSum=0;
for(int i = 0; i < N; ++i)
{
int d = rand();
sum+=d;
L1.push_back(d);
}

std::sort(L1.begin(),L1.end());

for(auto it : L1)
{
newSum+= it;

}

if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);

}

----cpplist.cpp

#include <list>
#include <cstdio>
#include <cstdlib>

#define N 10000000

int main()
{
std::list<int> L1;
long long sum=0,newSum=0;
for(int i = 0; i < N; ++i)
{
int d = rand();
sum+=d;
L1.push_back(d);
}

L1.sort();

for(auto it : L1)
{
newSum+= it;

}

if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);

}

Compile with -std=c++0x for gcc 4.6 or -std=c++11 for 4.7

As you can see your program is faster than list version
of C++, but is less elegant ;)


Greets!

[Juha Nieminen]

In comp.lang.c++ MelissA <me...@a.com> wrote:
> #define N 10000000
>
> int main()
> {
> std::list<int> L1;
> long long sum=0,newSum=0;
> for(int i = 0; i < N; ++i)
> {
> int d = rand();
> sum+=d;
> L1.push_back(d);

Your test is basically useless as a measurement of sorting speed because
the vast majority of the time will be spent on those push_back() calls.

If you want to test sorting speed and nothing else, you have to discard
the time spent in memory allocation.

[Ike Naar]

On the machine that I tried, most of the time was spent on the
implicit destruction of the list at program termination.

[jacob navia]

Le 04/06/12 17:32, Juha Nieminen a �crit :

> In comp.lang.c++ MelissA<me...@a.com> wrote:
>> #define N 10000000
>>
>> int main()
>> {
>> std::list<int> L1;
>> long long sum=0,newSum=0;
>> for(int i = 0; i< N; ++i)
>> {
>> int d = rand();
>> sum+=d;
>> L1.push_back(d);
>
> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
>

The purpose of this test is to compare the STL to the C Containers
Library (CCL). With this in mind I wanted a big test with both systems
doing roughly the same thing:

1) Allocate a list
2) Fill it with 100 million random numbers adding each number
to a grand total
3) Sort it
4) Go through the whole list again, reading the data and verify that
you get the same number.
5) Destroy the list.

> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

Yes, but what I want to test is the speed to do ALL tasks mentioned above

[jacob navia]

Le 04/06/12 17:44, Ike Naar a écrit :

>
> On the machine that I tried, most of the time was spent on the
> implicit destruction of the list at program termination.

Yes, I see a noticeable delay between the printing of the
result sum and the end of the program.

Apparently cleaning up is quit e expensive since destructors must be
called 100 million times.

In the CCL you can ADD a destructor if you want but they are NOT
required as in C++.

[BartC]

"jacob navia" <ja...@spamsink.net> wrote in message
news:jqi6o4$gqf$1...@speranza.aioe.org...

> I have uploaded the latest code to:
>
> http://code.google.com/p/ccl/
>
> There you will find (in listgen.c) the "templated" version of quick sort
> in C.

How do you build this thing? Typing make gives errors:

c:\lcc\bin\make says something about bitstrings.o.

Copying makefile.lcc to makefile then doing the same:

c:\lcc\bin\make now complains about something in lcc64.

(I never use 'make' so haven't got a clue. A readme file might be helpful
though.)

--
Bartc

[Paul]

If you're going to collect timing information, it should be
collected right around the working part of the test, and
inside the code itself. Rather than recording the runtime of
the entire executable, and all those rand() calls.

generate_random_numbers
...
get_time_before
do_the_sort
get_time_after
...
print ( get_time_after - get_time_before )

Paul

[jacob navia]

Le 04/06/12 18:30, BartC a �crit :

Sorry, I did not test under windows. I tested now, and you should
just type

make -f makefile.lcc

That compiles in 32 bits lcc

make -f makefile.lcc64

That compiles 64 bit lcc
I upddated the zip file. Please download again and tell me how it goes.

Thanks

[BartC]

"jacob navia" <ja...@spamsink.net> wrote in message

news:jqirb6$imi$1...@speranza.aioe.org...

> Le 04/06/12 18:30, BartC a �crit :

>> How do you build this thing? Typing make gives errors:

> Sorry, I did not test under windows.

That explains the funny line endings in the files..

> I tested now, and you should
> just type
>
> make -f makefile.lcc

Thanks. Downloading the latest lcc 32-bits to make sure, this now gets hung
up on errors in wchar.h (first on line 521, then on line 509).

> That compiles in 32 bits lcc
>
> make -f makefile.lcc64

I couldn't see a .lcc64 file (in the distribution downloaded after your
post)

Anyway I've now given up on make files (I always have trouble with them.
Always.) I found I could build your test program by manually compiling and
linking these files:

intlist.c
buffer.c
vector.c
bitstrings.c
bloom.c
containererror.c
deque.c
dictionary.c
dlist.c
fgetline.c
generic.c
hashtable.c
heap.c
iMask.c
list.c
malloc_debug.c
pool.c
pooldebug.c
qsortex.c
queue.c
redblacktree.c
scapegoat.c
searchtree.c
strcollection.c
valarraydouble.c
valarrayint.c
valarrayuint.c
valarraysize_t.c
valarrayfloat.c
valarraylongdouble.c
valarrayuint.c
valarraylonglong.c
valarrayulonglong.c
valarrayshort.c
observer.c
memorymanager.c
sequential.c
wstrcollection.c

--
Bartc

[jacob navia]

Le 04/06/12 20:18, BartC a écrit :

>
>
> "jacob navia" <ja...@spamsink.net> wrote in message
> news:jqirb6$imi$1...@speranza.aioe.org...

>> Le 04/06/12 18:30, BartC a écrit :

>
>>> How do you build this thing? Typing make gives errors:
>
>> Sorry, I did not test under windows.
>
> That explains the funny line endings in the files..
>
>> I tested now, and you should
>> just type
>>
>> make -f makefile.lcc
>
> Thanks. Downloading the latest lcc 32-bits to make sure, this now gets
> hung up on errors in wchar.h (first on line 521, then on line 509).
>

Ahhh you are using the distribution that comes with the compiler?

That's not really up-to-date. Please download the ccl code from

http://code.google.com/p/ccl/

[MelissA]

Here is just sorting time, C version is significantly faster:

bmaxa@maxa:~/jacob/ccl$ ./testlist
sort time 3.140
Sum = 10738138201479754
bmaxa@maxa:~/jacob/ccl$ ./cpplist
sort time 5.350
Sum = 10738138201479754
bmaxa@maxa:~/jacob/ccl$

[MelissA]

But watch out this:
It is faster to populate vector from list, then
to sort vector , then to clear list, then
to populate list from vector then C version! ;)

bmaxa@maxa:~/jacob/ccl$ time ./cpplist
sort time 0.750
Sum = 10738138201479754

real 0m1.813s
user 0m1.660s
sys 0m0.152s
bmaxa@maxa:~/jacob/ccl$ time ./testlist

sort time 3.140
Sum = 10738138201479754

real 0m4.302s
user 0m4.208s
sys 0m0.096s
bmaxa@maxa:~/jacob/ccl$ cat cpplist.cpp
#include <list>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>

#define N 10000000

int main()
{
std::list<int> L1;
long long sum=0,newSum=0;
for(int i = 0; i < N; ++i)
{
int d = rand();
sum+=d;
L1.push_back(d);
}

std::vector<int> tmp(L1.begin(),L1.end());
clock_t t = clock();
std::sort(tmp.begin(),tmp.end());
clock_t et = clock();
L1.clear();
L1.insert(L1.begin(),tmp.begin(),tmp.end());
printf("sort time %.3f\n",float(et - t)/CLOCKS_PER_SEC);

[jacob navia]

Confirmed.

real 0m5.112s
user 0m4.600s
sys 0m0.487s

That's faster than C by a small amount...

[pete]

jacob navia wrote:

> The expression used to compare two list elements is:
> #define COMPARE_EXPRESSION(A, B) \
> ((*B)->Data > (*A)->Data ? -1 : (*B)->Data != (*A)->Data)
>
> I thank Pete for that proposal, I wouldn't have come to it
> alone :-)

You're welcome.
I hope that I can give you an even handier tip.
I've never needed the three way comparison
to implement any sorting algorithm.

It has always been sufficient for me
to merely use a (Greater Than) macro, GT(A, B),
to implement any sorting algorithm.

#define GT(A, B) ((*A)->Data > (*B)->Data)

I have never needed to know whether two keys compare equal,
in order to implement a sorting algorithm.

--
pete

[Ian Collins]

I don't have the original code to had, but looking back at the original
thread, the C++ list sort was 5x faster, so I guess from your numbers it
is now 2-3 times faster.

--
Ian Collins

[MelissA]

This is with my inplace qsort with bidirectional
iterators:


bmaxa@maxa:~/jacob/ccl$ time ./cpplist1
sort time 1.480
Sum = 10738138201479754

real 0m2.105s
user 0m1.936s
sys 0m0.168s
bmaxa@maxa:~/jacob/ccl$ time ./testlist
sort time 3.130
Sum = 10738138201479754

real 0m4.265s
user 0m4.128s
sys 0m0.136s
bmaxa@maxa:~/jacob/ccl$ cat QSort.h
#include <algorithm>

namespace VLib{
using std::swap;

template <typename T,typename F>
void qsort(T begin, T end, unsigned size, F f)
{
if(begin == end)return;

T high = end;
if(!size)
{
T tmp = begin;
while(tmp!=end){ high=tmp++;++size; }
}
else
{
--high;
}

if(size == 1)return;

T low = begin;
++low;

unsigned counthigh = 0,countlow = 0;
do
{
while(high != low && f(*begin,*high)){ --high;++counthigh; }
while(low != high && f(*low,*begin)){ ++low;++countlow; }

if(low != high && !f(*low,*begin) && !f(*begin,*low) && !f(*begin,*high) && !f(*high,*begin))
{
while(high != low && !f(*high,*low) && !f(*low,*high)){ --high;++counthigh; }
}

swap(*low,*high);
}while(low != high);
swap(*low,*begin);
T i = low;

while(++i != end && !f(*i,*low) && !f(*low,*i) )--counthigh;

VLib::qsort(begin,low,countlow,f);
VLib::qsort(i,end,counthigh,f);
}

template <typename T>
inline void qsort(T begin, T end, unsigned size = 0)
{
VLib::qsort(begin,end,size,std::less<typename std::iterator_traits<T>::value_type>());
}

}
bmaxa@maxa:~/jacob/ccl$ cat cpplist1.cpp
#include <list>

#include <cstdio>
#include <cstdlib>
#include <ctime>

#include "QSort.h"

#define N 10000000

int main()
{
std::list<int> L1;
long long sum=0,newSum=0;
for(int i = 0; i < N; ++i)
{
int d = rand();
sum+=d;
L1.push_back(d);
}

clock_t t = clock();
VLib::qsort(L1.begin(),L1.end());
clock_t et = clock();

[Ian Collins]

So not leaking memory is optional :)

--
Ian Collins

[jacob navia]

C: 6.6 s
C++ 14.760

See the analysis after this session transcript. Please try this in your
machine using the latest version of libccl.a


~/stl/test $ cat listexample.cpp

#include <list>
#include <cstdio>
#include <cstdlib>

#define N 10000000

int main()
{
std::list<int> L1;
long long sum=0,newSum=0;

int i;
for( i = 0; i < N; ++i)

{
int d = rand();
sum+=d;
L1.push_back(d);
}

L1.sort();

//for(auto it : L1)
std::list<int>::iterator it;
for(it=L1.begin(); it != L1.end(); ++it)
{
newSum+= *it;

}

if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);

}

~/stl/test $ g++ -O2 -o listexample-cpp listexample.cpp
~/stl/test $ time ./listexample-cpp
Sum = 10737818730605039

real 0m14.760s
user 0m14.438s
sys 0m0.320s
~/stl/test $ cat tintlist.c

~/stl/test $ gcc -O2 -I.. -o listexample-c tintlist.c ../libccl.a
~/stl/test $ time ./listexample-c
Sum = 10737818730605039

real 0m6.584s
user 0m6.319s
sys 0m0.258s
~/stl/test $

Analysis:
---------
The main problems in the C++code are:

1) malloc overhead. There are several solutions to that, but none are
standard.
2) Apparently the algorithm for sorting a list is different in C++ to
the one I use. I copy the list into a vector and sort the vector, then
copy the sorted result into a list again.

For example:
~/stl/test $ cat tintlist1.cpp

#include <list>
#include <vector>
#include <algorithm>

#include <cstdio>
#include <cstdlib>
#include <ctime>

#define N 10000000

int main()
{
std::list<int> L1;
long long sum=0,newSum=0;
for(int i = 0; i < N; ++i)
{
int d = rand();
sum+=d;
L1.push_back(d);
}

std::vector<int> tmp(L1.begin(),L1.end());
clock_t t = clock();
std::sort(tmp.begin(),tmp.end());
clock_t et = clock();
L1.clear();
L1.insert(L1.begin(),tmp.begin(),tmp.end());

printf("sort time %.3f\n",float(et - t)/CLOCKS_PER_SEC);

// for(auto it : L1)
std::list<int>::iterator it;
for(it=L1.begin(); it != L1.end(); ++it)

{
newSum+= *it;

}

if (sum != newSum)
printf("Failed\n");
else printf("Sum = %lld\n",sum);

}

This code takes only
~/stl/test $ time ./tintlist1-cpp
sort time 1.138
Sum = 10737818730605039

real 0m5.137s
user 0m4.656s
sys 0m0.476s

An improvement of 300%.

Of course now we aren't fair to C since I could have done a vector sort
and I would be faster than C++ anyway.

Conclusion:

Probably C and C++ go at the same speed.

[jacob navia]

Le 05/06/12 00:23, Ian Collins a écrit :

>> In the CCL you can ADD a destructor if you want but they are NOT
>> required as in C++.
>
> So not leaking memory is optional :)

No. You do a

iintList.Finalize(list);

The advantage is that you free ALL memory in a single call to a function
that destroys the heap not individually (list element by list element)
but in blocks of 1000 list elements each you see?

C++ calls destructors 100 million times. That takes time.

[MelissA]

On Tue, 5 Jun 2012 00:16:36 +0200
MelissA <me...@a.com> wrote:

>
> unsigned counthigh = 0,countlow = 0;

mine error
countlow should be 1, not 0 ;)

[BartC]

"jacob navia" <ja...@spamsink.net> wrote in message

news:jqj017$vai$1...@speranza.aioe.org...

> Le 04/06/12 20:18, BartC a écrit :

>> Thanks. Downloading the latest lcc 32-bits to make sure, this now gets
>> hung up on errors in wchar.h (first on line 521, then on line 509).
>>
>
> Ahhh you are using the distribution that comes with the compiler?

No. I updated lcc in case it was out-of-date and causing the problem. The
CCL stuff is separate.

In any case, this project doesn't need a makefile as it's straightforward
(now I know what's needed); I will leave that to the experts.

I wanted to test the speed of container lists versus ordinary arrays (I know
containers are more sophisticated but your test is simple so I'm looking at
just that).

The results of your test program weren't so interesting, because 95% of the
runtime seemed to be in sorting. So got rid of that, and just tested
allocating and iterating over 100M (not 10M) int objects. This took about 8
seconds and seem to use about 1.3GB of memory (is there a per-element
overhead?)

Using an ordinary allocated array, took only 1.7 seconds, and used the
expected 0.4GB of memory.

However this was *preallocated*, a possible advantage. (I ran the same test
on a dynamic language, which took 16 seconds, whether the int-array was
preallocated or not. Interestingly (need to verify this), using a
preallocated generic list only took 10 seconds, not far off the CCL timing
for a non-generic list).

It seems the conclusion, if my results are valid, is that if the
requirements are very simple, that ordinary C array handling should be
considered if speed and memory are important. Maybe you might want to put
forward a more elaborate test that isn't so easy to rewrite in standard C...

--
Bartc

[Luca Risolia]

On 05/06/2012 00:31, jacob navia wrote:
> Le 05/06/12 00:23, Ian Collins a �crit :

Not necessarily. Memory deallocation and object destruction are two
separate things usually controlled by an allocator. With regard to the
standard containers an allocator is always an (optional) template
parameter. If you really want, you can provide your preferred
deallocation strategy for a given type T to std::list, so that it frees
the memory in blocks of 1000 and doesn't destroy any object.

[Martin Shobe]

In the code that lead to this, the list was a list of ints. They don't
even have destructors to call, so the time certainly wasn't spent
calling them.

Martin Shobe

[MelissA]

Final QSort.h (corrected errors, this one is little bit slower)

#include <algorithm>

namespace VLib{
using std::swap;

template <typename T,typename F>
void qsort(T begin, T end, unsigned size, F f)
{
if(begin == end)return;

T high = end;
if(!size)
{
T tmp = begin;
while(tmp!=end){ high=tmp++;++size; }
}
else
{
--high;
}

if(size == 1)return;
T low = begin;

unsigned count = 0;
while(++count<size/2)++low;
// printf("size %u\n",size);
swap(*low,*begin);
low = begin;
++low;

unsigned counthigh = 0,countlow = 1;

[Juha Nieminen]

In comp.lang.c++ jacob navia <ja...@spamsink.net> wrote:
>> If you want to test sorting speed and nothing else, you have to discard
>> the time spent in memory allocation.
>
> Yes, but what I want to test is the speed to do ALL tasks mentioned above

Then you will be comparing C++'s default memory allocator speed to whatever
that C list was using.

[Noob]

pete wrote:

> I've never needed the three way comparison
> to implement any sorting algorithm.
>
> It has always been sufficient for me
> to merely use a (Greater Than) macro, GT(A, B),
> to implement any sorting algorithm.
>
> #define GT(A, B) ((*A)->Data > (*B)->Data)
>
> I have never needed to know whether two keys compare equal,
> in order to implement a sorting algorithm.

Perhaps it is needed when writing "stable" sorting algorithms?
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

[Ike Naar]

Equality of A and B follows from

!(GT(A, B) || GT(B, A))

provided that GT defines a total order.

[pete]

No. Definitely not.
When implementing any of the inherently stable algorithms,
such as bubble sort, insertion sort or merge sort,
it is sufficient to know only
whether or not the two keys being compared, are out of order.

The wikipedia article claims that the order
of the keys can be used as a tie breaker to convert
an unstable algorithm into a stable one,
but that is wrong because,
when two distant unequal keys are compared,
the only way to maintain stability
between those two keys and all of the keys in between them,
is to move all of the keys in between them.

Example:
Suppose you have this array:

char numbers[][sizeof "eight"] = {"seven","eight","six"};

and you want to do a stable sort according to string length,
the result of a stable sort would be {"six","seven","eight"}.

If you sorted {"seven","eight","six"}
by using a non stable sort such as simple selection sort,
using the key addresses as a tie breaker,
"seven" would not be out of order compared to "eight",
regardless of whether their addresses were used as a tie breaker.
But when "seven" was compared to "six",
those two keys would be out of order and swapped
with the final sort result being {"six","eight","seven"}.

--
pete

[Robert Wessel]

On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfi...@mindspring.com>
wrote:

You're misreading the Wikipedia article. It actually says "One way of
doing this is to artificially extend the key comparison, so that
comparisons between two objects with otherwise equal keys are decided
using the order of the entries in the original data order as a
tie-breaker." The critical bit is "the order of the entries in the
*original* data order as a tie-breaker." And that's quite correct. In
the case of "distant" records with nominally equal keys, you're
extending the comparison to be between (key, original record number)
tuples.

[pete]

It says
"Unstable sorting algorithms can be specially
implemented to be stable.""

> It actually says "One way of
> doing this is to artificially extend the key comparison, so that
> comparisons between two objects with otherwise equal keys are decided
> using the order of the entries in the original data order as a
> tie-breaker."
> The critical bit is "the order of the entries in the
> *original* data order as a tie-breaker." And that's quite correct. In
> the case of "distant" records with nominally equal keys, you're
> extending the comparison to be between (key, original record number)
> tuples.

But that is not one way of doing it,
that is only *part* of one way of doing it.

The example that I showed,
*did* use the original order as a tie breaker.
To convert a nonstable algorithm to a stable one,
is more complicated
than just using the original order as a tiebreaker.

The article then says
"Remembering this order, however,
often involves an additional computational cost."

But
"Remembering this order"
is more complicated than merely
"additional computational cost."

"Remembering this order" also requires additional memory usage,
at which point it becomes simpler to stable sort using merge sort,
which merely requires the simple GT(A,B) macro.

A fast merge sort can be either done directly,
using a buffer half the size of the original array,
or if the element size is greater than (4 * sizeof(void *))
a fast merge sort can be done with less additional memory
using 2 arrays of pointers instead.


--
pete

[Robert Wessel]

On Wed, 06 Jun 2012 09:10:37 -0400, pete <pfi...@mindspring.com>
wrote:

That's not what a tie breaker does. The sort keys for the three items
in your sample list are (5,1), (5,2) and (3,3). The (only) ordered
version of that is (3,3), (5,1), (5,2). With a multi-part key you
compare each segment, first to last, until you find an unequal one.
There's still just the one sort, just the comparison is more complex
(ignoring the issue, in this case, of where you get the information
about the original order - which is typically just stored as a counter
with each record).

>The article then says
>"Remembering this order, however,
> often involves an additional computational cost."
>
>But
> "Remembering this order"
>is more complicated than merely
> "additional computational cost."
>
>"Remembering this order" also requires additional memory usage,
>at which point it becomes simpler to stable sort using merge sort,
>which merely requires the simple GT(A,B) macro.

Yes, and I never disputed that.

>A fast merge sort can be either done directly,
>using a buffer half the size of the original array,
>or if the element size is greater than (4 * sizeof(void *))
>a fast merge sort can be done with less additional memory
>using 2 arrays of pointers instead.

If you have the conditions for a merge sort, it's one of the best
choices, if not the best choice. It does require additional storage
beyond the records to be sorted itself. Obviously so does adding the
extra key segment need to force a sort to be stable. Whether or not
stability is important is one of the tradeoffs in selecting a sort (in
fact, it's actually a fairly rare requirement).

[pete]

Robert Wessel wrote:
>
> On Wed, 06 Jun 2012 09:10:37 -0400, pete <pfi...@mindspring.com>
> wrote:
>
> >Robert Wessel wrote:
> >>
> >> On Wed, 06 Jun 2012 00:20:21 -0400, pete <pfi...@mindspring.com>
> >> wrote:
> >>
> >> >Noob wrote:
> >> >>
> >> >> pete wrote:
> >> >>
> >> >> > I've never needed the three way comparison
> >> >> > to implement any sorting algorithm.
> >> >> >
> >> >> > It has always been sufficient for me
> >> >> > to merely use a (Greater Than) macro, GT(A, B),
> >> >> > to implement any sorting algorithm.
> >> >> >
> >> >> > #define GT(A, B) ((*A)->Data > (*B)->Data)

> If you have the conditions for a merge sort, it's one of the best
> choices, if not the best choice. It does require additional storage
> beyond the records to be sorted itself. Obviously so does adding the
> extra key segment need to force a sort to be stable. Whether or not
> stability is important is one of the tradeoffs in selecting a sort (in
> fact, it's actually a fairly rare requirement).

Anyway,
the point that I was was originally trying to make to Jacob Navia,
still stands; Which is,
that I have never needed anything else but a GreaterThan macro,
to implement any kind of comparison sorting algorithm,
stable or otherwise.

--
pete

[88888 Dihedral]

Juha Nieminen於 2012年6月4日星期一UTC+8下午11時32分34秒寫道：

> In comp.lang.c++ MelissA <me...@a.com> wrote:

> > #define N 10000000
> >
> > int main()
> > {
> > std::list<int> L1;
> > long long sum=0,newSum=0;
> > for(int i = 0; i < N; ++i)
> > {
> > int d = rand();
> > sum+=d;
> > L1.push_back(d);
>

> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
>

> If you want to test sorting speed and nothing else, you have to discard
> the time spent in memory allocation.

For known numeric types of arrays to be sorted, then the radix sort is
faster if the allocation of the memory does not slow down a lot.illion

The problem is for the size of 100 million elements. I sugest
one can sort from the first digit of 8 to 12 bits for the first 2 or 3 digits.


Then one can sort those with the same prefax chunk by the traditional radix
sort if necessary, thus the cache hit rate is increased in all passes of digits.








Juha Nieminen於 2012年6月4日星期一UTC+8下午11時32分34秒寫道：

> In comp.lang.c++ MelissA <me...@a.com> wrote:

> > #define N 10000000
> >
> > int main()
> > {
> > std::list<int> L1;
> > long long sum=0,newSum=0;
> > for(int i = 0; i < N; ++i)
> > {
> > int d = rand();
> > sum+=d;
> > L1.push_back(d);
>

> Your test is basically useless as a measurement of sorting speed because
> the vast majority of the time will be spent on those push_back() calls.
>

[Willem]

pete wrote:
) Anyway,
) the point that I was was originally trying to make to Jacob Navia,
) still stands; Which is,
) that I have never needed anything else but a GreaterThan macro,
) to implement any kind of comparison sorting algorithm,
) stable or otherwise.

Speaking theoretically: You can implement an 'Equals' macro in terms
of a 'GreaterThan' macro easily, so all you need is 'GreaterThan'.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[jacob navia]

Le 07/06/12 01:49, pete a écrit :

>
> Anyway,
> the point that I was was originally trying to make to Jacob Navia,
> still stands; Which is,
> that I have never needed anything else but a GreaterThan macro,
> to implement any kind of comparison sorting algorithm,
> stable or otherwise.
>

Maybe you have some spare time?

I am convinced my code would benefit from your critical eye Pete.

Just download it from

http://code.google.com/p/ccl/

and look at it. The file listgen.c contains the templated sort function.

[pete]

jacob navia wrote:
>
> Le 07/06/12 01:49, pete a écrit :
> >
> > Anyway,
> > the point that I was was originally trying to make to Jacob Navia,
> > still stands; Which is,
> > that I have never needed anything else but a GreaterThan macro,
> > to implement any kind of comparison sorting algorithm,
> > stable or otherwise.
> >
>
> Maybe you have some spare time?

From time to time, I have some time.

> I am convinced my code would benefit from your critical eye Pete.
>
> Just download it from
>
> http://code.google.com/p/ccl/
>
> and look at it.
> The file listgen.c contains the templated sort function.

I will take a look at it.

At this point, it occurs to me
that if you have searching functions
which use exactly the same COMPARE_EXPRESSION macro,
as your sorting functions use,
then it might be necessary to use the three way comparison.

Do you have searching functions which use
exactly the same COMPARE_EXPRESSION macro,
as your sorting functions use?

--
pete

[pete]

jacob navia wrote:

> I am convinced my code would benefit from your critical eye Pete.
>
> Just download it from
>
> http://code.google.com/p/ccl/
>
> and look at it.
> The file listgen.c contains the templated sort function.

The first mistake that I noticed, is a common one.

In
static void QSORT(LIST_ELEMENT **base, size_t num)
these two expressions
COMPARE_EXPRESSION(loguy,lo) <= 0
COMPARE_EXPRESSION(higuy,lo) >= 0
should be written this way
COMPARE_EXPRESSION(loguy,lo) < 0
COMPARE_EXPRESSION(higuy,lo) > 0
to properly address the issue of
How to handle keys equal to the partitioning element?

See page 4 of
http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
How to handle keys equal to the partitioning element?
by Robert Sedgewick and Jon Bentley.

--
pete

[pete]

jacob navia wrote:

> Maybe you have some spare time?
>
> I am convinced my code would benefit from your critical eye Pete.
>
> Just download it from
>
> http://code.google.com/p/ccl/
>
> and look at it.
> The file listgen.c contains the templated sort function.

/*
** On 6 September 2008, I posted pqsort.
**
** http://groups.google.com/group/comp.lang.c/msg/6a73e359f4814457
**
** This is a version of listgen.c with a new QSORT based on pqsort.
** It's an introspective quicksort.
** If you like, I can toss in a PRNG for the pivot selection.
** Try it.
*/
/* BEGIN listgen.c */
/*
* Value types generic list routines sample implementation
* ----------------------------------- ------------------
* Thisroutines handle the List container class. This is a very general
* implementation and efficiency considerations aren't yet primordial.
Lists
* can have elements of any size. This implement single linked Lists.
The
* design goals here are just correctness and showing how the
implementation
* of the proposed interface COULD be done.
*
----------------------------------------------------------------------
*/

#include "listgen.h"
#include "ccl_internal.h"

#include <assert.h>

/* Forward declarations */
static LIST_TYPE *SetVTable(LIST_TYPE *result);
static LIST_TYPE * Create(size_t elementsize);
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator);
#define CONTAINER_LIST_SMALL 2
#define CHUNK_SIZE 1000

static int DefaultListCompareFunction(const void * left, const void *
right, CompareInfo * ExtraArgs)
{
size_t siz = ((LIST_TYPE *)
ExtraArgs->ContainerLeft)->ElementSize;
return memcmp(left, right, siz);
}

/*------------------------------------------------------------------------
Procedure: Contains ID:1
Purpose: Determines if the given data is in the container
Input: The list and the data to be searched
Output: Returns 1 (true) if the data is in there, false
otherwise
Errors: The same as the function IndexOf
------------------------------------------------------------------------*/
static int Contains(const LIST_TYPE * l, const DATA_TYPE data)
{
size_t idx;
return (iList.IndexOf((List *)l, &data, NULL, &idx) < 0) ? 0 : 1;
}

static int Add(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.Add((List *)l,&elem);
}

/*------------------------------------------------------------------------
Procedure: GetElement ID:1
Purpose: Returns the data associated with a given position
Input: The list and the position
Output: A pointer to the data
Errors: NULL if error in the positgion index
------------------------------------------------------------------------*/
static DATA_TYPE GetElement(const LIST_TYPE * l, size_t position)
{
DATA_TYPE *pdata = iList.GetElement((List *)l,position);

if (pdata == NULL) return ERROR_RETURN;
return *pdata;
}

static DATA_TYPE Back(const LIST_TYPE * l)
{
DATA_TYPE *p = (DATA_TYPE *)iList.Back((List *)l);
if (p == NULL) return ERROR_RETURN;
return *p;
}

static DATA_TYPE Front(const LIST_TYPE * l)
{
DATA_TYPE *p = (DATA_TYPE *)iList.Front((List *)l);
if (p == NULL) return ERROR_RETURN;
return *p;
}

static int CopyElement(const LIST_TYPE * l, size_t position, DATA_TYPE
*outBuffer)
{
return iList.CopyElement((List *)l,position,outBuffer);
}

static int ReplaceAt(LIST_TYPE * l, size_t position, const DATA_TYPE
data)
{
return iList.ReplaceAt((List *)l,position,&data);;
}

static int PushFront(LIST_TYPE * l, const DATA_TYPE pdata)
{
return iList.PushFront((List *)l,&pdata);
}


static int PopFront(LIST_TYPE * l, DATA_TYPE *result)
{
return iList.PushFront((List *)l,result);
}


static int InsertAt(LIST_TYPE * l, size_t pos, const DATA_TYPE pdata)
{
return iList.InsertAt((List *)l,pos,&pdata);
}

static int Erase(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.Erase((List *)l, &elem);
}

static int EraseAll(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.EraseAll((List *)l, &elem);
}

static int IndexOf(const LIST_TYPE * l, const DATA_TYPE ElementToFind,
void *ExtraArgs, size_t * result)
{
return iList.IndexOf((List *)l, &ElementToFind, ExtraArgs, result);
}

static size_t Sizeof(const LIST_TYPE * l)
{
if (l == NULL) {
return sizeof(List);
}
return sizeof(LIST_TYPE) + l->ElementSize * l->count + l->count *
offsetof(LIST_ELEMENT,Data);
}

static size_t SizeofIterator(const LIST_TYPE * l)
{
return sizeof(struct ITERATOR(DATA_TYPE));
}

static LIST_TYPE *Load(FILE * stream, ReadFunction loadFn, void *arg)
{
LIST_TYPE *result = (LIST_TYPE *)iList.Load(stream,loadFn,arg);
return SetVTable(result);
}

/*
*
---------------------------------------------------------------------------
*
* Iterators
*
*
---------------------------------------------------------------------------
*/
static int ReplaceWithIterator(Iterator * it, DATA_TYPE data, int
direction)
{
struct ITERATOR(DATA_TYPE) *iter = (struct ITERATOR(DATA_TYPE) *)it;
return iter->ListReplace(it,&data,direction);
}

static Iterator *SetupIteratorVTable(struct ITERATOR(DATA_TYPE) *result)
{
if (result == NULL) return NULL;
result->ListReplace = result->it.Replace;
result->it.Replace = (int (*)(Iterator * , void * , int
))ReplaceWithIterator;
return &result->it;
}

static Iterator *NewIterator(LIST_TYPE * L)
{
return SetupIteratorVTable((struct ITERATOR(DATA_TYPE)
*)iList.NewIterator((List *)L));
}
static int InitIterator(LIST_TYPE * L, void *r)
{
iList.InitIterator((List *)L,r);
SetupIteratorVTable(r);
return 1;
}
static size_t GetElementSize(const LIST_TYPE * l)
{
return sizeof(DATA_TYPE);
}

static int Finalize(LIST_TYPE *l)
{
iList.Finalize((List *)l);
return 1;
}

static LIST_TYPE *Copy(const LIST_TYPE * l)
{
LIST_TYPE *result = (LIST_TYPE *)iList.Copy((List *)l);
return SetVTable(result);
}


static LIST_TYPE *SelectCopy(const LIST_TYPE *l,const Mask *m)
{
LIST_TYPE *result = (LIST_TYPE *)iList.SelectCopy((const List
*)l,m);
return SetVTable(result);
}

/*---------------------------------------------------------------------------*/
/* qsort() - perform a quicksort on an
array */
/*---------------------------------------------------------------------------*/

#ifndef COMPARE_EXPRESSION
#error foo
#define COMPARE_EXPRESSION(l,lo) comp(l, lo)
//COMPAR(A, B) (B > A ? -1 : B != A)
#endif

#define E_TYPE LIST_ELEMENT *e_type
#define GT(A, B) (COMPARE_EXPRESSION((A), (B)) > 0)
#define MOV(A, B) ((void)(*(A) = *(B)))
#define SMALL_PARTITION 8

#define SWAP(A, B, T) \
(MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))

#define SORT_3(A, B, C, T) \
if (GT((A), (B))) { \
MOV((T), (A)); \
if (GT((C), (B))) { \
MOV((A), (B)); \
if (GT((T), (C))) { \
MOV((B), (C)); \
MOV((C), (T)); \
} else { \
MOV((B), (T)); \
} \
} else { \
MOV((A), (C)); \
MOV((C), (T)); \
} \
} else { \
if (GT((B), (C))) { \
MOV((T), (B)); \
if (GT((A), (C))) { \
MOV((B), (A)); \
MOV((A), (C)); \
} else { \
MOV((B), (C)); \
} \
MOV((C), (T)); \
} \
}

#define SIFTDOWNM(P) \
{ \
parent = (P); \
child = parent * 2; \
MOV(&temp, array + parent); \
while (nmemb - parent > parent) { \
if (GT(array + child + 1, array + child)) { \
++child; \
} \
if (GT(array + child, &temp)) { \
MOV(array + parent, array + child); \
parent = child; \
child *= 2; \
} else { \
break; \
} \
} \
if (nmemb == child && GT(array + child, &temp)) { \
MOV(array + parent, array + child); \
parent = child; \
} \
MOV(array + parent, &temp); \
}

typedef E_TYPE;

static void sisort(e_type *array, size_t nmemb)
{
e_type *base, *low, *high, temp;

if (nmemb-- > 1) {
base = array;
do {
low = array++;
if (GT(low, array)) {
high = array;
MOV(&temp, high);
do {
MOV(high, low);
if (--high == base) {
break;
}
--low;
} while (GT(low, &temp));
MOV(high, &temp);
}
} while (--nmemb != 0);
}
}

static void jnloop(e_type *array, size_t nmemb, size_t d)
{
e_type *i, *j, temp;

while (nmemb > SMALL_PARTITION) {
if (!d--) {
hsortm(array, nmemb);
return;
}
i = nmemb / 2 + array;
SWAP(array, i, &temp);
i = 1 + array;
j = --nmemb + array;
SORT_3(j, array, i, &temp);
do {
SWAP(j, i, &temp);
do {
++i;
} while (GT(array, i));
do {
--j;
} while (GT(j, array));
} while (j > i);
SWAP(array, j, &temp);
jnloop(j + 1, nmemb + array - j, d);
nmemb = j - array;
}
sisort(array, nmemb);
}

static void hsortm(e_type *array, size_t nmemb)
{
size_t p, child, parent;
e_type temp;

if (nmemb > 1) {
p = --nmemb / 2;
do {
SIFTDOWNM(p);
} while (p-- != 0);
SWAP(array, array + nmemb, &temp);
while (--nmemb != 0) {
SIFTDOWNM(0);
SWAP(array, array + nmemb, &temp);
}
}
}

static void QSORT(e_type *array, size_t nmemb)
{
size_t d, n;

assert(SMALL_PARTITION >= 4);
d = 2;
for (n = nmemb / 4; n != 0; n /= 2) {
++d;
}
jnloop(array, nmemb, 2 * d);
}

static int Sort(LIST_TYPE * l)
{
LIST_ELEMENT **tab;
size_t i;
LIST_ELEMENT *rvp;

if (l == NULL)
return iError.NullPtrError("Sort");

if (l->count < 2)
return 1;
if (l->Flags & CONTAINER_READONLY) {
l->RaiseError("iList.Sort", CONTAINER_ERROR_READONLY);
return CONTAINER_ERROR_READONLY;
}
tab = l->Allocator->malloc(l->count * sizeof(LIST_ELEMENT *));
if (tab == NULL) {
l->RaiseError("iList.Sort", CONTAINER_ERROR_NOMEMORY);
return CONTAINER_ERROR_NOMEMORY;
}
rvp = l->First;
for (i = 0; i < l->count; i++) {
tab[i] = rvp;
rvp = rvp->Next;
}
QSORT(tab, l->count );
for (i = 0; i < l->count - 1; i++) {
tab[i]->Next = tab[i + 1];
}
tab[l->count - 1]->Next = NULL;
l->Last = tab[l->count - 1];
l->First = tab[0];
l->Allocator->free(tab);
return 1;

}
static LIST_TYPE *SetVTable(LIST_TYPE *result)
{
static int Initialized;
INTERFACE(DATA_TYPE) *intface = &INTERFACE_NAME(DATA_TYPE);

result->VTable = intface;
if (Initialized) return result;
Initialized = 1;
intface->FirstElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.FirstElement;
intface->LastElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.LastElement;
intface->Clear = (int (*)(LIST_TYPE *))iList.Clear;
intface->EraseAt = (int (*)(LIST_TYPE *,size_t))iList.EraseAt;
intface->RemoveRange = (int (*)(LIST_TYPE
*,size_t,size_t))iList.RemoveRange;
intface->Select = (int (*)(LIST_TYPE *,const Mask *))iList.Select;
intface->SetFlags = (unsigned (*)(LIST_TYPE
*,unsigned))iList.SetFlags;
intface->GetFlags = (unsigned (*)(const LIST_TYPE *))iList.GetFlags;
intface->SetDestructor = (DestructorFunction (*)(LIST_TYPE *,
DestructorFunction))iList.SetDestructor;
intface->Apply = (int (*)(LIST_TYPE *, int (Applyfn) (DATA_TYPE *,
void * ), void *))iList.Apply;
intface->Reverse = (int (*)(LIST_TYPE *))iList.Reverse;
intface->SetCompareFunction = (CompareFunction (*)(LIST_TYPE *,
CompareFunction ))iList.SetCompareFunction;
intface->GetRange = (LIST_TYPE *(*)(const LIST_TYPE * , size_t,
size_t))iList.GetRange;
intface->Skip = (LIST_ELEMENT *(*)(LIST_ELEMENT *,
size_t))iList.Skip;
intface->Append = (int (*)(LIST_TYPE *, LIST_TYPE *))iList.Append;
intface->Equal = (int (*)(const LIST_TYPE *, const LIST_TYPE
*))iList.Equal;
intface->InsertIn = (int (*)(LIST_TYPE *, size_t, LIST_TYPE
*))iList.InsertIn;
intface->AddRange = (int (*)(LIST_TYPE *, size_t, const DATA_TYPE
*))iList.AddRange;
intface->SetErrorFunction = (ErrorFunction (*)(LIST_TYPE *,
ErrorFunction))iList.SetErrorFunction;
intface->SetFlags = (unsigned (*)(LIST_TYPE * l, unsigned
newval))iList.SetFlags;
intface->RemoveRange = (int (*)(LIST_TYPE *, size_t,
size_t))iList.RemoveRange;
intface->UseHeap = (int (*)(LIST_TYPE *, const ContainerAllocator
*))iList.UseHeap;
intface->RotateLeft = (int (*)(LIST_TYPE *,
size_t))iList.RotateLeft;
intface->RotateRight = (int (*)(LIST_TYPE *,
size_t))iList.RotateRight;
intface->Save = (int (*)(const LIST_TYPE *, FILE *, SaveFunction,
void *))iList.Save;
intface->Size = (size_t (*)(const LIST_TYPE *))iList.Size;
intface->deleteIterator = (int (*)(Iterator *))iList.deleteIterator;
intface->SplitAfter = (LIST_TYPE *(*)(LIST_TYPE *, LIST_ELEMENT
*))iList.SplitAfter;
return result;
}

/*------------------------------------------------------------------------
Procedure: Create ID:1
Purpose: Allocates a new list object header, initializes the
VTable field and the element size
Input: The size of the elements of the list.
Output: A pointer to the newly created list or NULL if
there is no memory.
Errors: If element size is smaller than zero an error
routine is called. If there is no memory result is
NULL.

------------------------------------------------------------------------*/
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), allocator);
return SetVTable(result);
}

static LIST_TYPE * Create(size_t elementsize)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), CurrentAllocator);
return SetVTable(result);
}

static LIST_TYPE *InitializeWith(size_t elementSize, size_t n, const
void *Data)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.InitializeWith(sizeof(DATA_TYPE),n,Data);
return SetVTable(result);
}

static LIST_TYPE *InitWithAllocator(LIST_TYPE * result, size_t
elementsize,
const ContainerAllocator * allocator)
{
iList.InitWithAllocator((List *)result,sizeof(DATA_TYPE),allocator);
return SetVTable(result);
}

static LIST_TYPE * Init(LIST_TYPE * result, size_t elementsize)
{
return InitWithAllocator(result, elementsize, CurrentAllocator);
}

static const ContainerAllocator *GetAllocator(const LIST_TYPE * l)
{
if (l == NULL)
return NULL;
return l->Allocator;
}

static LIST_ELEMENT *NextElement(LIST_ELEMENT *le)
{
if (le == NULL) return NULL;
return le->Next;
}

static DATA_TYPE ElementData(LIST_ELEMENT *le)
{
if (le == NULL) return ERROR_RETURN;
return le->Data;
}

static int SetElementData(LIST_TYPE *l,LIST_ELEMENT *le,DATA_TYPE data)
{
return iList.SetElementData((List *)l,(ListElement *)le,&data);
}

static DATA_TYPE Advance(LIST_ELEMENT **ple)
{
LIST_ELEMENT *le;
DATA_TYPE result;

if (ple == NULL) {
iError.NullPtrError("Advance");
return ERROR_RETURN;
}
le = *ple;
if (le == NULL) return ERROR_RETURN;
result = le->Data;
le = le->Next;
*ple = le;
return result;
}

INTERFACE(DATA_TYPE) INTERFACE_NAME(DATA_TYPE) = {
NULL, // Size
NULL, // GetFlags,
NULL, // SetFlags,
NULL, // Clear,
Contains,
Erase,
EraseAll,
Finalize,
NULL, // Apply
NULL, // Equal
Copy,
NULL, // SetErrorFunction,
Sizeof,
NewIterator,
InitIterator,
NULL, // deleteIterator,
SizeofIterator,
NULL, // Save,
Load,
GetElementSize,
/* end of generic part */
Add,
GetElement,
PushFront,
PopFront,
InsertAt,
NULL, // EraseAt
ReplaceAt,
IndexOf,
/* End of sequential container part */
NULL, // InsertIn,
CopyElement,
NULL, // EraseRange,
Sort,
NULL, // Reverse,
NULL, // GetRange,
NULL, // Append,
NULL, // SetCompareFunction,
DefaultListCompareFunction,
NULL, // UseHeap,
NULL, // AddRange,
Create,
CreateWithAllocator,
Init,
InitWithAllocator,
GetAllocator,
NULL, // SetDestructor
InitializeWith,
Back,
Front,
NULL, // RemoveRange,
NULL, // RotateLeft,
NULL, // RotateRight,
NULL, // Select,
SelectCopy,
NULL, // FirstElement,
NULL, // LastElement,
NextElement,
ElementData,
SetElementData,
Advance,
NULL, // Skip,
NULL, // SplitAfter,
};
/* END listgen.c */

--
pete

[88888 Dihedral]

pete於 2012年6月10日星期日UTC+8上午11時49分21秒寫道：

This part is the heap sort here.

In my experience this is good in sorting for more than 30 elelments.

If the length of the unsorted array is considered, then one might need
3 to 4 sorting procedures to cover the desired range of the lengths of the arrays for the critical part.

[pete]

88888 Dihedral wrote:
>
> pete於 2012年6月10日星期日UTC+8上午11時49分21秒寫道：
> > jacob navia wrote:
> >
> > > Maybe you have some spare time?

> > ** This is a version of listgen.c with a new QSORT based on pqsort.
> > ** It's an introspective quicksort.
> > ** If you like, I can toss in a PRNG for the pivot selection.

sisort is an insertion sort.
hsortm is a heap sort.
QSORT, as implemented in this post, is an introsort.
The purpose of the heap sort is to take over
and keep the sort O(N*log(N))
in case of the quick sort starting to go quadratic.

http://en.wikipedia.org/wiki/Introsort

--
pete