fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <set>
  6. #include <x86intrin.h>
  7. #include <iterator>
  8.  
  9.  
  10.  
  11. std::vector<int> arr;
  12. int n2,n1;
  13.  
  14. void reset(int n,int k){//Сбросить, всего элементв и пересекающихся
  15.    n1=n-k;
  16.    n2=n;
  17.    arr.resize(n*2-k);
  18.    for (int i=0;i<arr.size();i++)
  19.       arr[i]=i;
  20.    std::default_random_engine  g(_rdtsc());
  21.    shuffle(arr.begin(),arr.end(),g);
  22. }
  23.  
  24. void prn_a(){  //Начепятать в виде массивов
  25.    printf("\n1: ");
  26.    for (int i=0;i<n1;i++)
  27.       printf("%2d ",arr[i]);
  28.    printf("\n=: ");
  29.    for (int i=n1;i<n2;i++)
  30.       printf("%2d ",arr[i]);
  31.    printf("\n2: ");
  32.    for (int i=n2;i<arr.size();i++)
  33.       printf("%2d ",arr[i]);
  34.  
  35. }
  36.  
  37. double test_1(int k=3){//Стандартный std::set
  38.    uint64_t t=0;
  39.    uint64_t t1,t2;
  40.    std::set<int> c;
  41.    std::set<int> a(arr.data()+0,arr.data()+n2),b(arr.data()+n1,arr.data()+arr.size());
  42.    for (int o=0;o<k;o++){
  43.       //printf("\n1: ");
  44.       // for (auto i:a)
  45.       //    printf("%2d ",i);
  46.       //printf("\n2: ");
  47.       //for (auto i:b)
  48.       //   printf("%2d ",i);
  49.       c.clear();
  50.       t1=_rdtsc();
  51.       set_intersection(a.begin(),a.end(), b.begin(),b.end(), std::inserter(c,c.begin()));
  52.       t2=_rdtsc();
  53.       if (o) t+=(t2-t1);
  54.       if (c.size()!=n2-n1)
  55.          printf("\nerr in &");
  56.  
  57.       // printf("\n&: ");
  58.       // for (auto i:c)
  59.       //   printf("%2d ",i);
  60.       c.clear();
  61.       t1=_rdtsc();
  62.       set_union(a.begin(),a.end(), b.begin(),b.end(), std::inserter(c,c.begin()));
  63.       t2=_rdtsc();
  64.       if (o) t+=(t2-t1);
  65.       if (c.size()!=arr.size())
  66.          printf("\nerr in |");
  67.       //printf("\n|: ");
  68.       //for (auto i:c)
  69.       //  printf("%2d ",i);
  70.  
  71.    }
  72.    return double(t)/(k-1)*2.4e-6;
  73. }
  74. double test_3(int k=3){//Стандартный std::set
  75.    uint64_t t=0;
  76.    uint64_t t1,t2;
  77.    std::set<int> c;
  78.    std::set<int> a(arr.data()+0,arr.data()+n2),b(arr.data()+n1,arr.data()+arr.size());
  79.    for (int o=0;o<k;o++){
  80.       //printf("\n1: ");
  81.       // for (auto i:a)
  82.       //    printf("%2d ",i);
  83.       //printf("\n2: ");
  84.       //for (auto i:b)
  85.       //   printf("%2d ",i);
  86.       c.clear();
  87.       t1=_rdtsc();
  88.       {
  89.          std::vector<int> d;
  90.          set_intersection(a.begin(),a.end(), b.begin(),b.end(), std::back_inserter(d));
  91.          c.insert(d.begin(),d.end());}
  92.       t2=_rdtsc();
  93.       if (o) t+=(t2-t1);
  94.       if (c.size()!=n2-n1)
  95.          printf("\nerr in &");
  96.  
  97.       // printf("\n&: ");
  98.       // for (auto i:c)
  99.       //   printf("%2d ",i);
  100.       c.clear();
  101.       t1=_rdtsc();
  102.       {
  103.          std::vector<int> d;
  104.          set_union(a.begin(),a.end(), b.begin(),b.end(), std::back_inserter(d));
  105.          c.insert(d.begin(),d.end());
  106.       }
  107.       t2=_rdtsc();
  108.       if (o) t+=(t2-t1);
  109.       if (c.size()!=arr.size())
  110.          printf("\nerr in |");
  111.       //printf("\n|: ");
  112.       //for (auto i:c)
  113.       //  printf("%2d ",i);
  114.  
  115.    }
  116.    return double(t)/(k-1)*2.4e-6;
  117. }
  118.  
  119.  
  120. template<typename T>
  121. struct my_tree{
  122.    struct node{
  123.       node *up;//Верхушка
  124.       node *le,*ri;//Ветки
  125.       T zn;
  126.       static node* __(T* a,T* b){
  127.          if (a==b)
  128.             return nullptr;
  129.          node* res=new node;
  130.          T* m=a+(b-a)/2;
  131.          res->zn=*m;
  132.          res->le=__(a,m);
  133.          res->ri=__(m+1,b);
  134.          if (res->le)
  135.             res->le->up=res;
  136.          if (res->ri)
  137.             res->ri->up=res;
  138.          return res;
  139.       }
  140.       node* next(){
  141.          node* h;
  142.          if (ri) {
  143.             h=ri;
  144.             while (h->le) h=h->le;
  145.             return h;
  146.          }else if (up){
  147.             h=up;
  148.             while (h and h->up and h->zn<zn)
  149.                h=h->up;
  150.             return (h->zn<zn)?nullptr:h;
  151.          }else return nullptr;
  152.       }
  153.  
  154.       int size(){
  155.          return 1+(le?le->size():0)+(ri?ri->size():0);
  156.       }
  157.       void prn(){
  158.          if (le) {
  159.             //            printf("(");
  160.             le->prn();
  161.             //            printf(")");
  162.          }
  163.          node* ne=next();
  164.          printf("%d",zn);
  165.          // if (ne)
  166.          //    printf("->%d",ne->zn);
  167.          printf(" ");
  168.          if (ri){
  169.             //            printf("{");
  170.             ri->prn();
  171.             //            printf("}");
  172.          }
  173.       }
  174.    };
  175.    node* core;
  176.  
  177.    my_tree():core(nullptr){}
  178.    my_tree(T* i1,T* i2){
  179.       add(i1,i2);
  180.    }
  181.    void add(T* i1,T* i2){ //Я отсортирую, и потому дерево будет сбалансированное
  182.       core=nullptr;
  183.       std::vector<T> arr(i1,i2);
  184.       sort(arr.begin(),arr.end());
  185.       core=node::__(&*arr.begin(),&*arr.end());
  186.       core->up=nullptr;
  187.    }
  188.    node* begin(){
  189.       node* h=core;
  190.       while (h and h->le) h=h->le;
  191.       return h;
  192.    }
  193.    node* end(){
  194.       node* h=core;
  195.       while (h and h->ri) h=h->ri;
  196.       return h;
  197.    }
  198.    void clear(){
  199.       core=nullptr;//Освобождение памяти не нужно
  200.    }
  201.    int size(){ //Это же лишь тест
  202.       if (core)
  203.          return core->size();
  204.       else
  205.          return 0;
  206.    }
  207.    void prn(){
  208.       printf("\n[ ");
  209.       if (core)
  210.          core->prn();
  211.       printf("]");
  212.    }
  213.    void _intersection( my_tree<T>& a, my_tree<T>& b){
  214.       node *a1=a.begin();
  215.       node *a2=b.begin();
  216.       std::vector<T> c;
  217.       while (a1 and a2){
  218.          //++t;
  219.          // printf("\n a1: %2d  a2: %2d",a1->zn,a2->zn);
  220.          if (a1->zn<a2->zn)
  221.             a1=a1->next();
  222.          else if (a1->zn>a2->zn)
  223.             a2=a2->next();
  224.          else {
  225.             c.push_back(a1->zn);
  226.             //printf(" %d ",a1->zn);
  227.             a1=a1->next();
  228.             a2=a2->next();
  229.          }
  230.  
  231.          // if (t>10)break;
  232.  
  233.       }
  234.       //      printf("{");
  235.       //      for (auto i:c)
  236.       //         printf(" %d ",i);
  237.       //      printf("}");
  238.       core=node::__(&*c.begin(),&*c.end());
  239.       core->up=nullptr;
  240.  
  241.    }
  242.    void _union( my_tree<T>& a, my_tree<T>& b){
  243.       node *a1=a.begin();
  244.       node *a2=b.begin();
  245.       std::vector<T> c;
  246.       while (a1 and a2){
  247.          //++t;
  248.          // printf("\n a1: %2d  a2: %2d",a1->zn,a2->zn);
  249.          if (a1->zn<a2->zn){
  250.             c.push_back(a1->zn);
  251.             a1=a1->next();}
  252.          else if (a1->zn>a2->zn){
  253.             c.push_back(a2->zn);
  254.             a2=a2->next();}
  255.          else {
  256.             c.push_back(a2->zn);
  257.             //printf(" %d ",a1->zn);
  258.             a1=a1->next();
  259.             a2=a2->next();
  260.          }
  261.  
  262.          // if (t>10)break;
  263.  
  264.       }
  265.       while (a1){
  266.          c.push_back(a1->zn);
  267.          a1=a1->next();
  268.       }
  269.       while (a2){
  270.          c.push_back(a2->zn);
  271.          a2=a2->next();
  272.       }
  273.       //      printf("{");
  274.       //      for (auto i:c)
  275.       //         printf(" %d ",i);
  276.       //      printf("}");
  277.       core=node::__(&*c.begin(),&*c.end());
  278.       core->up=nullptr;
  279.  
  280.    }
  281. };
  282.  
  283. double test_2(int k=3){
  284.    uint64_t t=0;
  285.    uint64_t t1,t2;
  286.    //
  287.    my_tree<int> c;
  288.    my_tree<int> a(arr.data()+0,arr.data()+n2),b(arr.data()+n1,arr.data()+arr.size());
  289.    //a.prn();
  290.    //b.prn();
  291.    for (int o=0;o<k;o++){
  292.       //printf("\n1: ");
  293.       // for (auto i:a)
  294.       //    printf("%2d ",i);
  295.       //printf("\n2: ");
  296.       //for (auto i:b)
  297.       //   printf("%2d ",i);
  298.       c.clear();
  299.       t1=_rdtsc();
  300.       c._intersection(a,b);
  301.       t2=_rdtsc();
  302.       //c.prn();
  303.       if (o) t+=(t2-t1);
  304.       if (c.size()!=n2-n1)
  305.          printf("\nerr in &");
  306.  
  307.       // printf("\n&: ");
  308.       // for (auto i:c)
  309.       //   printf("%2d ",i);
  310.       c.clear();
  311.       t1=_rdtsc();
  312.       c._union(a,b);
  313.       t2=_rdtsc();
  314.       //c.prn();
  315.       if (o) t+=(t2-t1);
  316.       if (c.size()!=arr.size())
  317.          printf("\nerr in |");
  318.       //printf("\n|: ");
  319.       //for (auto i:c)
  320.       //  printf("%2d ",i);
  321.  
  322.    }
  323.    return double(t)/(k-1)*2.4e-6;
  324. }
  325.  
  326. void te(double (*fun)(int) ,int i){
  327.  
  328.    reset(2*i,i);
  329.    double t=fun(2),s=1e3*t/i,s2=s/log(i)*4;
  330.    printf("\n%7d : %-12.3f n: %-5.2f   nlog: %-5.2f", i,t,s,s2);
  331. }
  332.  
  333. int main()
  334. {
  335.    reset(6,2);
  336.    prn_a();
  337.    test_2(2);
  338.  
  339.    printf("\n\n my_tree");
  340.    for (int i: {10, 31, 100, 316, 1000, 3162, 10000, 31622, 100000/*, 316227*/})
  341.       te(test_2,i);
  342.    printf("\n\n std::set");
  343.    for (int i: {10, 31, 100, 316, 1000, 3162, 10000, 31622, 100000/*, 316227*/})
  344.       te(test_1,i);
  345.    printf("\n\n std::set with vector");
  346.    for (int i: {10, 31, 100, 316, 1000, 3162, 10000, 31622, 100000/*, 316227*/})
  347.       te(test_3,i);
  348.  
  349.  
  350. }
  351.  
