fork(1) download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <time.h>
  4. #include <wchar.h>
  5. #include <chrono>
  6. #include <thread>
  7. #include <vector>
  8. #include <array>
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12.  
  13. using namespace std;
  14.  
  15. namespace me{
  16.  
  17.    using tint = unsigned long;//ideone жалуется на tint
  18.    using nint = long long;
  19.  
  20.    template <typename K,typename T,typename _hash= std::hash<K>>
  21.    struct unordered_map{
  22.       tint *data;//Вся информация
  23.  
  24.       struct key{
  25.          K first;
  26.          T second;
  27.          tint next;
  28.       };
  29.       key *pi;//Полезная информация
  30.       tint clv=0;// количество
  31.  
  32.       tint buck;
  33.       tint size;
  34.  
  35.       void resize(tint n){
  36.          size=n;
  37.          data=(decltype(data))realloc(data,n);
  38.          pi=(key*)(nint((void*)data)+sizeof(tint)*buck)-1;
  39.  
  40.       }
  41.  
  42.       unordered_map(int a):buck(a),data(nullptr){
  43.          //  data=malloc();
  44.          resize(sizeof(tint)*buck+buck*sizeof(key)/2);
  45.          for (tint i=0;i<buck;i++)
  46.             ((tint*)data)[i]=0;
  47.       }
  48.       unordered_map():unordered_map(4){}
  49.  
  50.  
  51.  
  52.       tint hash(K& a)const{
  53.          // return 0;
  54.          return _hash()(a)%buck;
  55.       }
  56.       void insert(std::pair<K,T> a){
  57.  
  58.          if (size<sizeof(tint)*buck+sizeof(key)*(5+clv))
  59.             resize(size*2);
  60.          tint y=hash(a.first);
  61.          //  wprintf(L"insert pair %f [hash=%d] %d ------------\n",*(float*)a.first.p,y,a.second);
  62.          //   prn();
  63.          tint* w=&data[y];
  64.          //  wprintf(L"]]");
  65.          //   wprintf(L":%d:",*w);
  66.          while (*w){
  67.             //pi[w]
  68.             w=&pi[*w].next;
  69.             //   wprintf(L":%d:",*w);
  70.          }
  71.          //    wprintf(L"[[===========\n");
  72.  
  73.  
  74.  
  75.          clv++;
  76.          key* me=&pi[clv];
  77.          me->first=a.first;
  78.          me->second=a.second;
  79.          me->next=0;
  80.          *w=clv;
  81.  
  82.       }
  83.  
  84.       key* find(K a){
  85.          tint y=hash(a);
  86.          tint* w=&data[y];
  87.          while (*w){
  88.             //pi[w]
  89.             if (pi[*w].first==a){
  90.                return &pi[*w];
  91.             }
  92.             w=&pi[*w].next;
  93.          }
  94.          return nullptr;
  95.       }
  96.  
  97.  
  98.       ~unordered_map(){
  99.          free(data);
  100.       }
  101.  
  102.  
  103.  
  104.  
  105.    };
  106.  
  107.    inline nint rdtsc()
  108.    {
  109.       static tint lo, hi;
  110.       asm volatile("rdtsc\n"
  111.                    : "=a"(lo), "=d"(hi));
  112.       return ((nint)hi << 32) | lo;
  113.    }
  114.  
  115. }
  116.  
  117. double hz;
  118.  
  119. void test(me::tint N,me::tint seed){
  120.  
  121.    wprintf(L"\n\n     N: %d    seed: %d\n",N,seed);
  122.    using namespace me;
  123.    tint c1,c2;
  124.    nint t1,t2;
  125.    struct mm{  //Какая-то временная структура
  126.       int n;//а тут их количество
  127.       float* p;//Вот тут лежат флоаты
  128.       size_t operator()(const mm& a) const{
  129.          size_t t=1231231;
  130.  
  131.          for (int i=0;i<a.n;i++)
  132.             t^=std::hash<float>()(a.p[i])<<i;
  133.          return t;
  134.       };
  135.       bool operator ==(const mm& a)const {
  136.          if (a.n!=n)return false;
  137.          for (int i=0;i<n;i++)
  138.             if (a.p[i]!=p[i])
  139.                return false;
  140.          return true;
  141.  
  142.       }
  143.    };
  144.  
  145.  
  146.  
  147.    std::vector<std::array<float,8>> ms{N};
  148.    srand(seed);
  149.    for (int i=0;i<N;i++){
  150.       ms[i][0]=rand()%(N/2);
  151.       for (int t=1;t<ms[i].size();t++)
  152.          ms[i][t]=0;
  153.    }
  154.  
  155.    std::vector<mm> arr{N};
  156.  
  157.    for (int i=0;i<N;i++){
  158.       arr[i].n=8;
  159.       arr[i].p=(decltype(arr[i].p))(&ms[i]);
  160.    }
  161.  
  162.  
  163.    double e1,m1,e2,m2;
  164.  
  165.    std::vector<tint> ind(N);//Здесь индексы
  166.    std::vector<float> ver(sizeof(float)*8*N);//Здесь вершины
  167.    int j;//Количество добавленных
  168.  
  169.    auto std=[&]
  170.    {
  171.       j=0;
  172.       c1=clock();t1=rdtsc();
  173.       std::unordered_map<mm,tint,mm> kk(N);
  174.       for (int i=0;i<N;i++)
  175.       {
  176.  
  177.          auto r=kk.find(arr[i]);
  178.          if (r==kk.cend()){//Если такого ещё нет
  179.             memcpy(&ver[j*8],arr[i].p,sizeof(float)*8);
  180.             ind[i]=j;
  181.             kk.insert({arr[i],j});
  182.             j++;
  183.          }
  184.          else
  185.          {
  186.             ind[i]=r->second;//kk[aa[i]];  }
  187.          }
  188.  
  189.       }
  190.       c2=clock();t2=rdtsc();
  191.       wprintf(L"N: %d    j: %d\n",N,j);
  192.       wprintf(L"std | %d ms [%.2f] :  %lldk\n",c2-c1,(t2-t1)/hz,t2-t1);
  193.       m1=c2-c1;
  194.       e1=t2-t1;
  195.    };
  196.  
  197.  
  198.  
  199.  
  200.    auto me=[&]
  201.    {
  202.       j=0;
  203.       c1=clock();t1=rdtsc();
  204.       me::unordered_map<mm,tint,mm> kk(N);
  205.       for (int i=0;i<N;i++)
  206.       {
  207.  
  208.          // kk.prn();
  209.          auto r=kk.find(arr[i]);
  210.          if (r==nullptr){//Если такого ещё нет
  211.             memcpy(&ver[j*8],arr[i].p,sizeof(float)*8);
  212.             ind[i]=j;
  213.             kk.insert({arr[i],j});
  214.             j++;
  215.          }
  216.          else
  217.          {
  218.             ind[i]=r->second;//kk[aa[i]];  }
  219.          }
  220.          // wprintf(L"\n");
  221.       }
  222.       c2=clock();t2=rdtsc();
  223.       wprintf(L"N: %d    j: %d\n ",N,j);
  224.       wprintf(L"me | %d ms [%.2f] :  %lldk\n",c2-c1,(t2-t1)/hz,t2-t1);
  225.       m2=c2-c1;
  226.       e2=t2-t1;
  227.    };
  228.  
  229.  
  230.    std();
  231.    me();
  232.    wprintf(L"                                       %.2f%%  %.2f%%\n",100.0*m1/m2,100.0*e1/e2);
  233.    me();
  234.    std();
  235.    wprintf(L"                                       %.2f%%  %.2f%%\n",100.0*m1/m2,100.0*e1/e2);
  236.  
  237.  
  238. }
  239.  
  240. int main()
  241. {
  242.    using namespace me;
  243.  
  244.    tint c1=clock();
  245.    nint t1=me::rdtsc();
  246.    std::this_thread::sleep_for(std::chrono::milliseconds(100));
  247.    tint c2=clock();
  248.    nint t2=me::rdtsc();
  249.    hz=double(t2-t1)/(c2-c1);
  250.    wprintf(L"khz: %.2f\n",hz);
  251.  
  252.    test(1000000,123);
  253.    test(1000,52);
  254.    test(10,76);
  255.  
  256.  
  257. }
  258.  
