fork download
copy 
  1. #include <iostream>
  2.  
  3. #include <chrono>
  4. #include <random>
  5. #include <list>
  6. #include <deque>
  7. #include <queue>
  8. #include <memory>
  9. #include <algorithm>
  10. #include <set>
  11. #include <queue>
  12.  
  13. using namespace std;
  14.  
  15. /* // Кто ж мать его тестит вставки/удаления/сортировки на малых массивах?
  16. const uint64_t iter = 1000000;
  17. const uint64_t elems = 100;
  18. //*/
  19.  
  20. const uint64_t iter = 10000;
  21. const uint64_t elems = 10000;
  22.  
  23. const std::string s = "qwiuehgflkjasgdfkjasgdfkjhagsdkjf23452345hgaskjhfdgaasdfasdfasdfasdfasdfasdfasdfasdfa234523452345sdfasddkjshdgfkjashgfdkjhgsadfkj";
  24.  
  25. class TimeMeasurer
  26. {
  27. public:
  28.     TimeMeasurer(const std::string &text) :
  29.         _text(text),
  30.         _time(std::chrono::steady_clock::now())
  31.     {}
  32.  
  33.     ~TimeMeasurer() {
  34.         using namespace std::chrono;
  35.         auto t = steady_clock::now();
  36.         // Давайте в миллисекундах, а?
  37.         auto ms = duration_cast<milliseconds>(t - _time).count();
  38.         cout << _text << " " << ms << " ms" << endl;
  39.     }
  40.  
  41. private:
  42.     std::string _text;
  43.     std::chrono::steady_clock::time_point _time;
  44. };
  45.  
  46. struct Ad {
  47.     Ad(const int a, const std::string &s, float b) :
  48.         a(a), s(s), b(b)
  49.     {}
  50.  
  51.     // Не забываем про noexcept
  52.     Ad(const Ad &) = default;
  53.     Ad(Ad &&) noexcept = default;
  54.     Ad &operator = (const Ad &) = default;
  55.     Ad &operator = (Ad &&) noexcept = default;
  56.  
  57.     int a;
  58.     std::string s;
  59.     float b;
  60.     bool operator<(const Ad &a) const {
  61.         return (b < a.b);
  62.     }
  63.     bool operator>(const Ad &a) const {
  64.         return (b > a.b);
  65.     }
  66. };
  67.  
  68. //void list_smart() {
  69. void list_stupid() {
  70.     for (uint64_t i = 0; i < iter; ++i) {
  71.         std::list<std::unique_ptr<Ad>> l;
  72.         for (uint64_t j = 0; j < elems; ++j) {
  73.             l.emplace_back(new Ad(rand(), s, rand()));
  74.         }
  75.         l.sort();
  76.         //l.resize(5);
  77.     }
  78. }
  79.  
  80. void list_smart() {
  81.     for (uint64_t i = 0; i < iter; ++i) {
  82.         std::list<Ad> l;
  83.         for (uint64_t j = 0; j < elems; ++j)
  84.             l.emplace_back(rand(), s, rand());
  85.         l.sort();
  86.         //l.resize(5);
  87.     }
  88. }
  89.  
  90. void vector_smart() {
  91.     for (uint64_t i = 0; i < iter; ++i) {
  92.         std::vector<std::unique_ptr<Ad>> l;
  93.         l.reserve(elems);
  94.         for (uint64_t j = 0; j < elems; ++j) {
  95.             l.emplace_back(new Ad(rand(), s, rand()));
  96.         }
  97.         std::sort(l.begin(), l.end());
  98.         //l.resize(5);
  99.     }
  100. }
  101.  
  102. void deque_smart() {
  103.     for (uint64_t i = 0; i < iter; ++i) {
  104.         std::deque<std::unique_ptr<Ad>> l;
  105.         for (uint64_t j = 0; j < elems; ++j) {
  106.             l.emplace_back(new Ad(rand(), s, rand()));
  107.         }
  108.         std::sort(l.begin(), l.end());
  109.         //l.resize(5);
  110.     }
  111. }
  112.  
  113. void set_stupid() {
  114.     for (uint64_t i = 0; i < iter; ++i) {
  115.         std::set<std::unique_ptr<Ad>> l;
  116.         for (uint64_t j = 0; j < elems; ++j) {
  117.             l.emplace(new Ad(rand(), s, rand()));
  118.         }
  119.         //std::sort(l.begin(), l.end());
  120.         //l.resize(5);
  121.     }
  122. }
  123.  
  124. void set_smart() {
  125.     for (uint64_t i = 0; i < iter; ++i) {
  126.         std::set<Ad> l;
  127.         for (uint64_t j = 0; j < elems; ++j) {
  128.             l.emplace(rand(), s, rand());
  129.         }
  130.         //std::sort(l.begin(), l.end());
  131.         //l.resize(5);
  132.     }
  133. }
  134.  
  135. void pqueue_smart() {
  136.     for (uint64_t i = 0; i < iter; ++i) {
  137.         std::priority_queue<std::unique_ptr<Ad>> l;
  138.         for (uint64_t j = 0; j < elems; ++j) {
  139.             l.emplace(new Ad(rand(), s, rand()));
  140.         }
  141.         //std::sort(l.begin(), l.end());
  142.         //l.resize(5);
  143.     }
  144. }
  145.  
  146. //void list_smart_ins_rm() {
  147. void list_stupid_ins_rm() {
  148.     for (uint64_t i = 0; i < iter; ++i) {
  149.         std::list<std::unique_ptr<Ad>> l;
  150.         for (uint64_t j = 0; j < elems; ++j) {
  151.             l.emplace_back(new Ad(rand(), s, rand()));
  152.         }
  153.         for (uint64_t j = 0; j < 10; ++j) {
  154.             auto rnd = rand() % elems;
  155.             auto it = l.begin();
  156.             std::advance(it, rnd);
  157.             l.erase(it);
  158.             rnd = rand() % (elems-1);
  159.             it = l.begin();
  160.             std::advance(it, rnd);
  161. //            l.insert(it, std::make_unique<Ad>(Ad(rand(), s, rand()))); // Тут копирование, зачем?
  162.             l.insert(it, std::make_unique<Ad>(rand(), s, rand()));
  163.         }
  164.     }
  165. }
  166.  
  167. void list_smart_ins_rm() {
  168.     for (uint64_t i = 0; i < iter; ++i) {
  169.         std::list<Ad> l;
  170.         for (uint64_t i = 0; i < elems; ++i) {
  171.             l.emplace_back(rand(), s, rand());
  172.         }
  173.         for (uint64_t j = 0; j < 10; ++j) {
  174.             auto rnd = rand() % elems;
  175.             auto it = l.begin();
  176.             std::advance(it, rnd);
  177.             l.erase(it);
  178.             rnd = rand() % (elems-1);
  179.             it = l.begin();
  180.             std::advance(it, rnd);
  181.             l.emplace(it, rand(), s, rand());
  182.         }
  183.     }
  184. }
  185.  
  186. void vector_ins_rm() {
  187.     for (uint64_t i = 0; i < iter; ++i) {
  188.         std::vector<std::unique_ptr<Ad>> l;
  189.         l.reserve(elems);
  190.         for (uint64_t j = 0; j < elems; ++j) {
  191.             l.emplace_back(new Ad(rand(), s, rand()));
  192.         }
  193.         for (uint64_t j = 0; j < 10; ++j) {
  194.             auto rnd = rand() % elems;
  195.             l.erase(l.begin() + rnd);
  196.             rnd = rand() % (elems-1);
  197. //            l.insert(l.begin() + rnd, std::make_unique<Ad>(Ad(rand(), s, rand()))); // Тут тоже. WTF?
  198.             l.insert(l.begin() + rnd, std::make_unique<Ad>(rand(), s, rand()));
  199.         }
  200.     }
  201. }
  202.  
  203. int main() {
  204.     {
  205.         TimeMeasurer _{"list<unique_ptr<T>>"};
  206.         list_stupid();
  207.     }
  208.     {
  209.         TimeMeasurer _{"list<T>"};
  210.         list_smart();
  211.     }
  212.     {
  213.         TimeMeasurer _{"vector"};
  214.         vector_smart();
  215.     }
  216.     {
  217.         TimeMeasurer _{"deque"};
  218.         deque_smart();
  219.     }
  220.     {
  221.         TimeMeasurer _{"set<unique_ptr<T>>"};
  222.         set_stupid();
  223.     }
  224.     {
  225.         TimeMeasurer _{"set<T>"};
  226.         set_smart();
  227.     }
  228.     {
  229.         TimeMeasurer _{"priority_queue"};
  230.         pqueue_smart();
  231.     }
  232.     {
  233.         TimeMeasurer _{"list<unique_ptr<T>> ins/rm"};
  234.         list_stupid_ins_rm();
  235.     }
  236.     {
  237.         TimeMeasurer _{"list<T> ins/rm"};
  238.         list_smart_ins_rm();
  239.     }
  240.     {
  241.         TimeMeasurer _{"vector ins/rm"};
  242.         vector_ins_rm();
  243.     }
  244.     std::cout << "finished" << std::endl;
  245. }
Time limit exceeded #stdin #stdout 5s 5228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b63kkI
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!