fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdint.h>
  4. #include <string.h>
  5. #include <limits.h>
  6. #include <time.h>
  7.  
  8. #include <iostream>
  9. #include <bitset>
  10. #include <vector>
  11.  
  12. using namespace std;
  13.  
  14. unsigned int myrand(){
  15.    return (rand()<<16) + rand();
  16. }
  17.  
  18. int main ()
  19. {
  20.   const int n = 1000000;
  21.   bitset<n> bcp;
  22.   printf("bcp %d\n", (int)sizeof(bcp));
  23.  
  24.   unsigned long ebits,
  25.     sz = (n + sizeof(unsigned long) * CHAR_BIT - 1) / (ebits = (sizeof(unsigned long) * CHAR_BIT)),
  26.     bc[sz], bysz = sizeof(bc);
  27.   printf("bc  sz = %d ebits = %d bysz = %d\n",
  28.          (int)(sz), (int)ebits, (int)bysz);
  29.  
  30.   clock_t s, e;
  31.   int nn = 0;
  32.  
  33.   s = clock();
  34.   srand(9);
  35.   for (int r = 0; r < 50; r++) {
  36.     bcp.reset();
  37.     for (int i = 0; i < n; i++)
  38.       bcp.set(myrand() % n);
  39.     for (int i = 0; i < n; i++)
  40.       if (bcp.test(i))
  41.         nn++;
  42.   }
  43.   e = clock();
  44.   cout << "nn = " << nn << " t = " << e - s << '\n';
  45.  
  46.   nn = 0;
  47.   s = clock();
  48.   srand(9);
  49.   for (int r = 0; r < 50; r++) {
  50.     memset(bc, 0, bysz);
  51.  
  52.     for (int i = 0; i < n; i++) {
  53.       int bi = myrand() % n;
  54.       bc[bi / ebits] |= (1UL << (bi % ebits));
  55.     }
  56.     for (int i = 0; i < n; i++) {
  57.       if (bc[i / ebits] & (1UL << (i % ebits)))
  58.         nn++;
  59.     }
  60.   }
  61.   e = clock();
  62.   cout << "nn = " << nn << " t = " << e - s << '\n';
  63.  
  64.  
  65.   vector<bool> vv;
  66.   vv.resize(n);
  67.   s = clock();
  68.   srand(9);
  69.   nn = 0;
  70.   for (int r = 0; r < 50; r++) {
  71.     vv.clear();
  72.  
  73.     for (int i = 0; i < n; i++) {
  74.       int bi = myrand() % n;
  75.       vv[bi] = 1;
  76.     }
  77.     for (int i = 0; i < n; i++) {
  78.       if (vv[i])
  79.         nn++;
  80.     }
  81.   }
  82.   e = clock();
  83.   cout << "nn = " << nn << " t = " << e - s << '\n';
  84. }
  85.  
Success #stdin #stdout 3.94s 3592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bcp 125000
bc  sz = 31250 ebits = 32 bysz = 125000
nn = 31603027 t = 1318571
nn = 31603027 t = 1323992
nn = 49419136 t = 1287675
https://ideone.com/uO4VPN
language:
C++14 (gcc 8.3)
created:
9 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!