Success #stdin #stdout 1.14s 224500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
khz: 50028719.00


     N: 1000000    seed: 123
N: 1000000    j: 432565
std | 275382 ms [19.30] :  965670426k
N: 1000000    j: 432565
 me | 242751 ms [17.01] :  851191018k
                                       113.44%  113.45%
N: 1000000    j: 432565
 me | 241049 ms [16.91] :  846005536k
N: 1000000    j: 432565
std | 278237 ms [19.51] :  976246676k
                                       115.43%  115.39%


     N: 1000    seed: 52
N: 1000    j: 414
std | 65 ms [0.00] :  235695k
N: 1000    j: 414
 me | 49 ms [0.00] :  172272k
                                       132.65%  136.82%
N: 1000    j: 414
 me | 47 ms [0.00] :  163571k
N: 1000    j: 414
std | 60 ms [0.00] :  210643k
                                       127.66%  128.78%


     N: 10    seed: 76
N: 10    j: 4
std | 1 ms [0.00] :  3300k
N: 10    j: 4
 me | 1 ms [0.00] :  5296k
                                       100.00%  62.31%
N: 10    j: 4
 me | 1 ms [0.00] :  2883k
N: 10    j: 4
std | 1 ms [0.00] :  2976k
                                       100.00%  103.23%
https://ideone.com/v6xbhx
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!