123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306 |
- //----------------------------------------------------------------------------
- /// @file benchmark_strings.cpp
- /// @brief Benchmark of several sort methods with strings
- ///
- /// @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 NMAXSTRING 10000000
- using namespace std;
- namespace bsc = boost::sort::common;
- namespace bsp = boost::sort;
- using bsc::time_point;
- using bsc::now;
- using bsc::subtract_time;
- 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 P A R A L L E L **\n";
- cout << "** S T R I N G S B E N C H M A R K **\n";
- cout << "** **\n";
- cout << "** S O R T O F 10 000 000 S T R I N G S **\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- cout << std::endl;
- cout<<"[ 1 ] block_indirect_sort [ 2 ] sample_sort\n";
- cout<<"[ 3 ] parallel_stable_sort\n\n";
- cout<<" | | | |\n";
- cout<<" | [ 1 ]| [ 2 ]| [ 3 ]|\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(NMAXSTRING / 1000);
- cout<<"sorted + 1% end |";
- Generator_sorted_end(NMAXSTRING / 100);
- cout<<"sorted + 10% end |";
- Generator_sorted_end(NMAXSTRING / 10);
- cout<<empty_line;
- cout<<"sorted + 0.1% mid |";
- Generator_sorted_middle (NMAXSTRING / 1000);
- cout<<"sorted + 1% mid |";
- Generator_sorted_middle (NMAXSTRING / 100);
- cout<<"sorted + 10% mid |";
- Generator_sorted_middle (NMAXSTRING / 10 );
- cout<<empty_line;
- cout<<"reverse sorted |";
- Generator_reverse_sorted();
- cout<<"rv sorted + 0.1% end|";
- Generator_reverse_sorted_end(NMAXSTRING / 1000);
- cout<<"rv sorted + 1% end|";
- Generator_reverse_sorted_end(NMAXSTRING / 100);
- cout<<"rv sorted + 10% end|";
- Generator_reverse_sorted_end(NMAXSTRING / 10);
- cout<<empty_line;
- cout<<"rv sorted + 0.1% mid|";
- Generator_reverse_sorted_middle(NMAXSTRING / 1000);
- cout<<"rv sorted + 1% mid|";
- Generator_reverse_sorted_middle(NMAXSTRING / 100);
- cout<<"rv sorted + 10% mid|";
- Generator_reverse_sorted_middle(NMAXSTRING / 10);
- cout<< "--------------------+------+------+------+\n";
- cout<<endl<<endl ;
- return 0;
- }
- void Generator_random(void)
- {
- std::vector<std::string> A;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- Test<std::string, std::less<std::string>>(A);
- };
- void Generator_sorted(void)
- {
- std::vector<std::string> A;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- std::sort( A.begin() , A.end() );
- Test<std::string, std::less<std::string>>(A);
- };
- void Generator_sorted_end(size_t n_last)
- {
- std::vector<std::string> A;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING+ n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- std::sort (A.begin() , A.begin() + NMAXSTRING );
- Test<std::string, std::less<std::string>>(A);
- };
- void Generator_sorted_middle(size_t n_last)
- {
- std::vector<std::string> A,B,C;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING + n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- for ( size_t i = NMAXSTRING ; i < A.size() ; ++i)
- B.push_back ( std::move ( A[i]));
- A.resize ( NMAXSTRING);
- std::sort (A.begin() , A.end() );
- size_t step = NMAXSTRING /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<std::string, std::less<std::string>>(A);
- };
- void Generator_reverse_sorted(void)
- {
- std::vector<std::string> A;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- std::sort( A.begin() , A.end());
- size_t nmid = (A.size() >>1), nlast = A.size() -1 ;
- for (size_t i = 0 ; i < nmid ;++i)
- std::swap ( A[i], A [nlast -i]);
- Test<std::string, std::less<std::string>>(A);
- };
- void Generator_reverse_sorted_end(size_t n_last)
- {
- std::vector<std::string> A;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING+ n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- std::sort (A.begin() , A.begin() + NMAXSTRING );
- for ( size_t i =0 ; i< (NMAXSTRING >>1); ++i)
- std::swap ( A[i], A[NMAXSTRING - 1 - i]);
- Test<std::string, std::less<std::string>>(A);
- };
- void Generator_reverse_sorted_middle(size_t n_last)
- {
- std::vector<std::string> A,B,C;
- A.reserve(NMAXSTRING);
- A.clear();
- if (bsc::fill_vector_string("input.bin", A, NMAXSTRING + n_last) != 0)
- {
- std::cout << "Error in the input file\n";
- return;
- };
- for ( size_t i = NMAXSTRING ; i < A.size() ; ++i)
- B.push_back ( std::move ( A[i]));
- A.resize ( NMAXSTRING);
- std::sort (A.begin() , A.end() );
- for ( size_t i =0 ; i< (NMAXSTRING >>1); ++i)
- std::swap ( A[i], A[NMAXSTRING - 1 - i]);
- size_t step = NMAXSTRING /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<std::string, std::less<std::string>>(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 ();
- bsp::block_indirect_sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- bsp::sample_sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- bsp::parallel_stable_sort (A.begin (), A.end (), comp);
- 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;
- };
|