1 // { dg-options "-std=gnu++0x" }
3 // Use smaller statistics when running on simulators, so it takes less time.
4 // { dg-options "-std=gnu++0x -DSAMPLES=30000" { target simulator } }
6 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
8 // This file is part of the GNU ISO C++ Library. This library is free
9 // software; you can redistribute it and/or modify it under the
10 // terms of the GNU General Public License as published by the
11 // Free Software Foundation; either version 3, or (at your option)
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 // GNU General Public License for more details.
19 // You should have received a copy of the GNU General Public License
20 // along with this library; see the file COPYING3. If not see
21 // <http://www.gnu.org/licenses/>.
23 // This file uses the chi^2 test to measure the quality of a hash
24 // function, by computing the uniformity with which it distributes a set
25 // of N strings into k buckets (where k is significantly greater than N).
27 // Each bucket has B[i] strings in it. The expected value of each bucket
28 // for a uniform distribution is z = N/k, so
29 // chi^2 = Sum_i (B[i] - z)^2 / z.
31 // We check whether chi^2 is small enough to be consistent with the
32 // hypothesis of a uniform distribution. If F(chi^2, k-1) is close to
33 // 0 (where F is the cumulative probability distribution), we can
34 // reject that hypothesis. So we don't want F to be too small, which
35 // for large k, means we want chi^2 to be not too much larger than k.
37 // We use the chi^2 test for several sets of strings. Any non-horrible
38 // hash function should do well with purely random strings. A really
39 // good hash function will also do well with more structured sets,
40 // including ones where the strings differ by only a few bits.
50 #include <unordered_set>
52 #include <testsuite_hooks.h>
55 #define SAMPLES 300000
58 template <typename Container
>
60 chi2_hash(const Container
& c
, long buckets
)
62 std::vector
<int> counts(buckets
);
63 std::hash
<std::string
> hasher
;
65 for (auto i
= c
.begin(); i
!= c
.end(); ++i
)
67 ++counts
[hasher(*i
) % buckets
];
71 const double z
= elements
/ buckets
;
73 for (long i
= 0; i
< buckets
; ++i
)
75 double delta
= counts
[i
] - z
;
81 // Tests chi^2 for a distribution of uniformly generated random strings.
85 bool test
__attribute__((unused
)) = true;
87 std::unordered_set
<std::string
> set
;
89 const unsigned long N
= SAMPLES
;
90 const unsigned long k
= N
/100;
91 const unsigned int len
= 25;
92 while (set
.size() < N
)
95 for (unsigned int i
= 0; i
< len
; ++i
)
96 s
.push_back(rand() % 128);
100 double chi2
= chi2_hash(set
, k
);
101 VERIFY( chi2
< k
*1.1 );
104 // Tests chi^2 for a distribution of strings that differ from each
105 // other by only a few bits. We start with an arbitrary base string, and
106 // flip three random bits for each member of the set.
110 bool test
__attribute__((unused
)) = true;
111 const unsigned long N
= SAMPLES
;
112 const unsigned long k
= N
/100;
113 const unsigned int len
= 67;
114 const unsigned int bitlen
= len
* 8;
115 const unsigned int bits_to_flip
= 3;
116 const char base
[len
+1] = "abcdefghijklmnopqrstuvwxyz"
117 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
120 std::unordered_set
<std::string
> set
;
121 while (set
.size() < N
)
123 std::string
s(base
, base
+len
);
124 for (unsigned int i
= 0; i
< bits_to_flip
; ++i
)
126 int bit
= rand() % bitlen
;
127 s
[bit
/8] ^= (1 << (bit
%8));
132 double chi2
= chi2_hash(set
, k
);
133 VERIFY( chi2
< k
*1.1 );
136 // Tests chi^2 of a set of strings that all have a similar pattern,
137 // intended to mimic some sort of ID string.
139 test_numeric_pattern_set()
141 bool test
__attribute__((unused
)) = true;
142 const unsigned long N
= SAMPLES
;
143 const unsigned long k
= N
/100;
144 std::vector
<std::string
> set
;
145 for (unsigned long i
= 0; i
< N
; ++i
)
147 long i1
= i
% 100000;
148 long i2
= i
/ 100000;
150 std::sprintf(buf
, "XX-%05lu-%05lu", i1
, i2
);
154 double chi2
= chi2_hash(set
, k
);
155 VERIFY( chi2
< k
*1.1 );
158 // Tests chi^2 for a set of strings that all consist of '1' and '0'.
160 test_bit_string_set()
162 bool test
__attribute__((unused
)) = true;
163 const unsigned long N
= SAMPLES
;
164 const unsigned long k
= N
/100;
165 std::vector
<std::string
> set
;
167 for (unsigned long i
= 0; i
< N
; ++i
)
170 for (unsigned int j
= 0; j
< sizeof(unsigned long) * 8; ++j
)
172 const bool bit
= (1UL << j
) & i
;
173 s
.push_back(bit
? '1' : '0');
178 double chi2
= chi2_hash(set
, k
);
179 VERIFY( chi2
< k
*1.1 );
182 // Tests chi^2 for a set of words taken from a document written in English.
184 test_document_words()
186 // That file is 187587 single-word lines. To avoid a timeout, just skip
187 // this part, which would take up to 95% of the program runtime (with
188 // SAMPLES == 10000), if we're not supposed to run anywhere that long.
189 #if SAMPLES >= 100000
190 bool test
__attribute__((unused
)) = true;
191 const std::string f_name
= "thirty_years_among_the_dead_preproc.txt";
192 std::ifstream
in(f_name
);
193 VERIFY( in
.is_open() );
194 std::vector
<std::string
> words
;
195 words
.assign(std::istream_iterator
<std::string
>(in
),
196 std::istream_iterator
<std::string
>());
197 VERIFY( words
.size() > 100000 );
198 std::sort(words
.begin(), words
.end());
199 auto it
= std::unique(words
.begin(), words
.end());
200 words
.erase(it
, words
.end());
201 VERIFY( words
.size() > 5000 );
203 const unsigned long k
= words
.size() / 20;
204 double chi2
= chi2_hash(words
, k
);
205 VERIFY( chi2
< k
*1.1 );
212 test_uniform_random();
214 test_numeric_pattern_set();
215 test_bit_string_set();
216 test_document_words();