fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <list>
  5. #include <cstdint>
  6. #include <cstdlib>
  7. #include <ctime>
  8.  
  9. using namespace std;
  10.  
  11. const int TotalVectorCount = 1000000;
  12. const int UniqueVectorCount = 10;//30000;
  13. const int VectorLength = 10;//30;
  14.  
  15. typedef vector<int> Vector;
  16.  
  17. typedef unsigned long long uint64;
  18.  
  19. void GenerateRandomVector(Vector& v)
  20. {
  21.   v.reserve(VectorLength);
  22.   // generate 30 values from -100 to +100
  23.   for (int i = 0; i < VectorLength; i++)
  24.     v.push_back(rand() % 201 - 100);
  25. }
  26.  
  27. bool IdenticalVectors(const Vector& v1, const Vector& v2)
  28. {
  29.   for (int i = 0; i < VectorLength; i++)
  30.     if (v1[i] != v2[i])
  31.       return false;
  32.  
  33.   return true;
  34. }
  35.  
  36. // this lets us do "cout << Vector"
  37. ostream& operator<<(ostream& os, const Vector& v)
  38. {
  39.   for (int i = 0; i < VectorLength; i++)
  40.     os << v[i] << ' ';
  41.  
  42.   return os;
  43. }
  44.  
  45. uint64 HashVector(const Vector& v)
  46. {
  47.   // this is probably a bad hash function,
  48.   // but it seems to work nonetheless
  49.   uint64 h = 0x7FFFFFFFFFFFFFE7;
  50.   for (int i = 0; i < VectorLength; i++)
  51.     h = h * 0xFFFFFFFFFFFFFFC5 + v[i];
  52.   return h & 0xFFFFFFFFFFFFFFFF;
  53. }
  54.  
  55. Vector UniqueTestVectors[UniqueVectorCount];
  56.  
  57. void GenerateUniqueTestVectors()
  58. {
  59.   map<uint64,char> m;
  60.   for (int i = 0; i < UniqueVectorCount; i++)
  61.   {
  62.     for (;;)
  63.     {
  64.       GenerateRandomVector(UniqueTestVectors[i]);
  65.       uint64 h = HashVector(UniqueTestVectors[i]);
  66.  
  67.       map<uint64,char>::iterator it = m.find(h);
  68.  
  69.       if (it == m.end())
  70.       {
  71.         m[h] = 0;
  72.         break;
  73.       }
  74.     }
  75.   }
  76. }
  77.  
  78. bool GetNextVector(Vector& v)
  79. {
  80.   static int count = 0;
  81.   v = UniqueTestVectors[count % UniqueVectorCount];
  82.   return ++count <= TotalVectorCount;
  83. }
  84.  
  85. int main()
  86. {
  87.   srand(time(0));
  88.  
  89.   cout << "Generating " << UniqueVectorCount << " unique random vectors..."
  90.        << endl;
  91.   GenerateUniqueTestVectors();
  92.  
  93. #if 01
  94.   for (int i = 0; i < UniqueVectorCount; i++)
  95.     cout << UniqueTestVectors[i] << endl;
  96. #endif
  97.  
  98.   cout << "Generating " << TotalVectorCount << " random vectors with only "
  99.        << UniqueVectorCount << " unique..." << endl;
  100.  
  101.   map<uint64,list<Vector>> TheBigHashTable;
  102.  
  103.   int uniqCnt = 0;
  104.   int totCnt = 0;
  105.  
  106.   Vector v;
  107.   while (GetNextVector(v))
  108.   {
  109.     totCnt++;
  110.  
  111.     uint64 h = HashVector(v);
  112.  
  113.     map<uint64,list<Vector>>::iterator it = TheBigHashTable.find(h);
  114.  
  115.     if (it == TheBigHashTable.end())
  116.     {
  117.       // seeing vector with this hash (h) for the first time,
  118.       // insert it into the hash table
  119.       list<Vector> l;
  120.       l.push_back(v);
  121.  
  122.       TheBigHashTable[h] = l;
  123.       uniqCnt++;
  124.     }
  125.     else
  126.     {
  127.       // we've seen vectors with this hash (h) before,
  128.       // let's see if we've already hashed this vector
  129.       list<Vector>::iterator it;
  130.       bool exists = false;
  131.  
  132.       for (it = TheBigHashTable[h].begin();
  133.            it != TheBigHashTable[h].end();
  134.            it++)
  135.       {
  136.         if (IdenticalVectors(*it, v))
  137.         {
  138.           // we've hashed this vector before
  139.           exists = true;
  140.           break;
  141.         }
  142.       }
  143.  
  144.       if (!exists)
  145.       {
  146.         // we haven't hashed this vector before,
  147.         // let's do it now
  148.         TheBigHashTable[h].push_back(v);
  149.         uniqCnt++;
  150.       }
  151.     }
  152.   }
  153.  
  154. #if 01
  155.   cout << "Unique vectors found:" << endl;
  156.   map<uint64,list<Vector>>::iterator it;
  157.   for (it = TheBigHashTable.begin();
  158.        it != TheBigHashTable.end();
  159.        it++)
  160.   {
  161.     list<Vector>::iterator it2;
  162.     for (it2 = it->second.begin();
  163.          it2 != it->second.end();
  164.          it2++)
  165.       cout << *it2 << endl;
  166.   }
  167. #endif
  168.  
  169.   cout << "Hashed " << uniqCnt << " unique vectors out of " << totCnt << " total" << endl;
  170.  
  171.   return 0;
  172. }
  173.  
Success #stdin #stdout 0.14s 3040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generating 10 unique random vectors...
-45 75 1 -71 -83 97 10 -18 89 -10 
-11 60 18 -54 -90 77 19 -90 -7 -31 
-15 -65 -47 88 25 -56 4 39 -20 39 
-64 -14 -37 -13 15 -70 -66 -75 12 73 
-35 -99 32 83 98 -8 59 16 2 -98 
86 37 -63 -62 24 62 -68 78 -50 -38 
17 -64 48 80 -26 -87 61 8 -62 -28 
-70 -47 -27 62 86 -29 -97 44 37 -45 
-4 -28 92 -17 -40 -35 -56 -58 -57 -55 
5 10 -19 -48 -61 5 -35 100 -88 -47 
Generating 1000000 random vectors with only 10 unique...
Unique vectors found:
86 37 -63 -62 24 62 -68 78 -50 -38 
17 -64 48 80 -26 -87 61 8 -62 -28 
5 10 -19 -48 -61 5 -35 100 -88 -47 
-4 -28 92 -17 -40 -35 -56 -58 -57 -55 
-11 60 18 -54 -90 77 19 -90 -7 -31 
-15 -65 -47 88 25 -56 4 39 -20 39 
-35 -99 32 83 98 -8 59 16 2 -98 
-45 75 1 -71 -83 97 10 -18 89 -10 
-64 -14 -37 -13 15 -70 -66 -75 12 73 
-70 -47 -27 62 86 -29 -97 44 37 -45 
Hashed 10 unique vectors out of 1000000 total
https://ideone.com/LXMUCB
language:
C++14 (gcc 8.3)
created:
11 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!