codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <algorithm> #include <iomanip> #include <cstdlib> #ifdef _MSC_VER #include <ctime> class Stopwatch { std::clock_t start; public: Stopwatch() { reset(); } void reset() { start=std::clock(); } double elapsed() { std::clock_t finish=std::clock(); return double(finish-start)/CLOCKS_PER_SEC; } }; #endif //_MSC_VER #ifndef _MSC_VER #include <sys/time.h> class Stopwatch { struct timeval start; static double value(struct timeval& tv) { return tv.tv_sec+(double)tv.tv_usec*1e-6; } public: Stopwatch() { reset(); } void reset() { gettimeofday(&start, NULL); } double elapsed() { struct timeval now; gettimeofday(&now, NULL); return value(now)-value(start); } }; #endif //_MSC_VER using namespace std; template <typename T> void wikipediasort(T* data, int n) { int i, j; T tmp; for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; } } template <typename T> void yaneuraosort(T* t, int MAX) { for (int i = 1; i < MAX; i++) { T tmp = t[i]; if (t[i-1] > tmp) { int j = i; do { t[j] = t[j-1]; --j; } while ( j > 0 && t[j-1] > tmp); t[j] = tmp; } } } int main() { srand(static_cast<unsigned int>(time(0))); Stopwatch sw; cout<<"size\trepetition\tstd\twiki\tyane\ty/w\n"; for (int logsize=2; logsize<=16; ++logsize) { int size=1<<logsize; double* a=new double[size]; for (int i=0; i<size; ++i) a[i]=rand(); int repetition=(1<<(24-logsize))/logsize/logsize; cout<<size<<'\t'<<repetition<<'\t'; sw.reset(); for (int t=0; t<repetition; ++t) { random_shuffle(a, a+size); } double basetime=sw.elapsed(); sw.reset(); for (int t=0; t<repetition; ++t) { random_shuffle(a, a+size); sort(a, a+size); } double sorttime=sw.elapsed()-basetime; cout<<'\t'<<setprecision(4)<<sorttime; sw.reset(); for (int t=0; t<repetition; ++t) { random_shuffle(a, a+size); wikipediasort(a, size); } double wikipediatime=sw.elapsed()-basetime; cout<<'\t'<<setprecision(4)<<wikipediatime; sw.reset(); for (int t=0; t<repetition; ++t) { random_shuffle(a, a+size); yaneuraosort(a, size); } double yaneuraotime=sw.elapsed()-basetime; cout<<'\t'<<setprecision(4)<<yaneuraotime; cout<<'\t'<<setprecision(4)<<yaneuraotime/wikipediatime<<endl; } }
Private
[
?
]
Run code
Submit