1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
-- Difficult: write a QuickCheck property that checks whether the observed false
-- positive rate is close to the requested false positive rate.
-- I think testing/proving statistical properties can never be done using finite
-- data. Thus, this test will only be a good effort for adequate testing. This
-- also implies that instead of trying to make every test run pass, the overall
-- test result will be determined by comparing number of passes and number of
-- discards.
-- Requesting false positive rate happens via the easyList function, so this
-- exercise is about testing that function.
-- The "is close" in the assignment is unclear. The authors probably meant to
-- check that the false positive rate is lower or close-to-equal than the
-- requested rate. For the "close" I add 10% margin to the requested false
-- positive rate when comparing the actual rate to it.
-- After running a few experiments with QuickCheck, I found that the initial
-- lists passed to the property function were, for example '[(),(),(),()]' or
-- '[0,0,0,0]' when I restricted the type to [Int].
--
-- I want to test the worst cases. It means, increasing the chance of getting a
-- false positive and see whether it is still less or equally frequent than
-- requested. The more values with different hashes are inserted to the bloom
-- filter (it means, the more bits are set), the higher chance of a false
-- positive. Thus, lists filled with the same value are not suitable.
--
-- To make the test simpler and easier to control, I will restrict the input
-- list type to [Int].
-- The test for worst cases will be as follows:
--
-- 1) Generate a random number L from range [maxLen..minLen]. The range is
-- limited so the lists are not too big and the testing not too slow.
--
-- 2) Create a list XS of length L of random Int values. They don't have to
-- be unique. I don't assume properties of the hash function used, so it's
-- not possible to tell that all-unique values would be the worst case
-- (set as many bits in the filter as possible).
--
-- 3) Create a list YS of length ysRatio*L of random Int values different
-- from XS. For the worst case it is important that all values in YS are
-- different from values in XS for getting as many false positives as
-- possible. It doesn't matter whether YS values are unique among
-- themselves. YS list should be as long as possible. If it's short, for
-- example, just 2 values, and both of them are false positives, the
-- actual false positive rate would be 2/2 = 1.0. The longer the list is,
-- the higher chance of getting closer to true false positive rate. I
-- restricted the length of YS to be a multiple of the length of XS. It
-- should be long enough, but not too long for the testing to be too slow.
--
-- 4) Generate a random requested false positive rate.
--
-- 5) Create a bloom filter via easyList function with values XS. If it
-- fails, discard the test case.
--
-- 6) Get an actual false positive rate. For each item in YS check if it is
-- in the bloom filter. If it is, increment false positive count. Divide
-- the count by length of YS.
--
-- 7) If the actual false positive rate is lower or close-to-equal to the
-- requested false positive rate, the test case passes. If not, it is
-- discarded.
{-- From examples/examples/ch26/examples/BloomCheck.hs and modified --}
import Test.QuickCheck
import qualified BloomFilter.Easy as B
import qualified Data.Map.Lazy as Map
-- Instead of failing the testing, use 'discard' so it can continue and report
-- the overall results
handyCheck :: Testable a => Int -> a -> IO ()
-- 'withDiscardRatio 1' means that the max. number of discards for the testing
-- to still pass will be 1*number of requested successful runs. The number of
-- all test runs might be different every time because the testing continues
-- until either the max. success limit or the max. discard limit is
-- reached. This means that testing passes when number of discards is < than
-- number of successful runs, and fails otherwise.
handyCheck limit p = quickCheck $ withDiscardRatio 1 $ withMaxSuccess limit p
falsePositive :: Gen Double
falsePositive = choose (epsilon, 1 - epsilon)
where epsilon = 1e-6
(=~>) :: Either a b -> (b -> Bool) -> Bool
k =~> f = either (const discard) f k
{-- End of code from examples --}
randomInt :: Gen Int
randomInt = chooseInt (minBound :: Int, maxBound :: Int)
randomList :: Int -> Gen [Int]
randomList len = vectorOf len randomInt
randomListWithout :: Int -> [Int] -> Gen [Int]
randomListWithout len without = go len withoutMap []
-- Use Map for faster lookup of excluded Ints
where withoutMap = Map.fromList $ zip without (repeat ())
go 0 _ res = return res
go len wo res = do
i <- randomInt
case Map.lookup i wo of
Nothing ->
-- Good value. Not excluded by the 'without' list. Add it to the
-- result.
go (len-1) wo (i:res)
Just _ ->
-- Excluded value. Try again.
go len wo res
prop_false_positive_rate =
let
-- These exact values are set based on experimental test runs for the
-- testing not to be too slow
minLen = 1
maxLen = 50
ysRatio = 500
in
-- Choose number of items in the bloom filter
forAll (choose (minLen, maxLen) :: Gen Int) $ \len -> do
-- Generate values to insert to the filter
forAll (randomList len) $ \xs-> do
-- Generate a longer list with values that won't be in the filter
forAll (randomListWithout (ysRatio * len) xs) $ \ys-> do
forAll falsePositive $ \requestedErrRate ->
B.easyList requestedErrRate xs =~> \filt ->
-- Add 10% margin to the requested rate
if (errRate filt ys) <= (requestedErrRate * 1.1)
then True
else discard
errRate :: B.Bloom Int -> [Int] -> Double
errRate filt ys = (fromIntegral fp) / fromIntegral (length ys)
where fp = countIsElem filt ys
countIsElem :: B.Bloom Int -> [Int] -> Int
countIsElem filt ys = length $ filter id $ map (`B.elem` filt) ys
-- stack ghci --ghci-options "-L$(pwd) -llookup3"
-- ghci> :l 26_a_2.hs
-- [1 of 7] Compiling BloomFilter.Hash ( BloomFilter/Hash.hs, interpreted )
--
-- ... omitted compiler warnings
--
-- [2 of 7] Compiling BloomFilter.Internal ( BloomFilter/Internal.hs, interpreted )
-- [3 of 7] Compiling BloomFilter.Mutable ( BloomFilter/Mutable.hs, interpreted )
-- [4 of 7] Compiling BloomFilter ( BloomFilter.hs, interpreted )
-- [5 of 7] Compiling BloomFilter.Easy ( BloomFilter/Easy.hs, interpreted )
-- [6 of 7] Compiling Main ( 26_a_2.hs, interpreted )
-- Ok, six modules loaded.
-- ghci> handyCheck 100 prop_false_positive_rate
-- +++ OK, passed 100 tests; 20 discarded.
-- ghci> handyCheck 600 prop_false_positive_rate
-- +++ OK, passed 600 tests; 179 discarded.
-- ghci> handyCheck 2000 prop_false_positive_rate
-- +++ OK, passed 2000 tests; 561 discarded.
|
