123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328 |
- //----------------------------------------------------------------------------
- /// @file benchmark_numbers.cpp
- /// @brief Benchmark of several sort methods with integer objects
- ///
- /// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n
- /// Distributed under the Boost Software License, Version 1.0.\n
- /// ( See accompanying file LICENSE_1_0.txt or copy at
- /// http://www.boost.org/LICENSE_1_0.txt )
- ///
- /// This program use for comparison purposes, the Threading Building
- /// Blocks which license is the GNU General Public License, version 2
- /// as published by the Free Software Foundation.
- ///
- /// @version 0.1
- ///
- /// @remarks
- //-----------------------------------------------------------------------------
- #include <algorithm>
- #include <iostream>
- #include <iomanip>
- #include <random>
- #include <stdlib.h>
- #include <vector>
- #include <boost/sort/common/time_measure.hpp>
- #include <boost/sort/common/file_vector.hpp>
- #include <boost/sort/common/int_array.hpp>
- #include <boost/sort/sort.hpp>
- #define NELEM 100000000
- using namespace std;
- namespace bsort = boost::sort;
- namespace bsc = boost::sort::common;
- using bsc::time_point;
- using bsc::now;
- using bsc::subtract_time;
- using bsc::fill_vector_uint64;
- using bsc::write_file_uint64;
- using bsort::spinsort;
- using bsort::flat_stable_sort;
- using bsort::spreadsort::spreadsort;
- using bsort::pdqsort;
- void Generator_random (void);
- void Generator_sorted (void);
- void Generator_sorted_end (size_t n_last);
- void Generator_sorted_middle (size_t n_last);
- void Generator_reverse_sorted (void);
- void Generator_reverse_sorted_end (size_t n_last);
- void Generator_reverse_sorted_middle (size_t n_last);
- template<class IA, class compare>
- int Test (std::vector<IA> &B, compare comp = compare ());
- int main (int argc, char *argv[])
- {
- cout << "\n\n";
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << "** B O O S T S O R T **\n";
- cout << "** S I N G L E T H R E A D **\n";
- cout << "** I N T E G E R B E N C H M A R K **\n";
- cout << "** **\n";
- cout << "** SORT OF 100 000 000 NUMBERS OF 64 BITS **\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- cout << std::endl;
- cout<<"[ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort \n";
- cout<<"[ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort\n\n";
- cout<<" | | | | | | |\n";
- cout<<" | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]|\n";
- cout<<"--------------------+------+------+------+------+------+------+\n";
- std::string empty_line =
- " | | | | | | |\n";
- cout<<"random |";
- Generator_random ();
- cout<<empty_line;
- cout<<"sorted |";
- Generator_sorted ();
- cout<<"sorted + 0.1% end |";
- Generator_sorted_end (NELEM / 1000);
- cout<<"sorted + 1% end |";
- Generator_sorted_end (NELEM / 100);
- cout<<"sorted + 10% end |";
- Generator_sorted_end (NELEM / 10);
- cout<<empty_line;
- cout<<"sorted + 0.1% mid |";
- Generator_sorted_middle (NELEM / 1000);
- cout<<"sorted + 1% mid |";
- Generator_sorted_middle (NELEM / 100);
- cout<<"sorted + 10% mid |";
- Generator_sorted_middle (NELEM / 10);
- cout<<empty_line;
- cout<<"reverse sorted |";
- Generator_reverse_sorted ();
- cout<<"rv sorted + 0.1% end|";
- Generator_reverse_sorted_end (NELEM / 1000);
- cout<<"rv sorted + 1% end|";
- Generator_reverse_sorted_end (NELEM / 100);
- cout<<"rv sorted + 10% end|";
- Generator_reverse_sorted_end (NELEM / 10);
- cout<<empty_line;
- cout<<"rv sorted + 0.1% mid|";
- Generator_reverse_sorted_middle (NELEM / 1000);
- cout<<"rv sorted + 1% mid|";
- Generator_reverse_sorted_middle (NELEM / 100);
- cout<<"rv sorted + 10% mid|";
- Generator_reverse_sorted_middle (NELEM / 10);
- cout<<"--------------------+------+------+------+------+------+------+\n";
- cout<<endl<<endl ;
- return 0;
- }
- void
- Generator_random (void)
- {
- vector<uint64_t> A;
- A.reserve (NELEM);
- A.clear ();
- if (fill_vector_uint64 ("input.bin", A, NELEM) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- Test<uint64_t, std::less<uint64_t>> (A);
- }
- ;
- void
- Generator_sorted (void)
- {
- vector<uint64_t> A;
- A.reserve (NELEM);
- A.clear ();
- for (size_t i = 0; i < NELEM; ++i)
- A.push_back (i);
- Test<uint64_t, std::less<uint64_t>> (A);
- }
- void Generator_sorted_end (size_t n_last)
- {
- vector<uint64_t> A;
- A.reserve (NELEM);
- A.clear ();
- if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- std::sort (A.begin (), A.begin () + NELEM);
- Test<uint64_t, std::less<uint64_t>> (A);
- }
- ;
- void Generator_sorted_middle (size_t n_last)
- {
- vector<uint64_t> A, B, C;
- A.reserve (NELEM);
- A.clear ();
- if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- for (size_t i = NELEM; i < A.size (); ++i)
- B.push_back (std::move (A[i]));
- A.resize ( NELEM);
- for (size_t i = 0; i < (NELEM >> 1); ++i)
- std::swap (A[i], A[NELEM - 1 - i]);
- std::sort (A.begin (), A.end ());
- size_t step = NELEM / n_last + 1;
- size_t pos = 0;
- for (size_t i = 0; i < B.size (); ++i, pos += step)
- {
- C.push_back (B[i]);
- for (size_t k = 0; k < step; ++k)
- C.push_back (A[pos + k]);
- };
- while (pos < A.size ())
- C.push_back (A[pos++]);
- A = C;
- Test<uint64_t, std::less<uint64_t>> (A);
- }
- ;
- void Generator_reverse_sorted (void)
- {
- vector<uint64_t> A;
- A.reserve (NELEM);
- A.clear ();
- for (size_t i = NELEM; i > 0; --i)
- A.push_back (i);
- Test<uint64_t, std::less<uint64_t>> (A);
- }
- void Generator_reverse_sorted_end (size_t n_last)
- {
- vector<uint64_t> A;
- A.reserve (NELEM);
- A.clear ();
- if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- std::sort (A.begin (), A.begin () + NELEM);
- for (size_t i = 0; i < (NELEM >> 1); ++i)
- std::swap (A[i], A[NELEM - 1 - i]);
- Test<uint64_t, std::less<uint64_t>> (A);
- }
- void Generator_reverse_sorted_middle (size_t n_last)
- {
- vector<uint64_t> A, B, C;
- A.reserve (NELEM);
- A.clear ();
- if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- for (size_t i = NELEM; i < A.size (); ++i)
- B.push_back (std::move (A[i]));
- A.resize ( NELEM);
- for (size_t i = 0; i < (NELEM >> 1); ++i)
- std::swap (A[i], A[NELEM - 1 - i]);
- std::sort (A.begin (), A.end ());
- size_t step = NELEM / n_last + 1;
- size_t pos = 0;
- for (size_t i = 0; i < B.size (); ++i, pos += step)
- {
- C.push_back (B[i]);
- for (size_t k = 0; k < step; ++k)
- C.push_back (A[pos + k]);
- };
- while (pos < A.size ())
- C.push_back (A[pos++]);
- A = C;
- Test<uint64_t, std::less<uint64_t>> (A);
- };
- template<class IA, class compare>
- int Test (std::vector<IA> &B, compare comp)
- { //---------------------------- begin --------------------------------
- double duration;
- time_point start, finish;
- std::vector<IA> A (B);
- std::vector<double> V;
- //--------------------------------------------------------------------
- A = B;
- start = now ();
- std::sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- pdqsort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- std::stable_sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- spinsort(A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- flat_stable_sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- spreadsort (A.begin (), A.end ());
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- //-----------------------------------------------------------------------
- // printing the vector
- //-----------------------------------------------------------------------
- std::cout<<std::setprecision(2)<<std::fixed;
- for ( uint32_t i =0 ; i < V.size() ; ++i)
- { std::cout<<std::right<<std::setw(5)<<V[i]<<" |";
- };
- std::cout<<std::endl;
- return 0;
- };
|