|
|
Boost : |
From: David Walthall (walthall_at_[hidden])
Date: 2007-03-21 12:20:05
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;
}
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk