summaryrefslogtreecommitdiff
path: root/main.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'main.cpp')
-rw-r--r--main.cpp285
1 files changed, 106 insertions, 179 deletions
diff --git a/main.cpp b/main.cpp
index 2546a8e..08a4368 100644
--- a/main.cpp
+++ b/main.cpp
@@ -1,126 +1,14 @@
#include <iostream>
-#include <cstdlib>
#include <random>
#include <cstring>
#include <ctime>
+#include <algorithm>
+#include "mqsort.h"
template<typename T>
-inline void swap(T &a, T &b) {
- T t = a;
- a = b;
- b = t;
-}
-
-template<typename T>
-inline void insert(T *l, T *r, int (*compar)(const void*, const void*)) {
- T* s = l;
- while (s<r) {
- T* k = s+1;
- while (k > l && compar(k,k-1) < 0) {
- swap(*k, *(k-1));
- --k;
- }
- ++s;
- }
-}
-
-#define INS 12
-
-template<typename T>
-void secret1(T *l, T *r, int (*compar)(const void*, const void*)) {
- T *j = r;
- T *i = l+1;
- {
- int a = compar(l, l+1), b= compar(l,l+2), c = compar(l+1,l+2);
- if (a > 0) {
- if (b > 0)
- if (c<0) swap(*l,l[2]);
- else swap(*l,l[1]);
- } else if (a < 0) {
- if (b < 0)
- if (c<0) swap(*l,l[1]);
- else swap(*l,l[2]);
- }
- }
- while (i <= j) {
- int a = compar(l,i);
- if (a <= 0) {
- int b = 0;
- while (j > l && (b = compar(l,j)) < 0)
- --j;
- if (j > i) {
- if (a != b) {
- swap(*j, *i);
- --j;
- } else {
- --i; --j;
- }
- } else break;
- } else {
- ++i;
- }
- }
- swap(*l, *j);
- --j;
- //std::cout<< j-l <<" " << r-i << std::endl;
- if (l+INS < j)
- secret1(l,j, compar);
- else
- insert(l,j,compar);
- if (i+INS < r)
- secret1(i,r, compar);
- else
- insert(i,r,compar);
-}
-
-inline void swapsize(char *a,char *b, size_t size) {
- for (int cnt = 0; cnt < size; ++cnt)
- swap<char>(a[cnt],b[cnt]);
-}
-
-void secret(char *l, char *r, size_t size,int (*compar)(const void*, const void*)) {
- char *j = r;
- char *i = l+size;
- while (i <= j) {
- if (compar(l,i) < 0) {
- swapsize(j, i, size);
- j -= size;
- } else {
- i += size;
- }
- }
- swapsize(l, j, size);
- j -= size;
- if (l < j)
- secret1(l, j, compar);
- if (i < r)
- secret1(i, r, compar);
-
-}
-
-void mqsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*)) {
- switch (size) {
- case 1:
- secret1((uint8_t*)base, (uint8_t*)base+(num-1), compar);
- break;
- case 2:
- secret1((uint16_t *)base, (uint16_t *)base+(num-1), compar);
- break;
- case 4:
- secret1((uint32_t *)base, (uint32_t*)base+(num-1), compar);
- break;
- case 8:
- secret1((uint64_t *)base, (uint64_t *)base+(num-1), compar);
- break;
- default:
- secret((char*)base, (char*)base+(num-1)*size, size, compar);
- }
-}
-
-template<typename T>
-int compr(const void * a, const void * b){
- T aa = *(T*)a;
- T bb = *(T*)b;
+int compr(const void *a, const void *b) {
+ T aa = *(T *) a;
+ T bb = *(T *) b;
if (aa > bb)
return 1;
if (aa < bb)
@@ -129,118 +17,157 @@ int compr(const void * a, const void * b){
}
template<typename T>
-void* genInt(size_t num) {
+void genInt(void *base, size_t num) {
std::random_device r;
std::mt19937_64 e(r());
- std::uniform_int_distribution<T> unifrom_dist(0, 1 << (sizeof(T)*8 -2));
- T * res = (T*)malloc(num * sizeof(T));
- for (size_t i = 0; i<num; ++i)
+ std::uniform_int_distribution<T> unifrom_dist(0, (T) 1 << (sizeof(T) * 8 - 2));
+ T *res = (T *) base;
+ for (size_t i = 0; i < num; ++i)
res[i] = unifrom_dist(e);
- return res;
}
template<typename T>
-void* genFloat(size_t num) {
+void genFloat(void *base, size_t num) {
std::random_device r;
std::mt19937_64 e(r());
std::uniform_real_distribution<T> unifrom_dist(0, 1);
- T * res = (T*)malloc(num * sizeof(T));
- for (size_t i = 0; i<num; ++i)
+ T *res = (T *) base;
+ for (size_t i = 0; i < num; ++i)
res[i] = unifrom_dist(e);
- return res;
}
template<typename T>
-void* gen(size_t num) {
- return genInt<T>(num);
+void gen(void *base, size_t num) {
+ genInt<T>(base, num);
}
-template <>
-void* gen<float>(size_t num) {
- return genFloat<float>(num);
+template<>
+void gen<float>(void *base, size_t num) {
+ genFloat<float>(base, num);
}
-template <>
-void* gen<double>(size_t num) {
- return genFloat<double>(num);
+template<>
+void gen<double>(void *base, size_t num) {
+ genFloat<double>(base, num);
}
-int compeq(uint32_t *a,uint32_t *b, size_t size) {
- for (size_t i = 0; i< size; ++i)
+int compeq(uint32_t *a, uint32_t *b, size_t size) {
+ for (size_t i = 0; i < size; ++i)
if (a[i] != b[i])
return 1;
return 0;
}
template<typename T>
-void print(void *v, size_t num) {
- T * k = (T*) v;
- for (int i = 0; i<num; ++i)
- std::cout<< k[i] << " ";
- std::cout<<std::endl;
-}
-
-template<typename T>
-void runAndTest(size_t num) {
+void runAndTest(size_t num, size_t it) {
clock_t tst;
clock_t tmd;
clock_t ted;
+ std::vector<clock_t> mine, stnd;
size_t size = sizeof(T);
- void *base = gen<T>(num);
- void *base2 = malloc(num*size);
- memcpy(base2,base,num*size);
- tst = clock();
- mqsort(base,num,size,compr<T>);
- tmd = clock();
- qsort(base2,num,size,compr<T>);
- ted = clock();
- if (compeq((uint32_t*)base,(uint32_t*)base2,num*size/4)) {
- std::cout << "Not equal" << std::endl;
- print<T>(base, num);
- print<T>(base2,num);
+ void *base = malloc(num * size);
+ void *base2 = malloc(num * size);
+ for (size_t t = 0; t < it; ++t) {
+ gen<T>(base, num);
+ memcpy(base2, base, num * size);
+ tst = clock();
+ mqsort(base, num, size, compr<T>);
+ tmd = clock();
+ qsort(base2, num, size, compr<T>);
+ ted = clock();
+ if (compeq((uint32_t *) base, (uint32_t *) base2, num * size / 4)) {
+ std::cout << "Not equal" << std::endl;
+ return;
+ }
+ mine.push_back(tmd - tst);
+ stnd.push_back(ted - tmd);
}
- else
- std::cout<<"Equal"<<std::endl;
- std::cout<<"Time taken for me : " << float(tmd - tst) / CLOCKS_PER_SEC<<std::endl;
- std::cout<<"Time taken for std : " << float(ted - tmd) / CLOCKS_PER_SEC<<std::endl;
+ free(base);
+ free(base2);
+ std::sort(mine.begin(), mine.end());
+ std::sort(stnd.begin(), stnd.end());
+ double m = 0, s = 0;
+ for (auto itt = mine.begin(); itt < mine.end(); ++itt)
+ m += *itt;
+ for (auto itt = stnd.begin(); itt < stnd.end(); ++itt)
+ s += *itt;
+ std::cout << "Average time taken for me (s): " << m / CLOCKS_PER_SEC / it << std::endl;
+ std::cout << "Average time taken for std (s): " << s / CLOCKS_PER_SEC / it << std::endl;
+ std::cout << "Speedup over std : " << s / m << std::endl;
+ if (it & 1) {
+ m = mine[it >> 1];
+ s = stnd[it >> 1];
+ } else {
+ m = mine[it >> 1];
+ m += mine[(it >> 1) - 1];
+ m /= 2;
+ s = stnd[it >> 1];
+ s += stnd[(it >> 1) - 1];
+ s /= 2;
+ }
+ std::cout << "Median time taken for me (s): " << m / CLOCKS_PER_SEC << std::endl;
+ std::cout << "Median time taken for std (s): " << s / CLOCKS_PER_SEC << std::endl;
+ std::cout << "Speedup over std : " << s / m << std::endl;
}
void usage() {
- std::cout << "Usage: <this> [TYPE] [LENGTH]" <<std::endl;
- std::cout << " [TYPE]" <<std::endl;
- std::cout << " i : int" <<std::endl;
- std::cout << " l : long" <<std::endl;
- std::cout << " f : float" <<std::endl;
- std::cout << " d : double" <<std::endl;
- std::cout << " [LENGTH]" <<std::endl;
- std::cout << " An int specify the number of elements in the list to be sorted" <<std::endl;
-}
-
-int main(int argc,char** argv) {
- if (argc < 3) {
+ std::cout << "Usage: <this> [TYPE] [LENGTH]" << std::endl;
+ std::cout << " [TYPE]" << std::endl;
+ std::cout << " c : char(int8)" << std::endl;
+ std::cout << " s : short(int16)" << std::endl;
+ std::cout << " i : int" << std::endl;
+ std::cout << " l : long" << std::endl;
+ std::cout << " f : float" << std::endl;
+ std::cout << " d : double" << std::endl;
+ std::cout << " [LENGTH]" << std::endl;
+ std::cout << " An int specify the number of elements in the list to be sorted" << std::endl;
+ std::cout << " [ITERATIONS]" << std::endl;
+ std::cout << " An int specify the number of iterations of test" << std::endl;
+}
+
+int main(int argc, char **argv) {
+ if (argc < 4) {
usage();
return -1;
}
size_t num;
+ size_t it;
try {
- num = (size_t)std::stoi(argv[2]);
+ num = (size_t) std::stoi(argv[2]);
+ if (num > 10000000)
+ std::cout << "The [LENGTH] seems to be too large" << std::endl;
+ it = (size_t) std::stoi(argv[3]);
+ if (it > 10000000)
+ std::cout << "The [ITERATIONS] seems to be too large" << std::endl;
} catch (std::exception &e) {
std::cout << e.what() << std::endl;
usage();
return -1;
}
- switch(argv[1][0]) {
+ switch (argv[1][0]) {
+ case 'c':
+ std::cout<<num<<" Char for "<<it<<" Iterations"<<std::endl;
+ runAndTest<int8_t>(num, it);
+ break;
+ case 's':
+ std::cout<<num<<" Short for "<<it<<" Iterations"<<std::endl;
+ runAndTest<int16_t>(num, it);
+ break;
case 'i':
- runAndTest<int>(num);
+ std::cout<<num<<" Int for "<<it<<" Iterations"<<std::endl;
+ runAndTest<int>(num, it);
break;
case 'l':
- runAndTest<long>(num);
+ std::cout<<num<<" Long for "<<it<<" Iterations"<<std::endl;
+ runAndTest<long>(num, it);
break;
case 'f':
- runAndTest<float>(num);
+ std::cout<<num<<" Float for "<<it<<" Iterations"<<std::endl;
+ runAndTest<float>(num, it);
break;
case 'd':
- runAndTest<double>(num);
+ std::cout<<num<<" Double for "<<it<<" Iterations"<<std::endl;
+ runAndTest<double>(num, it);
break;
default:
usage();
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2025-02-01 19:05:48 +0000