涉及随机性的算法的 TDD
TDD for an algorithm involving randomness
我想尝试测试驱动开发，但我正在做的项目涉及很多随机性，我很不确定如何测试它。这是我可能想写的那种算法的玩具示例：
Write a function taking no argument and returning a list of random integers satisfying the following properties
- Each integer is between 0 and 10
- The same number doesn’t appear twice
- The list is of length 3 90% of the time, and of length 4 10% of the time
- There is a 50% chance for the number 3 to appear
我不需要测试精确的统计分布，但显然我希望测试如果有人完全删除相应的代码就会失败。
我正在使用您可以认为是正确的外部 RNG，而且我在如何构建代码方面非常自由，因此我可以使用依赖注入来让测试使用伪造的 RNG，但我仍然不这样做真的看不出这会有什么帮助。例如，即使我总是使用相同的种子进行测试，一旦我重构算法以不同的顺序选择随机数，所有测试都变得毫无意义。
我想前两点可以通过生成许多案例并检查是否满足约束来测试，但这并不像 TDD。
对于最后两点，我正在考虑使用不同的配置进行测试，例如 90% 是 100% 或 0%，然后我可以测试列表的长度是否确实是 3或4.我想它会起作用，但它似乎有点弱。
在使用 TDD 测试涉及随机性的算法时是否有任何指南或其他技术可供使用？
有几种方法可以解决这样的问题，我以后可能会添加另一个答案，但我立即发现最引人注目的方法是结合 test-driven 开发 (TDD) property-based 测试.
您可以使用多种语言和各种框架来实现这一点。在这里，我将使用原始 property-based 测试库 QuickCheck.
前两个要求直接转化为 QuickCheck 可以执行的谓词。后两者转化为分布测试 - QuickCheck 的更高级功能 John Hughes explains in this presentation.
每个人依次。
预赛
在编写第一个测试之前，您将设置测试并导入适当的库：
module RintsProperties where
import Test.Framework (Test)
import Test.Framework.Providers.QuickCheck2
import Test.QuickCheck
import Q72168364
其中被测系统 (SUT) 在 Q72168364 库中定义。 SUT 本身是一个名为 rints 的动作（对于 Random INTS）：
rints :: IO [Int]
由于要生成随机数，因此必须 运行 in IO。
图片
第一个要求说明了 SUT 的 the image。这很容易表示为 属性:
testProperty "Each integer is between 0 and 10" $ \() -> ioProperty $ do
actual <- rints
return $
counterexample ("actual: " ++ show actual) $
all (\i -> 0 <= i && i <= 10) actual
如果您忽略一些与生成有用的断言消息等相关的仪式，那么核心断言是这样的：
all (\i -> 0 <= i && i <= 10) actual
验证 actual 中的所有整数 i 都在 0 到 10 之间。
在真正的 TDD 方式中，通过测试的最简单的实现是这样的：
rints :: IO [Int]
rints = return []
始终return 一个空列表。虽然退化了，但它满足了要求。
无重复
下一个要求也很容易转化为谓词：
testProperty "The same number does not appear twice" $ \() -> ioProperty $ do
actual <- rints
return $ nub actual === actual
nub 删除了重复项，因此此断言指出 nub actual（删除了重复项的 actual）应等于 actual。只有 actual.
中没有重复项才会出现这种情况
在 TDD 方式中，遗憾的是实现没有改变：
rints :: IO [Int]
rints = return []
其实我写这篇属性的时候，直接就过去了。如果您关注 the red-green-refactor checklist，这是不允许的。您应该通过编写一个红色测试来开始每个循环，但是这个立即变成绿色。
正确的反应应该是放弃（或stash) that test and instead write another one - perhaps taking a cue from the Transformation Priority Premise选择下一个好的测试。
但是，出于指导原因，我将坚持 OP 中规定的要求顺序。我没有遵循 red-green-refactor 清单，而是以各种方式修改了 rints 以确保断言按预期工作。
长度分布
下一个要求不是简单的谓词，而是关于结果分布的陈述。 QuickCheck 的 cover 功能实现了这一点——我在其他 property-based 测试库中没有看到的功能：
testProperty "Length is and distribution is correct" $ \() -> ioProperty $ do
actual <- rints
let l = length actual
return $
checkCoverage $
cover 90 (l == 3) "Length 3" $
cover 10 (l == 4) "Length 4"
True -- Base property, but really, the distribution is the test
cover 的工作方式，它需要有一个 'base property'，但这里我只是 return True - 基数 属性 总是通过,意思是分布是实际测试。
cover 的两个实例说明了每个谓词（l == 3 和 l == 4）应该出现的百分比。
运行 具有退化实现的测试产生此测试失败：
Length is and distribution is correct: [Failed]
*** Failed! Insufficient coverage (after 100 tests):
Only 0% Length 3, but expected 90%
如消息所述，它预计 90% 的 Length 3 个案例，但得到了 0%。
同样，在 TDD 之后，可以尝试解决直接错误：
rints :: IO [Int]
rints = return [1,2,3]
但是，这会导致此测试失败：
Length is and distribution is correct: [Failed]
*** Failed! Insufficient coverage (after 400 tests):
100.0% Length 3
Only 0.0% Length 4, but expected 10.0%
属性 预计 10% Length 4 个案例，但得到了 0%。
也许以下是可能可行的最简单的方法？
import System.Random.Stateful
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
if 10 < p then return [1,2,3] else return [1,2,3,4]
可能不像您期望的那样随机，但它通过了所有测试。
更多三分球
最终（明确的）要求是 3 应该出现 50% 的次数。那是另一个分布 属性:
testProperty "3 appears 50% of the times" $ \() -> ioProperty $ do
actual <- rints
return $
checkCoverage $
cover 50 (3 `elem` actual) "3 present" $
cover 50 (3 `notElem` actual) "3 absent"
True -- Base property, but really, the distribution is the test
运行 所有测试都会导致此测试失败：
3 appears 50% of the times: [Failed]
*** Failed! Insufficient coverage (after 100 tests):
100% 3 present
Only 0% 3 absent, but expected 50%
毫不奇怪，它说 3 present 情况发生的概率为 100%。
本着 TDD 的精神（也许有点散漫，但它说明了正在发生的事情），您可以尝试像这样修改 rints：
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
if 10 < p then return [1,2,3] else return [1,2,4,5]
然而，这不起作用，因为分布仍然是错误的：
3 appears 50% of the times: [Failed]
*** Failed! Insufficient coverage (after 100 tests):
89% 3 present
11% 3 absent
Only 11% 3 absent, but expected 50%
也许以下是最简单的方法。这就是我的选择，至少：
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
includeThree <- uniformM globalStdGen
if 10 < p
then if includeThree then return [1,2,3] else return [1,2,4]
else if includeThree then return [1,2,3,4] else return [1,2,4,5]
不优雅，它仍然不产生随机数，但它通过了所有测试。
随机数
虽然上面涵盖了所有明确规定的要求，但显然不能令人满意，因为它并没有真正产生 1 到 10 之间的随机数。
这是典型的 TDD 过程。当您编写测试和 SUT 并让两者交互时，您会发现需要的测试比您原先想象的要多。
老实说，我不确定 'force' 生成 0 到 10 之间所有数字的最佳方法是什么。现在我有了 hammer 分布 tsts，我写了以下内容：
testProperty "All numbers are represented" $ \() -> ioProperty $ do
actual <- rints
return $
checkCoverage $
cover 5 ( 0 `elem` actual) " 0 present" $
cover 5 ( 1 `elem` actual) " 1 present" $
cover 5 ( 2 `elem` actual) " 2 present" $
cover 5 ( 3 `elem` actual) " 3 present" $
cover 5 ( 4 `elem` actual) " 4 present" $
cover 5 ( 5 `elem` actual) " 5 present" $
cover 5 ( 6 `elem` actual) " 6 present" $
cover 5 ( 7 `elem` actual) " 7 present" $
cover 5 ( 8 `elem` actual) " 8 present" $
cover 5 ( 9 `elem` actual) " 9 present" $
cover 5 (10 `elem` actual) "10 present"
True -- Base property, but really, the distribution is the test
我承认我对此并不完全满意，因为它似乎无法 'scale' 解决函数图像大得多的问题。我愿意接受更好的选择。
我也不想对每个数字的确切分布过于具体。毕竟，3 会比其他人更频繁地出现。因此，我只选择了一小部分（5%）来表示每个数字应该不会出现太少。
到目前为止，rints 的实施以与其他分发测试相同的方式未能通过此新测试。
粗略地说，我将实现更改为：
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
let l = if 10 < p then 3 else 4
ns <- shuffle $ [0..2] ++ [4..10]
includeThree <- uniformM globalStdGen
if includeThree
then do
let ns' = take (l - 1) ns
shuffle $ 3 : ns'
else
return $ take l ns
虽然我觉得还有改进的余地，但它通过了所有测试并实际生成了随机数：
ghci> rints
[5,2,1]
ghci> rints
[9,2,10]
ghci> rints
[8,1,3]
ghci> rints
[0,9,8]
ghci> rints
[0,10,3,6]
此示例使用了 QuickCheck with Haskell，但大部分想法都翻译成其他语言。 QuickCheck 的 cover 函数可能是该规则的一个例外，因为我不知道它已被移植到通用语言实现中，但也许我只是落后于曲线。
在 cover 之类的东西不可用的情况下，您必须编写一个测试，循环遍历足够多的随机生成的测试用例，以验证分发是否符合要求。多一点工作，但并非不可能。
I would like to try out test-driven development, but the project I am working on involves a lot of randomness
你应该意识到“随机性”在一个相当尴尬的地方影响了 TDD，所以它不是最直接的“try-it-out”项目。
有两个问题 - 一个是“随机性”是一个非常昂贵的断言：
您如何可靠地区分此实现和“真正的”随机数生成器，后者恰好在更改为其他数字之前发出有限的 4 序列？
因此我们可以在实际上不表达我们所有约束的稳定测试或偶尔报告不正确结果的更精确测试之间做出选择。
这里的一种设计方法是倾向于“可测试性”——在我们界面的外观背后是一个将通用随机位源与 确定性 函数相结合的实现将位序列映射到某个结果。
def randomListOfIntegers():
seed_bits = generalPurpose.random_bits()
return determisticFunction(seed_bits)
def deterministicFunction(seed_bits):
???
声称randomListOfIntegers“简单到明显没有缺陷”，所以我们可以通过检查来确定其正确性，并集中精力进行deterministicFunction的设计。
现在，我们 运行 进入第二个问题：seed_bits 到某些可观察结果的映射是任意的。大多数业务领域问题（例如：薪资系统）对于任何给定的输入都有一个单一的预期输出，但在随机系统中你仍然有一些额外的自由度。如果您编写的函数在给定任何位序列的情况下都能产生可接受的答案，那么我的函数（将这些位取反然后调用您的函数）也将产生可接受的答案——即使我的答案和您的答案不同。
实际上，如果我们想要一套测试在代码更改导致行为变化时发出警报，那么我们必须发明我们想要锁定的行为规范。
除非我们很好地猜测哪些任意行为将支持干净的实现，否则这可能会非常痛苦。
（或者，我们只依靠我们的“验收”测试池，它忽略切换到不同的任意行为的代码更改——它一直在权衡取舍）。
我们可能会考虑的一种更简单的实现方式是将 seed_bits 视为一系列候选响应的索引
def deterministicFunction(seed_bits):
choices = ???
n = computeIndex(seed_bits, len(choices))
return choices[n]
这暴露了另一个问题：k seed_bits 表示 2^k 个自由度；除非 len(choices) 恰好是 2 的幂并且不大于 2^k，否则在选择时会有一些偏差。您可以通过为 k 选择足够大的值来使偏差误差任意小，但是您不能用有限的位数来消除它。
进一步分解问题，我们可以将工作分为两个部分，一个负责生成候选人库，另一个负责实际选择其中一个。
def deterministicFunction(seed_bits):
return choose(seed_bits, weighted_candidates())
def choose(seed_bits, weighted_candidates):
choices = []
# note: the order of elements in this enumeration
# is still arbitrary
for candidate, weight in weighted_candidates:
for _ in range(weight):
choices.add(candidate)
# technically, this is also still arbirary
n = computeIndex(seed_bits, len(choices))
return choices[n]
在这一点上，我们可以决定使用“可能工作的最简单的东西”来实现computeIndex（如果你愿意，请先测试），这个新的weighted_candidates()功能也很容易进行测试，因为它的每次测试都只是“计算候选人并确保问题约束被整个人口所满足”。 choose 可以使用更简单的人群作为输入进行测试。
这种实现可能不尽如人意 - 毕竟，我们正在构建候选数据结构，然后是另一个选择，只能选择一个。这可能是我们能做的最好的。但是，通常可以采用不同的实现方式。
实际上，问题说明为我们定义了（加权的）响应总体的大小。换句话说，len(choices) 实际上是一些常量 L.
choices = [ generate(n) for n in range(L)]
n = computeIndex(seed_bits, L)
return choices[n]
这又可以简化为
n = computeIndex(seed_bits, L)
return generate(n)
也就是说，如果我们可以计算哪个响应排在第n位，我们就不需要传递一堆数据结构。
请注意，虽然 generate(n) 仍然具有任意行为，但我们可以对数据结构 [generate(n) for n in range(L)].
做出明确的断言
稍微重构一下，我们可能会
def randomListOfIntegers():
seed_bits = generalPurpose.random_bits()
n = computeIndex(seed_bits, L)
return generateListOfIntegers(n)
请注意，这个骨架并不是从写出一堆测试和重构中“出现”的，而是从思考问题和我们需要考虑的选择中“出现”的，以便“控制决策之间的差距”和反馈”。
将其称为“尖峰”可能比较公平 - 我们用来更好地理解我们要解决的问题的沙盒练习。
The same number doesn’t appear twice
了解组合学 会有所帮助。
基本思路：我们可以计算集合 [0,1,2,3,4,5,6,7,8,9,10] 的 4 个唯一元素的所有可能排列的集合，并且我们可以使用一种称为 squashed ordering 的技术来生成它们的特定子集。
在这里，我们可能想要处理规范al case of 3 更仔细一点。粗略的骨架看起来像
def generateListOfIntegers(n):
other_numbers = [0,1,2,4,5,6,7,8,9,10]
has3, hasLength3, k = decode(n)
if has3:
if hasLength3:
# 45 distinct candidates
assert 0 <= k < 45
return [3] ++ choose(other_numbers, 2, k)
else:
# 120 distinct candidates
assert 0 <= k < 120
return [3] ++ choose(other_numbers, 3, k)
else:
if hasLength3:
# 120 distinct candidates
assert 0 <= k < 120
return choose(other_numbers, 3, k)
else:
# 210 distinct candidates
assert 0<= k < 210
return choose(other_numbers, 4, k)
其中 choose(other_numbers, j, k) returns other_numbers 的 kth 子集具有 j 个总元素，并且 decode(n) 具有必要的逻辑以确保人口权重是正确的。
choose的行为是任意的，但是子集的进展有一个“自然”顺序（即，您可以对它们进行“排序”），因此任意使用排序顺序是合理的。
可能还值得注意的是，choose 是非常通用的 - 我们传入的列表可以是任何内容，它并不关心您如何处理答案。与 decode 相比，我们对“正确”行为的定义与 generateListOfNumbers 的消费紧密相关。
您可能想要查看 Peter Seiber 的 Fischer Chess Exercise, to see the different approaches people were taking when TDD was new. Warning, the threading is horribly broken now, so you may need to sift through multiple threads 以找到所有好的部分。
首先，TDD 的方法不止一种，因此没有唯一的正确答案。但这是我对此的看法：
您提到您不需要测试精确的统计分布，但我认为您必须这样做。否则，编写满足您的测试的最简单代码将导致完全确定的 non-random 解决方案。 （如果你在不考虑随机性的情况下查看你的需求，你会发现你可以使用一个简单的循环和很少的 if 语句来满足它们）。但显然，这不是您真正想要的。因此，在您的情况下，您必须编写一个测试来检查算法的统计分布。
此类测试需要收集被测功能的许多结果，因此可能会很慢，因此有些人会认为这是一种不好的做法，但恕我直言，这是您实际测试您真正关心的内容的唯一方法。
假设这不仅仅是一个理论练习，您可能还想将结果保存到一个文件中，您以后可以手动检查（例如使用 Excel），检查结果的其他统计属性，并可能相应地添加或调整您的测试。
我想尝试测试驱动开发，但我正在做的项目涉及很多随机性，我很不确定如何测试它。这是我可能想写的那种算法的玩具示例：
Write a function taking no argument and returning a list of random integers satisfying the following properties
- Each integer is between 0 and 10
- The same number doesn’t appear twice
- The list is of length 3 90% of the time, and of length 4 10% of the time
- There is a 50% chance for the number 3 to appear
我不需要测试精确的统计分布，但显然我希望测试如果有人完全删除相应的代码就会失败。
我正在使用您可以认为是正确的外部 RNG，而且我在如何构建代码方面非常自由，因此我可以使用依赖注入来让测试使用伪造的 RNG，但我仍然不这样做真的看不出这会有什么帮助。例如，即使我总是使用相同的种子进行测试，一旦我重构算法以不同的顺序选择随机数，所有测试都变得毫无意义。
我想前两点可以通过生成许多案例并检查是否满足约束来测试，但这并不像 TDD。
对于最后两点，我正在考虑使用不同的配置进行测试，例如 90% 是 100% 或 0%，然后我可以测试列表的长度是否确实是 3或4.我想它会起作用，但它似乎有点弱。
在使用 TDD 测试涉及随机性的算法时是否有任何指南或其他技术可供使用？
有几种方法可以解决这样的问题，我以后可能会添加另一个答案，但我立即发现最引人注目的方法是结合 test-driven 开发 (TDD) property-based 测试.
您可以使用多种语言和各种框架来实现这一点。在这里，我将使用原始 property-based 测试库 QuickCheck.
前两个要求直接转化为 QuickCheck 可以执行的谓词。后两者转化为分布测试 - QuickCheck 的更高级功能 John Hughes explains in this presentation.
每个人依次。
预赛
在编写第一个测试之前，您将设置测试并导入适当的库：
module RintsProperties where
import Test.Framework (Test)
import Test.Framework.Providers.QuickCheck2
import Test.QuickCheck
import Q72168364
其中被测系统 (SUT) 在 Q72168364 库中定义。 SUT 本身是一个名为 rints 的动作（对于 Random INTS）：
rints :: IO [Int]
由于要生成随机数，因此必须 运行 in IO。
图片
第一个要求说明了 SUT 的 the image。这很容易表示为 属性:
testProperty "Each integer is between 0 and 10" $ \() -> ioProperty $ do
actual <- rints
return $
counterexample ("actual: " ++ show actual) $
all (\i -> 0 <= i && i <= 10) actual
如果您忽略一些与生成有用的断言消息等相关的仪式，那么核心断言是这样的：
all (\i -> 0 <= i && i <= 10) actual
验证 actual 中的所有整数 i 都在 0 到 10 之间。
在真正的 TDD 方式中，通过测试的最简单的实现是这样的：
rints :: IO [Int]
rints = return []
始终return 一个空列表。虽然退化了，但它满足了要求。
无重复
下一个要求也很容易转化为谓词：
testProperty "The same number does not appear twice" $ \() -> ioProperty $ do
actual <- rints
return $ nub actual === actual
nub 删除了重复项，因此此断言指出 nub actual（删除了重复项的 actual）应等于 actual。只有 actual.
在 TDD 方式中，遗憾的是实现没有改变：
rints :: IO [Int]
rints = return []
其实我写这篇属性的时候，直接就过去了。如果您关注 the red-green-refactor checklist，这是不允许的。您应该通过编写一个红色测试来开始每个循环，但是这个立即变成绿色。
正确的反应应该是放弃（或stash) that test and instead write another one - perhaps taking a cue from the Transformation Priority Premise选择下一个好的测试。
但是，出于指导原因，我将坚持 OP 中规定的要求顺序。我没有遵循 red-green-refactor 清单，而是以各种方式修改了 rints 以确保断言按预期工作。
长度分布
下一个要求不是简单的谓词，而是关于结果分布的陈述。 QuickCheck 的 cover 功能实现了这一点——我在其他 property-based 测试库中没有看到的功能：
testProperty "Length is and distribution is correct" $ \() -> ioProperty $ do
actual <- rints
let l = length actual
return $
checkCoverage $
cover 90 (l == 3) "Length 3" $
cover 10 (l == 4) "Length 4"
True -- Base property, but really, the distribution is the test
cover 的工作方式，它需要有一个 'base property'，但这里我只是 return True - 基数 属性 总是通过,意思是分布是实际测试。
cover 的两个实例说明了每个谓词（l == 3 和 l == 4）应该出现的百分比。
运行 具有退化实现的测试产生此测试失败：
Length is and distribution is correct: [Failed]
*** Failed! Insufficient coverage (after 100 tests):
Only 0% Length 3, but expected 90%
如消息所述，它预计 90% 的 Length 3 个案例，但得到了 0%。
同样，在 TDD 之后，可以尝试解决直接错误：
rints :: IO [Int]
rints = return [1,2,3]
但是，这会导致此测试失败：
Length is and distribution is correct: [Failed]
*** Failed! Insufficient coverage (after 400 tests):
100.0% Length 3
Only 0.0% Length 4, but expected 10.0%
属性 预计 10% Length 4 个案例，但得到了 0%。
也许以下是可能可行的最简单的方法？
import System.Random.Stateful
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
if 10 < p then return [1,2,3] else return [1,2,3,4]
可能不像您期望的那样随机，但它通过了所有测试。
更多三分球
最终（明确的）要求是 3 应该出现 50% 的次数。那是另一个分布 属性:
testProperty "3 appears 50% of the times" $ \() -> ioProperty $ do
actual <- rints
return $
checkCoverage $
cover 50 (3 `elem` actual) "3 present" $
cover 50 (3 `notElem` actual) "3 absent"
True -- Base property, but really, the distribution is the test
运行 所有测试都会导致此测试失败：
3 appears 50% of the times: [Failed]
*** Failed! Insufficient coverage (after 100 tests):
100% 3 present
Only 0% 3 absent, but expected 50%
毫不奇怪，它说 3 present 情况发生的概率为 100%。
本着 TDD 的精神（也许有点散漫，但它说明了正在发生的事情），您可以尝试像这样修改 rints：
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
if 10 < p then return [1,2,3] else return [1,2,4,5]
然而，这不起作用，因为分布仍然是错误的：
3 appears 50% of the times: [Failed]
*** Failed! Insufficient coverage (after 100 tests):
89% 3 present
11% 3 absent
Only 11% 3 absent, but expected 50%
也许以下是最简单的方法。这就是我的选择，至少：
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
includeThree <- uniformM globalStdGen
if 10 < p
then if includeThree then return [1,2,3] else return [1,2,4]
else if includeThree then return [1,2,3,4] else return [1,2,4,5]
不优雅，它仍然不产生随机数，但它通过了所有测试。
随机数
虽然上面涵盖了所有明确规定的要求，但显然不能令人满意，因为它并没有真正产生 1 到 10 之间的随机数。
这是典型的 TDD 过程。当您编写测试和 SUT 并让两者交互时，您会发现需要的测试比您原先想象的要多。
老实说，我不确定 'force' 生成 0 到 10 之间所有数字的最佳方法是什么。现在我有了 hammer 分布 tsts，我写了以下内容：
testProperty "All numbers are represented" $ \() -> ioProperty $ do
actual <- rints
return $
checkCoverage $
cover 5 ( 0 `elem` actual) " 0 present" $
cover 5 ( 1 `elem` actual) " 1 present" $
cover 5 ( 2 `elem` actual) " 2 present" $
cover 5 ( 3 `elem` actual) " 3 present" $
cover 5 ( 4 `elem` actual) " 4 present" $
cover 5 ( 5 `elem` actual) " 5 present" $
cover 5 ( 6 `elem` actual) " 6 present" $
cover 5 ( 7 `elem` actual) " 7 present" $
cover 5 ( 8 `elem` actual) " 8 present" $
cover 5 ( 9 `elem` actual) " 9 present" $
cover 5 (10 `elem` actual) "10 present"
True -- Base property, but really, the distribution is the test
我承认我对此并不完全满意，因为它似乎无法 'scale' 解决函数图像大得多的问题。我愿意接受更好的选择。
我也不想对每个数字的确切分布过于具体。毕竟，3 会比其他人更频繁地出现。因此，我只选择了一小部分（5%）来表示每个数字应该不会出现太少。
到目前为止，rints 的实施以与其他分发测试相同的方式未能通过此新测试。
粗略地说，我将实现更改为：
rints :: IO [Int]
rints = do
p <- uniformRM (1 :: Int, 100) globalStdGen
let l = if 10 < p then 3 else 4
ns <- shuffle $ [0..2] ++ [4..10]
includeThree <- uniformM globalStdGen
if includeThree
then do
let ns' = take (l - 1) ns
shuffle $ 3 : ns'
else
return $ take l ns
虽然我觉得还有改进的余地，但它通过了所有测试并实际生成了随机数：
ghci> rints
[5,2,1]
ghci> rints
[9,2,10]
ghci> rints
[8,1,3]
ghci> rints
[0,9,8]
ghci> rints
[0,10,3,6]
此示例使用了 QuickCheck with Haskell，但大部分想法都翻译成其他语言。 QuickCheck 的 cover 函数可能是该规则的一个例外，因为我不知道它已被移植到通用语言实现中，但也许我只是落后于曲线。
在 cover 之类的东西不可用的情况下，您必须编写一个测试，循环遍历足够多的随机生成的测试用例，以验证分发是否符合要求。多一点工作，但并非不可能。
I would like to try out test-driven development, but the project I am working on involves a lot of randomness
你应该意识到“随机性”在一个相当尴尬的地方影响了 TDD，所以它不是最直接的“try-it-out”项目。
有两个问题 - 一个是“随机性”是一个非常昂贵的断言：
您如何可靠地区分此实现和“真正的”随机数生成器，后者恰好在更改为其他数字之前发出有限的 4 序列？
因此我们可以在实际上不表达我们所有约束的稳定测试或偶尔报告不正确结果的更精确测试之间做出选择。
这里的一种设计方法是倾向于“可测试性”——在我们界面的外观背后是一个将通用随机位源与 确定性 函数相结合的实现将位序列映射到某个结果。
def randomListOfIntegers():
seed_bits = generalPurpose.random_bits()
return determisticFunction(seed_bits)
def deterministicFunction(seed_bits):
???
声称randomListOfIntegers“简单到明显没有缺陷”，所以我们可以通过检查来确定其正确性，并集中精力进行deterministicFunction的设计。
现在，我们 运行 进入第二个问题：seed_bits 到某些可观察结果的映射是任意的。大多数业务领域问题（例如：薪资系统）对于任何给定的输入都有一个单一的预期输出，但在随机系统中你仍然有一些额外的自由度。如果您编写的函数在给定任何位序列的情况下都能产生可接受的答案，那么我的函数（将这些位取反然后调用您的函数）也将产生可接受的答案——即使我的答案和您的答案不同。
实际上，如果我们想要一套测试在代码更改导致行为变化时发出警报，那么我们必须发明我们想要锁定的行为规范。
除非我们很好地猜测哪些任意行为将支持干净的实现，否则这可能会非常痛苦。
（或者，我们只依靠我们的“验收”测试池，它忽略切换到不同的任意行为的代码更改——它一直在权衡取舍）。
我们可能会考虑的一种更简单的实现方式是将 seed_bits 视为一系列候选响应的索引
def deterministicFunction(seed_bits):
choices = ???
n = computeIndex(seed_bits, len(choices))
return choices[n]
这暴露了另一个问题：k seed_bits 表示 2^k 个自由度；除非 len(choices) 恰好是 2 的幂并且不大于 2^k，否则在选择时会有一些偏差。您可以通过为 k 选择足够大的值来使偏差误差任意小，但是您不能用有限的位数来消除它。
进一步分解问题，我们可以将工作分为两个部分，一个负责生成候选人库，另一个负责实际选择其中一个。
def deterministicFunction(seed_bits):
return choose(seed_bits, weighted_candidates())
def choose(seed_bits, weighted_candidates):
choices = []
# note: the order of elements in this enumeration
# is still arbitrary
for candidate, weight in weighted_candidates:
for _ in range(weight):
choices.add(candidate)
# technically, this is also still arbirary
n = computeIndex(seed_bits, len(choices))
return choices[n]
在这一点上，我们可以决定使用“可能工作的最简单的东西”来实现computeIndex（如果你愿意，请先测试），这个新的weighted_candidates()功能也很容易进行测试，因为它的每次测试都只是“计算候选人并确保问题约束被整个人口所满足”。 choose 可以使用更简单的人群作为输入进行测试。
这种实现可能不尽如人意 - 毕竟，我们正在构建候选数据结构，然后是另一个选择，只能选择一个。这可能是我们能做的最好的。但是，通常可以采用不同的实现方式。
实际上，问题说明为我们定义了（加权的）响应总体的大小。换句话说，len(choices) 实际上是一些常量 L.
choices = [ generate(n) for n in range(L)]
n = computeIndex(seed_bits, L)
return choices[n]
这又可以简化为
n = computeIndex(seed_bits, L)
return generate(n)
也就是说，如果我们可以计算哪个响应排在第n位，我们就不需要传递一堆数据结构。
请注意，虽然 generate(n) 仍然具有任意行为，但我们可以对数据结构 [generate(n) for n in range(L)].
稍微重构一下，我们可能会
def randomListOfIntegers():
seed_bits = generalPurpose.random_bits()
n = computeIndex(seed_bits, L)
return generateListOfIntegers(n)
请注意，这个骨架并不是从写出一堆测试和重构中“出现”的，而是从思考问题和我们需要考虑的选择中“出现”的，以便“控制决策之间的差距”和反馈”。
将其称为“尖峰”可能比较公平 - 我们用来更好地理解我们要解决的问题的沙盒练习。
The same number doesn’t appear twice
了解组合学 会有所帮助。
基本思路：我们可以计算集合 [0,1,2,3,4,5,6,7,8,9,10] 的 4 个唯一元素的所有可能排列的集合，并且我们可以使用一种称为 squashed ordering 的技术来生成它们的特定子集。
在这里，我们可能想要处理规范al case of 3 更仔细一点。粗略的骨架看起来像
def generateListOfIntegers(n):
other_numbers = [0,1,2,4,5,6,7,8,9,10]
has3, hasLength3, k = decode(n)
if has3:
if hasLength3:
# 45 distinct candidates
assert 0 <= k < 45
return [3] ++ choose(other_numbers, 2, k)
else:
# 120 distinct candidates
assert 0 <= k < 120
return [3] ++ choose(other_numbers, 3, k)
else:
if hasLength3:
# 120 distinct candidates
assert 0 <= k < 120
return choose(other_numbers, 3, k)
else:
# 210 distinct candidates
assert 0<= k < 210
return choose(other_numbers, 4, k)
其中 choose(other_numbers, j, k) returns other_numbers 的 kth 子集具有 j 个总元素，并且 decode(n) 具有必要的逻辑以确保人口权重是正确的。
choose的行为是任意的，但是子集的进展有一个“自然”顺序（即，您可以对它们进行“排序”），因此任意使用排序顺序是合理的。
可能还值得注意的是，choose 是非常通用的 - 我们传入的列表可以是任何内容，它并不关心您如何处理答案。与 decode 相比，我们对“正确”行为的定义与 generateListOfNumbers 的消费紧密相关。
您可能想要查看 Peter Seiber 的 Fischer Chess Exercise, to see the different approaches people were taking when TDD was new. Warning, the threading is horribly broken now, so you may need to sift through multiple threads 以找到所有好的部分。
首先，TDD 的方法不止一种，因此没有唯一的正确答案。但这是我对此的看法：
您提到您不需要测试精确的统计分布，但我认为您必须这样做。否则，编写满足您的测试的最简单代码将导致完全确定的 non-random 解决方案。 （如果你在不考虑随机性的情况下查看你的需求，你会发现你可以使用一个简单的循环和很少的 if 语句来满足它们）。但显然，这不是您真正想要的。因此，在您的情况下，您必须编写一个测试来检查算法的统计分布。
此类测试需要收集被测功能的许多结果，因此可能会很慢，因此有些人会认为这是一种不好的做法，但恕我直言，这是您实际测试您真正关心的内容的唯一方法。
假设这不仅仅是一个理论练习，您可能还想将结果保存到一个文件中，您以后可以手动检查（例如使用 Excel），检查结果的其他统计属性，并可能相应地添加或调整您的测试。