Success #stdin #stdout 1.29s 121952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1:  3  9  1  2 
=:  4  5 
2:  8  0  7  6 

 my_tree
     10 : 0.018        n: 1.81    nlog: 3.15 
     31 : 0.058        n: 1.87    nlog: 2.18 
    100 : 0.203        n: 2.03    nlog: 1.76 
    316 : 0.746        n: 2.36    nlog: 1.64 
   1000 : 2.102        n: 2.10    nlog: 1.22 
   3162 : 6.630        n: 2.10    nlog: 1.04 
  10000 : 21.222       n: 2.12    nlog: 0.92 
  31622 : 66.699       n: 2.11    nlog: 0.81 
 100000 : 214.506      n: 2.15    nlog: 0.75 

 std::set
     10 : 0.029        n: 2.87    nlog: 4.99 
     31 : 0.080        n: 2.59    nlog: 3.01 
    100 : 0.268        n: 2.68    nlog: 2.33 
    316 : 0.913        n: 2.89    nlog: 2.01 
   1000 : 3.030        n: 3.03    nlog: 1.75 
   3162 : 10.697       n: 3.38    nlog: 1.68 
  10000 : 40.776       n: 4.08    nlog: 1.77 
  31622 : 213.206      n: 6.74    nlog: 2.60 
 100000 : 1076.380     n: 10.76   nlog: 3.74 

 std::set with vector
     10 : 0.020        n: 2.02    nlog: 3.51 
     31 : 0.052        n: 1.69    nlog: 1.97 
    100 : 0.296        n: 2.96    nlog: 2.57 
    316 : 0.814        n: 2.58    nlog: 1.79 
   1000 : 2.752        n: 2.75    nlog: 1.59 
   3162 : 9.211        n: 2.91    nlog: 1.45 
  10000 : 31.665       n: 3.17    nlog: 1.38 
  31622 : 159.835      n: 5.05    nlog: 1.95 
 100000 : 632.511      n: 6.33    nlog: 2.20
https://ideone.com/XsREc2
language:
C++14 (clang 8.0)
created:
4 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!