fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <chrono>
  4. #include <algorithm>
  5. #include <boost/sort/sort.hpp>
  6.  
  7. using namespace std;
  8.  
  9. #define LEN 4
  10. #define COUNT 1000000
  11. #define USE_BOOST_SORT
  12.  
  13. // simple structure that i think to be identical to std::string
  14. struct test
  15. {
  16. inline bool operator<(const test& a) const noexcept
  17. {
  18. size_t minsize = len < a.len ? len : a.len;
  19. int res = ::memcmp(ptr, a.ptr, minsize);
  20. return res < 0 || (res == 0 && len < a.len);
  21. }
  22. inline size_t size() const noexcept
  23. {return len;}
  24. inline const char* data() const noexcept
  25. {return ptr;}
  26. inline const char& operator[](size_t index) const noexcept
  27. {return ptr[index];}
  28.  
  29. const char* ptr = nullptr;
  30. size_t len = 0;
  31. };
  32.  
  33.  
  34. int main(int,char**)
  35. {
  36. // stage 1.a - initialize string sorting data with randoms
  37. vector<string> strings;
  38. strings.resize(COUNT);
  39. int counter = 0;
  40. for (string& s : strings)
  41. {
  42. s.resize(LEN);
  43. for (char& c : s)
  44. c = (counter++) % 256;
  45. }
  46. // stage 1.b - make the copy of data to get deterministic results and initialize tests array
  47. vector<string> strings_copy = strings;
  48. vector<test> tests;
  49. tests.resize(strings_copy.size());
  50. for (size_t i = 0; i < tests.size(); ++i)
  51. {
  52. tests[i].ptr = strings_copy[i].data();
  53. tests[i].len = strings_copy[i].size();
  54. }
  55.  
  56. // stage 2. sorting
  57. for (size_t i = 0; i < 10; ++i)
  58. {
  59. // make the copy of data to keep order unchanged
  60. vector<string> to_be_sorted = strings;
  61. chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
  62. #ifdef USE_BOOST_SORT
  63. boost::sort::spreadsort::string_sort(to_be_sorted.begin(), to_be_sorted.end());
  64. #else
  65. sort(to_be_sorted.begin(), to_be_sorted.end());
  66. #endif
  67. chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
  68. to_be_sorted.clear();
  69. // make the copy of tests for sorting
  70. vector<test> tests_for_sort = tests;
  71. chrono::high_resolution_clock::time_point t3 = chrono::high_resolution_clock::now();
  72. #ifdef USE_BOOST_SORT
  73. boost::sort::spreadsort::string_sort(tests_for_sort.begin(), tests_for_sort.end());
  74. #else
  75. sort(tests_for_sort.begin(), tests_for_sort.end());
  76. #endif
  77. chrono::high_resolution_clock::time_point t4 = chrono::high_resolution_clock::now();
  78.  
  79. cout << "String sort time: " << chrono::duration_cast<chrono::milliseconds>(t2-t1).count()
  80. << " msec" << endl;
  81. cout << "Test sort time: " << chrono::duration_cast<chrono::milliseconds>(t4-t3).count()
  82. << " msec" << endl;
  83. }
  84. }
  85.  
Success #stdin #stdout 2.02s 127820KB
stdin
Standard input is empty
stdout
String sort time: 56 msec
Test sort time: 133 msec
String sort time: 51 msec
Test sort time: 130 msec
String sort time: 49 msec
Test sort time: 129 msec
String sort time: 51 msec
Test sort time: 129 msec
String sort time: 49 msec
Test sort time: 129 msec
String sort time: 50 msec
Test sort time: 130 msec
String sort time: 49 msec
Test sort time: 129 msec
String sort time: 50 msec
Test sort time: 130 msec
String sort time: 50 msec
Test sort time: 130 msec
String sort time: 50 msec
Test sort time: 131 msec