Rosetta Code

Verify distribution uniformity/Naive: Difference between revisions

Page Discussion

Verify distribution uniformity/Naive (view source)

Revision as of 04:56, 21 July 2011

353 bytes added ,  12 years ago
→‎{{header|C}}: replace: remove odd lib dependence
m ({{omit from|GUISS}})
(→‎{{header|C}}: replace: remove odd lib dependence)
Line 58:
 
=={{header|C}}==
<lang c>#include <stdlib.h>▼
{{libheader|Judy}}
<lang c>#include <stdio.h>
▲#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
 
inline int rand5()
#include <Judy.h>
{
int r, rand_max = RAND_MAX - (RAND_MAX % 5);
while ((r = rand()) >= rand_max);
return r / (rand_max / 5) + 1;
}
 
inline int rand5_7()
bool distcheck(int (*dist)(), int n, double D)
{
int r;
Pvoid_t h = (Pvoid_t) NULL;
while ((r = rand5() * 5 + rand5()) >= 27);
PWord_t value;
return r / 3 - 1;
PWord_t element;
}
 
/* assumes gen() returns a value from 1 to n */
Word_t i;
int check(int (*gen)(), int n, int cnt, double delta) /* delta is relative */
int h_length;
{
 
int i = cnt, *bins = calloc(sizeof(int), n);
// populate hashes
double ratio;
for(i=0; i < n; i++) {▼
while (i--) bins[gen() - 1]++;
int rn = dist();
▲ for (i = 0; i < n; i++) {
JLI(value, h, rn);
ratio = bins[i] * n / (double)cnt - 1;
++*value;
if (ratio > -delta && ratio < delta) continue;
}
 
printf("bin %d out of range: %d (%g%% vs %g%%), ",
JLC(h_length, h, 0, -1);
i + 1, bins[i], ratio * 100, delta * 100);
 
break;
double target = 1.0 * n / (double)h_length;
}
 
free(bins);
i = 0;
return i == n;
JLF(element, h, i);
while(element != NULL) {
if ( abs(*element - target) > 0.01*n*D ) {
fprintf(stderr, "distribution potentially skewed for '%d': expected '%d', got '%d'\n",
i, (int)target, *element);
JudyLFreeArray(&h, PJE0);
return false; // bad distr.
}
JLN(element, h, i);
}
 
JudyLFreeArray(&h, PJE0);
return true; // distr. ok
}
 
int main()
{
int cnt = 1;
distcheck(rand, 1000000, 1);
while ((cnt *= 10) <= 1000000) {
return 0;▼
printf("Count = %d: ", cnt);
}</lang>▼
printf(check(rand5_7, 7, cnt, 0.03) ? "flat\n" : "NOT flat\n");
}
 
▲ return 0;
▲}</lang>output<pre>
Count = 10: bin 1 out of range: 1 (-30% vs 3%), NOT flat
Count = 100: bin 1 out of range: 11 (-23% vs 3%), NOT flat
Count = 1000: bin 1 out of range: 150 (5% vs 3%), NOT flat
Count = 10000: bin 3 out of range: 1477 (3.39% vs 3%), NOT flat
Count = 100000: flat
Count = 1000000: flat
</pre>
 
=={{header|C++}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/125133"