diff options
Diffstat (limited to 'Stats.h')
| -rw-r--r-- | Stats.h | 368 |
1 files changed, 184 insertions, 184 deletions
@@ -15,7 +15,7 @@ void plot ( double n ); inline double ExpectedCollisions ( double balls, double bins )
{
- return balls - bins + bins * pow(1 - 1/bins,balls);
+ return balls - bins + bins * pow(1 - 1/bins,balls);
}
double chooseK ( int b, int k );
@@ -25,13 +25,13 @@ double chooseUpToK ( int n, int k ); inline uint32_t f3mix ( uint32_t k )
{
- k ^= k >> 16;
- k *= 0x85ebca6b;
- k ^= k >> 13;
- k *= 0xc2b2ae35;
- k ^= k >> 16;
+ k ^= k >> 16;
+ k *= 0x85ebca6b;
+ k ^= k >> 13;
+ k *= 0xc2b2ae35;
+ k ^= k >> 16;
- return k;
+ return k;
}
//-----------------------------------------------------------------------------
@@ -39,17 +39,17 @@ inline uint32_t f3mix ( uint32_t k ) template< typename hashtype >
int CountCollisions ( std::vector<hashtype> const & hashes )
{
- int collcount = 0;
+ int collcount = 0;
- std::vector<hashtype> temp = hashes;
- std::sort(temp.begin(),temp.end());
+ std::vector<hashtype> temp = hashes;
+ std::sort(temp.begin(),temp.end());
- for(size_t i = 1; i < hashes.size(); i++)
- {
- if(temp[i] == temp[i-1]) collcount++;
- }
+ for(size_t i = 1; i < hashes.size(); i++)
+ {
+ if(temp[i] == temp[i-1]) collcount++;
+ }
- return collcount;
+ return collcount;
}
//-----------------------------------------------------------------------------
@@ -57,35 +57,35 @@ int CountCollisions ( std::vector<hashtype> const & hashes ) template < class keytype, typename hashtype >
int PrintCollisions ( hashfunc<hashtype> hash, std::vector<keytype> & keys )
{
- int collcount = 0;
+ int collcount = 0;
- typedef std::map<hashtype,keytype> htab;
- htab tab;
+ typedef std::map<hashtype,keytype> htab;
+ htab tab;
- for(size_t i = 1; i < keys.size(); i++)
- {
- keytype & k1 = keys[i];
+ for(size_t i = 1; i < keys.size(); i++)
+ {
+ keytype & k1 = keys[i];
- hashtype h = hash(&k1,sizeof(keytype),0);
+ hashtype h = hash(&k1,sizeof(keytype),0);
- typename htab::iterator it = tab.find(h);
+ typename htab::iterator it = tab.find(h);
- if(it != tab.end())
- {
- keytype & k2 = (*it).second;
+ if(it != tab.end())
+ {
+ keytype & k2 = (*it).second;
- printf("A: ");
- printbits(&k1,sizeof(keytype));
- printf("B: ");
- printbits(&k2,sizeof(keytype));
- }
- else
- {
+ printf("A: ");
+ printbits(&k1,sizeof(keytype));
+ printf("B: ");
+ printbits(&k2,sizeof(keytype));
+ }
+ else
+ {
tab.insert( std::make_pair(h,k1) );
- }
- }
+ }
+ }
- return collcount;
+ return collcount;
}
//----------------------------------------------------------------------------
@@ -93,45 +93,45 @@ int PrintCollisions ( hashfunc<hashtype> hash, std::vector<keytype> & keys ) template < typename hashtype >
bool TestHashList ( std::vector<hashtype> & hashes, bool testColl, bool testDist, bool drawDiagram )
{
- bool result = true;
+ bool result = true;
- if(testColl)
- {
- size_t count = hashes.size();
+ if(testColl)
+ {
+ size_t count = hashes.size();
- double expected = (double(count) * double(count-1)) / pow(2.0,double(sizeof(hashtype) * 8 + 1));
+ double expected = (double(count) * double(count-1)) / pow(2.0,double(sizeof(hashtype) * 8 + 1));
- printf("Testing collisions - Expected %8.2f, ",expected);
+ printf("Testing collisions - Expected %8.2f, ",expected);
- double collcount = 0;
+ double collcount = 0;
- collcount = CountCollisions(hashes);
+ collcount = CountCollisions(hashes);
- printf("actual %8.2f (%5.2fx)",collcount, collcount / expected);
+ printf("actual %8.2f (%5.2fx)",collcount, collcount / expected);
- // 2x expected collisions = fail
+ // 2x expected collisions = fail
- // #TODO - collision failure cutoff needs to be expressed as a standard deviation instead
- // of a scale factor, otherwise we fail erroneously if there are a small expected number
- // of collisions
+ // #TODO - collision failure cutoff needs to be expressed as a standard deviation instead
+ // of a scale factor, otherwise we fail erroneously if there are a small expected number
+ // of collisions
- if(double(collcount) / double(expected) > 2.0)
- {
- printf(" !!!!! ");
- result = false;
- }
+ if(double(collcount) / double(expected) > 2.0)
+ {
+ printf(" !!!!! ");
+ result = false;
+ }
- printf("\n");
- }
+ printf("\n");
+ }
- //----------
+ //----------
- if(testDist)
- {
- TestDistribution(hashes,drawDiagram);
- }
+ if(testDist)
+ {
+ TestDistribution(hashes,drawDiagram);
+ }
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -139,30 +139,30 @@ bool TestHashList ( std::vector<hashtype> & hashes, bool testColl, bool testDist template < class keytype, typename hashtype >
bool TestKeyList ( hashfunc<hashtype> hash, std::vector<keytype> & keys, bool testColl, bool testDist, bool drawDiagram )
{
- int keycount = (int)keys.size();
+ int keycount = (int)keys.size();
- std::vector<hashtype> hashes;
+ std::vector<hashtype> hashes;
- hashes.resize(keycount);
+ hashes.resize(keycount);
- printf("Hashing");
+ printf("Hashing");
- for(int i = 0; i < keycount; i++)
- {
- if(i % (keycount / 10) == 0) printf(".");
+ for(int i = 0; i < keycount; i++)
+ {
+ if(i % (keycount / 10) == 0) printf(".");
- keytype & k = keys[i];
+ keytype & k = keys[i];
- hash(&k,sizeof(k),0,&hashes[i]);
- }
+ hash(&k,sizeof(k),0,&hashes[i]);
+ }
- printf("\n");
+ printf("\n");
- bool result = TestHashList(hashes,testColl,testDist,drawDiagram);
+ bool result = TestHashList(hashes,testColl,testDist,drawDiagram);
- printf("\n");
+ printf("\n");
- return result;
+ return result;
}
//-----------------------------------------------------------------------------
@@ -178,52 +178,52 @@ bool TestKeyList ( hashfunc<hashtype> hash, std::vector<keytype> & keys, bool te template < typename hashtype >
double TestDistributionBytepairs ( std::vector<hashtype> & hashes, bool drawDiagram )
{
- const int nbytes = sizeof(hashtype);
- const int hashbits = nbytes * 8;
-
- const int nbins = 65536;
+ const int nbytes = sizeof(hashtype);
+ const int hashbits = nbytes * 8;
+
+ const int nbins = 65536;
- std::vector<int> bins(nbins,0);
+ std::vector<int> bins(nbins,0);
- double worst = 0;
+ double worst = 0;
- for(int a = 0; a < hashbits; a++)
- {
- if(drawDiagram) if((a % 8 == 0) && (a > 0)) printf("\n");
+ for(int a = 0; a < hashbits; a++)
+ {
+ if(drawDiagram) if((a % 8 == 0) && (a > 0)) printf("\n");
- if(drawDiagram) printf("[");
+ if(drawDiagram) printf("[");
- for(int b = 0; b < hashbits; b++)
- {
- if(drawDiagram) if((b % 8 == 0) && (b > 0)) printf(" ");
+ for(int b = 0; b < hashbits; b++)
+ {
+ if(drawDiagram) if((b % 8 == 0) && (b > 0)) printf(" ");
- bins.clear();
- bins.resize(nbins,0);
+ bins.clear();
+ bins.resize(nbins,0);
- for(size_t i = 0; i < hashes.size(); i++)
- {
- hashtype & hash = hashes[i];
+ for(size_t i = 0; i < hashes.size(); i++)
+ {
+ hashtype & hash = hashes[i];
- uint32_t pa = window(&hash,sizeof(hash),a,8);
- uint32_t pb = window(&hash,sizeof(hash),b,8);
+ uint32_t pa = window(&hash,sizeof(hash),a,8);
+ uint32_t pb = window(&hash,sizeof(hash),b,8);
- bins[pa | (pb << 8)]++;
- }
+ bins[pa | (pb << 8)]++;
+ }
- double s = calcScore(bins,bins.size(),hashes.size());
+ double s = calcScore(bins,bins.size(),hashes.size());
- if(drawDiagram) plot(s);
+ if(drawDiagram) plot(s);
- if(s > worst)
- {
- worst = s;
- }
- }
+ if(s > worst)
+ {
+ worst = s;
+ }
+ }
- if(drawDiagram) printf("]\n");
- }
+ if(drawDiagram) printf("]\n");
+ }
- return worst;
+ return worst;
}
@@ -233,84 +233,84 @@ double TestDistributionBytepairs ( std::vector<hashtype> & hashes, bool drawDiag template< typename hashtype >
double TestDistribution ( std::vector<hashtype> & hashes, bool drawDiagram )
{
- printf("Testing distribution - ");
+ printf("Testing distribution - ");
- if(drawDiagram) printf("\n");
+ if(drawDiagram) printf("\n");
- const int hashbits = sizeof(hashtype) * 8;
+ const int hashbits = sizeof(hashtype) * 8;
- int maxwidth = 20;
+ int maxwidth = 20;
- // We need at least 5 keys per bin to reliably test distribution biases
- // down to 1%, so don't bother to test sparser distributions than that
+ // We need at least 5 keys per bin to reliably test distribution biases
+ // down to 1%, so don't bother to test sparser distributions than that
- while(double(hashes.size()) / double(1 << maxwidth) < 5.0)
- {
- maxwidth--;
- }
+ while(double(hashes.size()) / double(1 << maxwidth) < 5.0)
+ {
+ maxwidth--;
+ }
- std::vector<int> bins;
- bins.resize(1 << maxwidth);
+ std::vector<int> bins;
+ bins.resize(1 << maxwidth);
- double worst = 0;
- int worstStart = -1;
- int worstWidth = -1;
+ double worst = 0;
+ int worstStart = -1;
+ int worstWidth = -1;
- for(int start = 0; start < hashbits; start++)
- {
- int width = maxwidth;
- int bincount = (1 << width);
+ for(int start = 0; start < hashbits; start++)
+ {
+ int width = maxwidth;
+ int bincount = (1 << width);
- memset(&bins[0],0,sizeof(int)*bincount);
+ memset(&bins[0],0,sizeof(int)*bincount);
- for(size_t j = 0; j < hashes.size(); j++)
- {
- hashtype & hash = hashes[j];
+ for(size_t j = 0; j < hashes.size(); j++)
+ {
+ hashtype & hash = hashes[j];
- uint32_t index = window(&hash,sizeof(hash),start,width);
+ uint32_t index = window(&hash,sizeof(hash),start,width);
- bins[index]++;
- }
+ bins[index]++;
+ }
- // Test the distribution, then fold the bins in half,
- // repeat until we're down to 256 bins
+ // Test the distribution, then fold the bins in half,
+ // repeat until we're down to 256 bins
- if(drawDiagram) printf("[");
+ if(drawDiagram) printf("[");
- while(bincount >= 256)
- {
- double n = calcScore(&bins[0],bincount,(int)hashes.size());
+ while(bincount >= 256)
+ {
+ double n = calcScore(&bins[0],bincount,(int)hashes.size());
- if(drawDiagram) plot(n);
+ if(drawDiagram) plot(n);
- if(n > worst)
- {
- worst = n;
- worstStart = start;
- worstWidth = width;
- }
+ if(n > worst)
+ {
+ worst = n;
+ worstStart = start;
+ worstWidth = width;
+ }
- width--;
- bincount /= 2;
+ width--;
+ bincount /= 2;
- if(width < 8) break;
+ if(width < 8) break;
- for(int i = 0; i < bincount; i++)
- {
- bins[i] += bins[i+bincount];
- }
- }
+ for(int i = 0; i < bincount; i++)
+ {
+ bins[i] += bins[i+bincount];
+ }
+ }
- if(drawDiagram) printf("]\n");
- }
+ if(drawDiagram) printf("]\n");
+ }
- double pct = worst * 100.0;
+ double pct = worst * 100.0;
- printf("Worst bias is the %3d-bit window at bit %3d - %5.3f%%",worstWidth,worstStart,pct);
- if(pct >= 1.0) printf(" !!!!! ");
- printf("\n");
+ printf("Worst bias is the %3d-bit window at bit %3d - %5.3f%%",worstWidth,worstStart,pct);
+ if(pct >= 1.0) printf(" !!!!! ");
+ printf("\n");
- return worst;
+ return worst;
}
//-----------------------------------------------------------------------------
@@ -319,36 +319,36 @@ double TestDistribution ( std::vector<hashtype> & hashes, bool drawDiagram ) template < typename hashtype >
void TestDistributionFast ( std::vector<hashtype> & hashes, double & dworst, double & davg )
{
- const int hashbits = sizeof(hashtype) * 8;
- const int nbins = 65536;
-
- std::vector<int> bins(nbins,0);
+ const int hashbits = sizeof(hashtype) * 8;
+ const int nbins = 65536;
+
+ std::vector<int> bins(nbins,0);
- dworst = -1.0e90;
- davg = 0;
+ dworst = -1.0e90;
+ davg = 0;
- for(int start = 0; start < hashbits; start += 8)
- {
- bins.clear();
- bins.resize(nbins,0);
+ for(int start = 0; start < hashbits; start += 8)
+ {
+ bins.clear();
+ bins.resize(nbins,0);
- for(size_t j = 0; j < hashes.size(); j++)
- {
- hashtype & hash = hashes[j];
+ for(size_t j = 0; j < hashes.size(); j++)
+ {
+ hashtype & hash = hashes[j];
- uint32_t index = window(&hash,sizeof(hash),start,16);
+ uint32_t index = window(&hash,sizeof(hash),start,16);
- bins[index]++;
- }
+ bins[index]++;
+ }
- double n = calcScore((int*)bins.begin(),(int)hashes.size(),(int)bins.size());
-
- davg += n;
+ double n = calcScore((int*)bins.begin(),(int)bins.size(),(int)hashes.size());
+
+ davg += n;
- if(n > dworst) dworst = n;
- }
+ if(n > dworst) dworst = n;
+ }
- davg /= double(hashbits/8);
+ davg /= double(hashbits/8);
}
//-----------------------------------------------------------------------------
|