Debian Codegraph @

pkg/util/shufflesharding/shufflesharding_test.go

raw
1 /*
2 Copyright 2019 The Kubernetes Authors.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package shufflesharding
18
19 import (
20 "fmt"
21 "math"
22 "math/rand"
23 "reflect"
24 "sort"
25 "testing"
26 )
27
28 func TestRequiredEntropyBits(t *testing.T) {
29 tests := []struct {
30 name string
31 deckSize int
32 handSize int
33 expectedBits int
34 }{
35 {
36 "deckSize: 1024 handSize: 6",
37 1024,
38 6,
39 60,
40 },
41 {
42 "deckSize: 512 handSize: 8",
43 512,
44 8,
45 72,
46 },
47 }
48
49 for _, test := range tests {
50 bits := RequiredEntropyBits(test.deckSize, test.handSize)
51 if bits != test.expectedBits {
52 t.Errorf("test %s fails: expected %v but got %v", test.name, test.expectedBits, bits)
53 return
54 }
55 }
56 }
57
58 func TestNewDealer(t *testing.T) {
59 tests := []struct {
60 name string
61 deckSize int
62 handSize int
63 err error
64 }{
65 {
66 "deckSize <= 0",
67 -100,
68 8,
69 fmt.Errorf("deckSize -100 or handSize 8 is not positive"),
70 },
71 {
72 "handSize <= 0",
73 100,
74 0,
75 fmt.Errorf("deckSize 100 or handSize 0 is not positive"),
76 },
77 {
78 "handSize is greater than deckSize",
79 100,
80 101,
81 fmt.Errorf("handSize 101 is greater than deckSize 100"),
82 },
83 {
84 "deckSize is impractically large",
85 1 << 27,
86 2,
87 fmt.Errorf("deckSize 134217728 is impractically large"),
88 },
89 {
90 "required entropy bits is greater than MaxHashBits",
91 512,
92 8,
93 fmt.Errorf("required entropy bits of deckSize 512 and handSize 8 is greater than 60"),
94 },
95 {
96 "deckSize: 1024 handSize: 6",
97 1024,
98 6,
99 nil,
100 },
101 }
102 for _, test := range tests {
103 t.Run(test.name, func(t *testing.T) {
104 _, err := NewDealer(test.deckSize, test.handSize)
105 if !reflect.DeepEqual(err, test.err) {
106 t.Errorf("test %s fails: expected %v but got %v", test.name, test.err, err)
107 return
108 }
109 })
110 }
111 }
112
113 func TestCardDuplication(t *testing.T) {
114 tests := []struct {
115 name string
116 deckSize int
117 handSize int
118 }{
119 {
120 "deckSize = handSize = 4",
121 4,
122 4,
123 },
124 {
125 "deckSize = handSize = 8",
126 8,
127 8,
128 },
129 {
130 "deckSize = handSize = 10",
131 10,
132 10,
133 },
134 {
135 "deckSize = handSize = 12",
136 12,
137 12,
138 },
139 {
140 "deckSize = 128, handSize = 8",
141 128,
142 8,
143 },
144 {
145 "deckSize = 256, handSize = 7",
146 256,
147 7,
148 },
149 {
150 "deckSize = 512, handSize = 6",
151 512,
152 6,
153 },
154 }
155 for _, test := range tests {
156 hashValue := rand.Uint64()
157 t.Run(test.name, func(t *testing.T) {
158 dealer, err := NewDealer(test.deckSize, test.handSize)
159 if err != nil {
160 t.Errorf("fail to create Dealer: %v", err)
161 return
162 }
163 hand := make([]int, 0)
164 hand = dealer.DealIntoHand(hashValue, hand)
165
166 // check cards number
167 if len(hand) != int(test.handSize) {
168 t.Errorf("test case %s fails in cards number", test.name)
169 return
170 }
171
172 // check cards range and duplication
173 cardMap := make(map[int]struct{})
174 for _, card := range hand {
175 if card < 0 || card >= int(test.deckSize) {
176 t.Errorf("test case %s fails in range check", test.name)
177 return
178 }
179 cardMap[card] = struct{}{}
180 }
181 if len(cardMap) != int(test.handSize) {
182 t.Errorf("test case %s fails in duplication check", test.name)
183 return
184 }
185
186 })
187 }
188 }
189
190 // ff computes the falling factorial `n!/(n-m)!` and requires n to be
191 // positive and m to be in the range [0, n] and requires the answer to
192 // fit in an int
193 func ff(n, m int) int {
194 ans := 1
195 for f := n; f > n-m; f-- {
196 ans *= f
197 }
198 return ans
199 }
200
201 func TestUniformDistribution(t *testing.T) {
202 const spare = 64 - MaxHashBits
203 tests := []struct {
204 deckSize, handSize int
205 hashMax int
206 }{
207 {64, 3, 1 << uint(math.Ceil(math.Log2(float64(ff(64, 3))))+spare)},
208 {128, 3, ff(128, 3)},
209 {50, 4, ff(50, 4)},
210 }
211 for _, test := range tests {
212 dealer, err := NewDealer(test.deckSize, test.handSize)
213 if err != nil {
214 t.Errorf("fail to create Dealer: %v", err)
215 return
216 }
217 handCoordinateMap := make(map[int]int) // maps coded hand to count of times seen
218
219 fallingFactorial := ff(test.deckSize, test.handSize)
220 permutations := ff(test.handSize, test.handSize)
221 allCoordinateCount := fallingFactorial / permutations
222 nff := float64(test.hashMax) / float64(fallingFactorial)
223 minCount := permutations * int(math.Floor(nff))
224 maxCount := permutations * int(math.Ceil(nff))
225 aHand := make([]int, test.handSize)
226 for i := 0; i < test.hashMax; i++ {
227 aHand = dealer.DealIntoHand(uint64(i), aHand)
228 sort.IntSlice(aHand).Sort()
229 handCoordinate := 0
230 for _, card := range aHand {
231 handCoordinate = handCoordinate<<7 + card
232 }
233 handCoordinateMap[handCoordinate]++
234 }
235 numHandsSeen := len(handCoordinateMap)
236
237 t.Logf("Deck size = %v, hand size = %v, number of possible hands = %d, number of hands seen = %d, number of deals = %d, expected count range = [%v, %v]", test.deckSize, test.handSize, allCoordinateCount, numHandsSeen, test.hashMax, minCount, maxCount)
238
239 // histogram maps (count of times a hand is seen) to (number of hands having that count)
240 histogram := make(map[int]int)
241 for _, count := range handCoordinateMap {
242 histogram[count] = histogram[count] + 1
243 }
244
245 var goodSum int
246 for count := minCount; count <= maxCount; count++ {
247 goodSum += histogram[count]
248 }
249
250 goodPct := 100 * float64(goodSum) / float64(numHandsSeen)
251
252 t.Logf("good percentage = %v, histogram = %v", goodPct, histogram)
253 if goodSum != numHandsSeen {
254 t.Errorf("Only %v percent of the hands got a central count", goodPct)
255 }
256 }
257 }
258
259 func TestDealer_DealIntoHand(t *testing.T) {
260 dealer, _ := NewDealer(6, 6)
261
262 tests := []struct {
263 name string
264 hand []int
265 expectedSize int
266 }{
267 {
268 "nil slice",
269 nil,
270 6,
271 },
272 {
273 "empty slice",
274 make([]int, 0),
275 6,
276 },
277 {
278 "size: 6 cap: 6 slice",
279 make([]int, 6),
280 6,
281 },
282 {
283 "size: 6 cap: 12 slice",
284 make([]int, 6, 12),
285 6,
286 },
287 {
288 "size: 4 cap: 4 slice",
289 make([]int, 4),
290 6,
291 },
292 {
293 "size: 4 cap: 12 slice",
294 make([]int, 4, 12),
295 6,
296 },
297 {
298 "size: 10 cap: 10 slice",
299 make([]int, 10),
300 6,
301 },
302 {
303 "size: 10 cap: 12 slice",
304 make([]int, 10, 12),
305 6,
306 },
307 }
308 for _, test := range tests {
309 t.Run(test.name, func(t *testing.T) {
310 h := dealer.DealIntoHand(0, test.hand)
311 if len(h) != test.expectedSize {
312 t.Errorf("test %s fails: expetced size %d but got %d", test.name, test.expectedSize, len(h))
313 return
314 }
315 })
316 }
317 }