Sam Schetterer wrote:

Hi. I am just wondering if there is still interest in the library, because I have not recieved any comments on the library in the last two days, no posts at all, while I have made multiple posts, some with very important ideas in them.

Hi Sam, I downloaded your library to do some testing. The first issue I ran into was that MSVC 7.1 complained about some of the specializations: template<> void insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r) and template<> void r_insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r) (This may be a vc 7.1 bug, I'm not sure.) The second issue is that in rquicksort.hpp (and possibly other places), a lot of the functions have parameters named 'strfnc', but the functions use parameters named 'strfunc'. The final issue is that create_id_string has some bugs. (It only works if %s is the first control sequence it encounters, so format strings like "%e" will crash.) After fixing those issues, I found that the radix_qsort and radix_sort are slower than standard sort. Maybe this is a result of when I commented out the specializations of insertion and r_insertion? I've attached the changes I made to the sorting stuff to get it to compile and run on MSVC 7.1. I've also included the code that I used to get the timings. (I know that timings are difficult to get, and I welcome any comments/criticisms. Perhaps my results are bad because I ended up sorting an already sorted array. However, all of the sorts were fast enough that I had to do this to a non-zero number.) Here are my results: radix_sort: people = 0.94s, radixtest = 0.12s radix_qsort: people = 0.69s, radixtest = 2.4s std::sort: people = 0.037s, radixtest = 0.015s Specs: Windows XP Professional x64 SP2, Visual C++ 7.1, Intel Xeon dual core @ 2.66GHz, 2.0 GB RAM. Do you have anything that shows that your code beats std::sort? David //include file for radix quicksort #ifndef BOOST_RQUICKSORT_HPP #define BOOST_RQUICKSORT_HPP #include <cstring> #include <cstdlib> #include "detail/insertion.hpp" #include <stdarg.h> namespace boost { namespace detail { template<class T> inline unsigned char qdigit(const T& a, int d) { return a.idstring_qs[d]; } typedef char* cptr; template<> inline unsigned char qdigit<cptr>(const cptr& a, int d) { return a[d]; } template<class T> void rquicksort(T* ar, int l, int r, int bit) { if((r - l) <= 16) { insertion(ar, l, r); return;} register T* a = ar; register int i = l - 1, j = r, d = bit, v = qdigit(a[j], d);//speed increase with registers int p = i, q = j; while(i < j) { while(qdigit(a[++i], d) < v) ; while(v < qdigit(a[--j], d)) if(j == l) break; if(i > j) break; std::swap(a[i], a[j]); if(qdigit(a[i], d) == v) {++p; std::swap(a[p], a[i]);} if(qdigit(a[j], d) == v) {--q; std::swap(a[q], a[j]);} } if(p == q) { if(v != '\0') rquicksort(a, l, r, d + 1); return; } if(qdigit(a[i], d) < v) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(a[k], a[j]); for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]); rquicksort(a, l, j, d); if((i == r) && (qdigit(a[i], d) == v)) ++i; if(v != '\0') rquicksort(a, j + 1, i - 1, d + 1); rquicksort(a, i, r, d); } template<class T> void rrquicksort(T* ar, int l, int r, int bit) { if((r - l) <= 16) { r_insertion(ar, l, r); return;} register T* a = ar; register int i = l - 1, j = r, d = bit, v = qdigit(a[j], d);//speed increase with registers int p = i, q = j; while(i < j) { while(v < qdigit(a[++i], d)) ; while(qdigit(a[--j], d) < v) if(j == l) break; if(i > j) break; std::swap(a[i], a[j]); if(qdigit(a[i], d) == v) {++p; std::swap(a[p], a[i]);} if(qdigit(a[j], d) == v) {--q; std::swap(a[q], a[j]);} } if(p == q) { if(v != '\0') rrquicksort(a, l, r, d + 1); return; } if(v < qdigit(a[i], d)) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(a[k], a[j]); for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]); rrquicksort(a, l, j, d); if((i == r) && (qdigit(a[i], d) == v)) ++i; if(v != '\0') rrquicksort(a, j + 1, i - 1, d + 1); rrquicksort(a, i, r, d); } } template<class T> inline void radix_qsort(T* data, int size) //normal { detail::rquicksort(data, 0, size, 0); } template<class T> inline void r_radix_qsort(T* data, int size) //reverse { detail::rrquicksort(data, 0, size, 0); } /////////////////////////user-defined functions namespace detail { template<class T> void rquicksort(T* ar, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) { if((r - l) <= 16) { insertion(ar, l, r, ltfunc); return;} register T* a = ar; register int i = l - 1, j = r, d = bit, v = strfunc(a[j], d); int p = i, q = j; while(i < j) { while(strfunc(a[++i], d) < v) ; while(v < strfunc(a[--j], d)) if(j == l) break; if(i > j) break; std::swap(a[i], a[j]); if(strfunc(a[i], d) == v) {++p; std::swap(a[p], a[i]);} if(strfunc(a[j], d) == v) {--q; std::swap(a[q], a[j]);} } if(p == q) { if(v != '\0') rquicksort(a, l, r, d + 1); return; } if(strfunc(a[i], d) < v) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(a[k], a[j]); for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]); rquicksort(a, l, j, d); if((i == r) && (strfunc(a[i], d) == v)) ++i; if(v != '\0') rquicksort(a, j + 1, i - 1, d + 1); rquicksort(a, i, r, d); } template<class T> void rrquicksort(T* ar, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) { if((r - l) <= 16) { r_insertion(ar, l, r, ltfunc); return;} register T* a = ar; register int i = l - 1, j = r, d = bit, v = strfunc(a[j], d);//speed increase with registers int p = i, q = j; while(i < j) { while(v < strfunc(a[++i], d)) ; while(strfunc(a[--j], d) < v) if(j == l) break; if(i > j) break; std::swap(a[i], a[j]); if(strfunc(a[i], d) == v) {++p; std::swap(a[p], a[i]);} if(strfunc(a[j], d) == v) {--q; std::swap(a[q], a[j]);} } if(p == q) { if(v != '\0') rrquicksort(a, l, r, d + 1); return; } if(v < strfunc(a[i], d)) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(a[k], a[j]); for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]); rrquicksort(a, l, j, d); if((i == r) && (strfunc(a[i], d) == v)) ++i; if(v != '\0') rrquicksort(a, j + 1, i - 1, d + 1); rrquicksort(a, i, r, d); } } template<class T> inline void radix_qsort(T* data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //normal { detail::rquicksort(data, 0, size, 0, strfunc, ltfunc); } template<class T> inline void r_radix_qsort(T* data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //reverse { detail::rrquicksort(data, 0, size, 0, strfunc, ltfunc); } //////////////////////////////////////////////////////////////////////////variable bytes template<class T> inline void radix_qsort(T* a, int size, int startbyte) { detail::rquicksort(a, 0, size, startbyte); } template<class T> inline void radix_qsort(T* a, int start, int size, int startbyte) { detail::rquicksort(a, start, size, startbyte); } template<class T> inline void radix_qsort(T* a, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&)) { detail::rquicksort(a, 0, size, startbyte, strfunc, ltfunc); } template<class T> inline void radix_qsort(T* a, int start, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&)) { detail::rquicksort(a, start, size, startbyte, strfunc, ltfunc); } ////////////////////////////////////////////////////////////stl iterator namespace detail { template<class T> void rquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit) { if((r - l) <= 16) { insertion<T>(a, l, r); return;} register int i = l - 1, j = r, d = bit, v = qdigit(*(a + j), d);//speed increase with registers int p = i, q = j; while(i < j) { while(qdigit(*(a + ++i), d) < v) ; while(v < qdigit(*(a + --j), d)) if(j == l) break; if(i > j) break; std::swap(*(a + i), *(a + j)); if(qdigit(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));} if(qdigit(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));} } if(p == q) { if(v != '\0') rquicksort<T>(a, l, r, d + 1); return; } if(qdigit(*(a + i), d) < v) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j)); for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i)); rquicksort<T>(a, l, j, d); if((i == r) && (qdigit(*(a + i), d) == v)) ++i; if(v != '\0') rquicksort<T>(a, j + 1, i - 1, d + 1); rquicksort<T>(a, i, r, d); } template<class T> void rrquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit) { if((r - l) <= 16) { r_insertion<T>(a, l, r); return;} register int i = l - 1, j = r, d = bit, v = qdigit(*(a + j), d);//speed increase with registers int p = i, q = j; while(i < j) { while(v < qdigit(*(a + ++i), d)) ; while(qdigit(*(a + --j), d) < v) if(j == l) break; if(i > j) break; std::swap(*(a + i), *(a + j)); if(qdigit(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));} if(qdigit(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));} } if(p == q) { if(v != '\0') rrquicksort<T>(a, l, r, d + 1); return; } if(v < qdigit(*(a + i), d)) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j)); for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i)); rrquicksort<T>(a, l, j, d); if((i == r) && (qdigit(*(a + i), d) == v)) ++i; if(v != '\0') rrquicksort<T>(a, j + 1, i - 1, d + 1); rrquicksort<T>(a, i, r, d); } } template<class T> inline void radix_qsort(typename std::deque<T>::iterator& data, int size) //normal { detail::rquicksort<T>(data, 0, size, 0); } template<class T> inline void r_radix_qsort(typename std::deque<T>::iterator& data, int size) //reverse { detail::rrquicksort<T>(data, 0, size, 0); } /////////////////////////user-defined functions namespace detail { template<class T> void rquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) { if((r - l) <= 16) { insertion<T>(a, l, r, ltfunc); return;} register int i = l - 1, j = r, d = bit, v = strfunc(*(a + j), d); int p = i, q = j; while(i < j) { while(strfunc(*(a + ++i), d) < v) ; while(v < strfunc(*(a + --j), d)) if(j == l) break; if(i > j) break; std::swap(*(a + i), *(a + j)); if(strfunc(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));} if(strfunc(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));} } if(p == q) { if(v != '\0') rquicksort<T>(a, l, r, d + 1); return; } if(strfunc(*(a + i), d) < v) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j)); for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i)); rquicksort<T>(a, l, j, d); if((i == r) && (strfunc(*(a + i), d) == v)) ++i; if(v != '\0') rquicksort<T>(a, j + 1, i - 1, d + 1); rquicksort<T>(a, i, r, d); } template<class T> void rrquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) { if((r - l) <= 16) { r_insertion<T>(a, l, r, ltfunc); return;} register int i = l - 1, j = r, d = bit, v = strfunc(*(a + j), d);//speed increase with registers int p = i, q = j; while(i < j) { while(v < strfunc(*(a + ++i), d)) ; while(strfunc(*(a + --j), d) < v) if(j == l) break; if(i > j) break; std::swap(*(a + i), *(a + j)); if(strfunc(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));} if(strfunc(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));} } if(p == q) { if(v != '\0') rrquicksort<T>(a, l, r, d + 1); return; } if(v < strfunc(*(a + i), d)) ++i; int k = l; for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j)); for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i)); rrquicksort<T>(a, l, j, d); if((i == r) && (strfunc(*(a + i), d) == v)) ++i; if(v != '\0') rrquicksort<T>(a, j + 1, i - 1, d + 1); rrquicksort<T>(a, i, r, d); } } template<class T> inline void radix_qsort(typename std::deque<T>::iterator& data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //normal { detail::rquicksort<T>(data, 0, size, 0, strfunc, ltfunc); } template<class T> inline void r_radix_qsort(typename std::deque<T>::iterator& data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //reverse { detail::rrquicksort<T>(data, 0, size, 0, strfunc, ltfunc); } //////////////////////////////////////////////////////////////////////////variable bytes template<class T> inline void radix_qsort(typename std::deque<T>::iterator& a, int size, int startbyte) { detail::rquicksort<T>(a, 0, size, startbyte); } template<class T> inline void radix_qsort(typename std::deque<T>::iterator& a, int start, int size, int startbyte) { detail::rquicksort<T>(a, start, size, startbyte); } template<class T> inline void radix_qsort(typename std::deque<T>::iterator& a, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&)) { detail::rquicksort<T>(a, 0, size, startbyte, strfunc, ltfunc); } template<class T> inline void radix_qsort(typename std::deque<T>::iterator& a, int start, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&)) { detail::rquicksort<T>(a, start, size, startbyte, strfunc, ltfunc); } std::size_t create_id_string(const char* fmt, char* dest, ...) { va_list ap; const char* p; std::size_t n = 0; va_start(ap, dest); for(p = fmt; *p; p++) { if(*p != '%') { dest[n++] = *p; continue; } switch(*++p) { case 'd': case 'D': case 'i': case 'I': { int itemp = va_arg(ap, int); _ui64toa(itemp, (char*)(dest+n), 16); n += strlen(dest+n); break; } case 's': case 'S': { const char *ctemp = va_arg(ap, const char*); strcpy(dest+n, ctemp); n += strlen(dest+n); break; } case 'e': case 'E': case 'g': case 'G': { double dtemp = va_arg(ap, double); long long dval = *((long long*)&dtemp); _ui64toa(dval, (char*)(dest+n), 16); n += strlen(dest+n); break; } default: { dest[n++] = *p; break; } } } dest[n++] = '\0'; va_end(ap); return n + 1; //1 compenstates for zero index array } } #endif #ifndef BOOST_DETAIL_INSERTION_HPP #define BOOST_DETAIL_INSERTION_HPP #include <algorithm> #include <cstring> #include <deque> namespace boost { namespace detail { template<class T> void insertion(T* ar, int l, int r) { register T* a = ar; register int i; for(i = r; i > l; i--) if(a[i] < a[i - 1]) std::swap<T>(a[i], a[i - 1]); for(i = l + 2; i <= r; i++) { register int j = i; T v = a[i]; while(v < a[j - 1]) { a[j] = a[j - 1]; --j; } a[j] = v; } } template<> void insertion<char*>(char** ar, int l, int r) { register char** a = ar; register int i; for(i = r; i > l; i--) if(strcmp(a[i], a[i - 1]) & 0x80000000) std::swap<char*>(a[i], a[i - 1]); for(i = l + 2; i <= r; i++) { register int j = i; register char* v = a[i]; while(strcmp(v, a[j - 1]) & 0x80000000) { a[j] = a[j - 1]; --j; } a[j] = v; } } template<class T> void r_insertion(T* ar, int l, int r) { register T* a = ar; register int i; for(i = r; i > l; i--) if(a[i - 1] < a[i]) std::swap<T>(a[i], a[i - 1]); for(i = l + 2; i <= r; i++) { register int j = i; T v = a[i]; while(a[j - 1] < v) { a[j] = a[j - 1]; --j; } a[j] = v; } } template<> void r_insertion<char*>(char** ar, int l, int r) { register char** a = ar; register int i; for(i = r; i > l; i--) if(strcmp(a[i - 1], a[i]) & 0x80000000) std::swap<char*>(a[i], a[i - 1]); for(i = l + 2; i <= r; i++) { register int j = i; char* v = a[i]; while(strcmp(a[j - 1], v) & 0x80000000) { a[j] = a[j - 1]; --j; } a[j] = v; } } //////////////user-defined template<class T> void insertion(T* ar, int l, int r, bool(*ltfunc)(const T&, const T&)) { register T* a = ar; register int i; for(i = r; i > l; i--) if(lt(a[i], a[i - 1])) std::swap<T>(a[i], a[i - 1]); for(i = l + 2; i <= r; i++) { register int j = i; T v = a[i]; while(lt(v, a[j - 1])) { a[j] = a[j - 1]; --j; } a[j] = v; } } template<class T> void r_insertion(T* ar, int l, int r, bool(*ltfunc)(const T&, const T&)) { register T* a = ar; register int i; for(i = r; i > l; i--) if(lt(a[i - 1], a[i])) std::swap<T>(a[i], a[i - 1]); for(i = l + 2; i <= r; i++) { register int j = i; T v = a[i]; while(lt(a[j - 1], v)) { a[j] = a[j - 1]; --j; } a[j] = v; } } ///////////////////////////////////////////////////////////////////////standard library sorters template<class T> void insertion(typename std::deque<T>::iterator& a, int l, int r) { register int i; for(i = r; i > l; i--) if(*(a + i) < *(a + i - 1)) std::swap<T>(*(a + i), *(a + i - 1)); for(i = l + 2; i <= r; i++) { register int j = i; T v = *(a + i); while(v < *(a + j - 1)) { *(a + j) = *(a + j - 1); --j; } *(a + j) = v; } } //template<> //void insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r) //{ // register int i; // for(i = r; i > l; i--) if(strcmp(*(a + i), *(a + i - 1)) & 0x80000000) std::swap<char*>(*(a + i), *(a + i - 1)); // for(i = l + 2; i <= r; i++) // { // register int j = i; register char* v = *(a + i); // while(strcmp(v, *(a + j - 1)) & 0x80000000) // { // *(a + j) = *(a + j - 1); // --j; // } // *(a + j) = v; // } //} template<class T> void r_insertion(typename std::deque<T>::iterator& a, int l, int r) { register int i; for(i = r; i > l; i--) if(*(a + i - 1) < *(a + i)) std::swap<T>(*(a + i), *(a + i - 1)); for(i = l + 2; i <= r; i++) { register int j = i; T v = *(a + i); while(*(a + j - 1) < v) { *(a + j) = *(a + j - 1); --j; } *(a + j) = v; } } //template<> //void r_insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r) //{ // register int i; // for(i = r; i > l; i--) if(strcmp(*(a + i - 1), *(a + i)) & 0x80000000) std::swap<char*>(*(a + i), *(a + i - 1)); // for(i = l + 2; i <= r; i++) // { // register int j = i; char* v = *(a + i); // while(strcmp(*(a + j - 1), v) & 0x80000000) // { // *(a + j) = *(a + j - 1); // --j; // } // *(a + j) = v; // } //} //////////////user-defined template<class T> void insertion(typename std::deque<T>::iterator& a, int l, int r, bool(*ltfunc)(const T&, const T&)) { register int i; for(i = r; i > l; i--) if(lt(*(a + i), *(a + i - 1))) std::swap<T>(*(a + i), *(a + i - 1)); for(i = l + 2; i <= r; i++) { register int j = i; T v = *(a + i); while(lt(v, *(a + j - 1))) { *(a + j) = *(a + j - 1); --j; } *(a + j) = v; } } template<class T> void r_insertion(typename std::deque<T>::iterator& a, int l, int r, bool(*ltfunc)(const T&, const T&)) { register int i; for(i = r; i > l; i--) if(lt(*(a + i - 1), *(a + i))) std::swap<T>(*(a + i), *(a + i - 1)); for(i = l + 2; i <= r; i++) { register int j = i; T v = *(a + i); while(lt(*(a + j - 1), v)) { *(a + j) = *(a + j - 1); --j; } *(a + j) = v; } } } } #endif #include <iostream> #include <string> #include <vector> #include <ctime> #define STD_SORT 0 #define RADIX_Q_SORT 1 #define RADIX_SORT 2 // -------------------------------------- // TODO: Set SORT_TYPE to one of: // STD_SORT, RADIX_Q_SORT, or RADIX_SORT // -------------------------------------- #define SORT_TYPE RADIX_SORT #if (SORT_TYPE == RADIX_Q_SORT) #include <boost/sorting/rquicksort.hpp> #elif (SORT_TYPE == RADIX_SORT) #include <boost/sorting/radix.hpp> #include <boost/sorting/rquicksort.hpp> // for create_id_string #else // std::sort #include <algorithm> #endif static double doublerand() { double a = static_cast<double>(rand()); double b = static_cast<double>(rand()); double c = static_cast<double>(rand()); return (a*b)/c; } static std::string stringrand() { std::string s; for(int i=0 ; i<5 ; ++i) { s += static_cast<char>(rand() % 26) + 'a'; } return s; } static int intrand() {return rand();} struct person { std::string name; int iNum; double fNum; int order; #if ((SORT_TYPE == RADIX_Q_SORT) || (SORT_TYPE == RADIX_SORT)) static const int STR_SZ = 30; char idstring_qs[STR_SZ]; #endif person(){} person(int iOrder, int inum, const std::string &n, double w) { order = iOrder; iNum = inum; name = n; fNum = w; #if ((SORT_TYPE == RADIX_Q_SORT) || (SORT_TYPE == RADIX_SORT)) //%s means string, %d means int, and %e means double boost::create_id_string("%s%e%d", idstring_qs, name.c_str(), fNum, iNum); #endif } #if (SORT_TYPE == RADIX_Q_SORT) inline int operator<(const person& rhs) const { return strcmp(idstring_qs, rhs.idstring_qs) & 0x80000000; } #elif (SORT_TYPE == RADIX_SORT) inline unsigned char operator[](int d) const { return idstring_qs[d]; } #else // std::sort inline bool operator<(const person& rhs) { if(name < rhs.name) return true; if(rhs.name < name) return false; if(fNum < rhs.fNum) return true; if(rhs.fNum < fNum) return false; return (iNum < rhs.iNum); } #endif }; static void FillData(std::vector<double> &vec_d, std::vector<int> &vec_i, std::vector<std::string> &vec_s, std::size_t desired_size) { vec_d.clear(); vec_d.reserve(desired_size); vec_i.clear(); vec_i.reserve(desired_size); vec_s.clear(); vec_s.reserve(desired_size); for(std::size_t i=0 ; i<desired_size ; ++i) { vec_d.push_back(doublerand()); vec_i.push_back(intrand()); vec_s.push_back(stringrand()); } } // We want a large number of objects to sort, but we don't // want it to crash if it can't find enough stack space. static const std::size_t NUM_PEOPLE = 10000; static void PrintPeople(const person people[NUM_PEOPLE]) { for(int x = 0; x < NUM_PEOPLE; x++) { std::cout << people[x].name << " has floating point value " << people[x].fNum << " and is #" << people[x].iNum << " originally " << people[x].order << std::endl; } } static int GetMin(int a, int b) {return (std::min)(a,b);} static int GetMax(int a, int b, int c) {return (std::max)(a, (std::max)(b,c));} static clock_t TestPeopleSorting(int num_loops) { static const int I_MOD = 5; static const int S_MOD = 7; static const int F_MOD = 3; //// If I make all objects unique (with the code below), then the //// sorts are closer, but std::sort still wins. //static const int I_MOD = NUM_PEOPLE; //static const int S_MOD = NUM_PEOPLE; //static const int F_MOD = NUM_PEOPLE; static const int DATA_MAX = GetMin(NUM_PEOPLE, GetMax(I_MOD, S_MOD, F_MOD)); std::vector<double> fnumbers; std::vector<int> numbers; std::vector<std::string> names; FillData(fnumbers, numbers, names, DATA_MAX); person people[NUM_PEOPLE]; for(int x = 0; x < NUM_PEOPLE; x++) { people[x] = person(x, numbers[x%I_MOD], names[x%S_MOD], fnumbers[x%F_MOD]); } //std::cout << "Before sort:\n"; //PrintPeople(people); std::clock_t start_time = std::clock(); for(int i=0 ; i<num_loops ; ++i) { #if (SORT_TYPE == RADIX_Q_SORT) boost::radix_qsort(people, NUM_PEOPLE-1); // why -1 ??? #elif (SORT_TYPE == RADIX_SORT) boost::radix_sort(people, NUM_PEOPLE); #else // std::sort std::sort(people, people+NUM_PEOPLE); #endif } std::clock_t end_time = std::clock(); //std::cout << "\n\nAfter sort:\n"; //PrintPeople(people); return end_time - start_time; } class radixtest { public: int numbers[2]; #if (SORT_TYPE == RADIX_Q_SORT) static const int STR_SZ = 30; char idstring_qs[STR_SZ]; #endif radixtest() { numbers[0] = rand() % 10; numbers[1] = rand() % 10; #if (SORT_TYPE == RADIX_Q_SORT) //%s means string, %d means int, and %e means double boost::create_id_string("%e%e", idstring_qs, numbers[0], numbers[1]); #endif } inline unsigned char operator[](int num) {return ((unsigned char*)numbers)[num];} inline unsigned char operator[](int num) const {return ((unsigned char*)numbers)[num];} ~radixtest() {} #if ((SORT_TYPE == STD_SORT) || (SORT_TYPE == RADIX_Q_SORT)) bool operator<(const radixtest& a) const { if(numbers[0] < a.numbers[0]) return true; else if(numbers[0] == a.numbers[0]) { if (numbers[1] < a.numbers[1]) return true; } return false; } #endif }; // We want a large number of objects to sort, but we don't // want it to crash if it can't find enough stack space. static const int NUM_RADIX = 15000; static clock_t TestRadixSorting(int num_loops) { radixtest tests[NUM_RADIX]; std::clock_t start_time = std::clock(); for(int i=0 ; i<num_loops ; ++i) { #if (SORT_TYPE == RADIX_Q_SORT) boost::radix_qsort(tests, NUM_RADIX-1); // why -1 ??? #elif (SORT_TYPE == RADIX_SORT) boost::radix_sort(tests, NUM_RADIX, sizeof(int)*2); #else // std::sort std::sort(tests, tests+NUM_RADIX); #endif } std::clock_t end_time = std::clock(); return end_time - start_time; } int main(int argc, char* argv[]) { //clock_t people_sorting = TestPeopleSorting(10); //clock_t radix_sorting = TestRadixSorting(100); clock_t people_sorting = TestPeopleSorting(1); clock_t radix_sorting = TestRadixSorting(1); std::cout << "\nTime for " #if (SORT_TYPE == RADIX_Q_SORT) << "radix_qsort " #elif (SORT_TYPE == RADIX_SORT) << "radix_sort " #else << "std::sort " #endif << "sorting:\n" << "people: " << static_cast<double>(people_sorting) / CLOCKS_PER_SEC << std::endl << "radixtest: " << static_cast<double>(radix_sorting) / CLOCKS_PER_SEC << std::endl; return 0; }