如何可重复调试依赖随机算法的程序？

Question

我在寻找一些调试随机程序的一般原则，还有在Python中调试的具体指导。

比如，考虑下面这个在跳表中插入的实现：

#inserts key into the lowest level list and then promotes it upwards based on coin flips
    def insert(self,key):
        new_node = SkipListNode()
        new_node.val = key
        #insert in order in the lowest list
        self.orderedInsert(new_node,self.search(key,True))
        flip = random.randint(0,1)
        level = 0
        level_node= new_node
        #promote upwards based on coin flips
        while flip == 1:
            level_up_node = SkipListNode()
            level_up_node.val = key
            #see if an upper level exists, if not create it
            if(len(self.lists)-1<=level):
                ...
            #upper level exists, move back find the first element with an up
            #insert new node as it's next
            else:
                ...
            ...
            level +=1
            flip = random.randint(0,1)

这里的insert函数依赖于随机的抛硬币结果。所以这个函数里的错误很难发现，因为每次运行时可能会出现，也可能不会出现。那在这种情况下，我们该如何简化调试呢？

Answer 1

对于“我该如何调试一个随机算法”这个问题，简单来说：

首先，你要明白，random模块使用的随机数生成器其实是一个伪随机数生成器。它会用一个种子（也就是一个起始数字）来初始化自己，然后根据这个种子确定性地生成一个看起来随机的数字序列。如果用同样的起始数字重新初始化，它会生成完全一样的序列。

有了这个知识，我们可以查看random的文档，发现它允许你自己选择种子。文档里还告诉你它通常使用什么作为种子：https://docs.python.org/2/library/random.html#random.seed

所以，这里有一段代码，你可以把它放进你的随机算法里：

import os
import time
import random
def init_rand(seed=None):
    if seed is None:
        try:
            seed = os.urandom(8)
        except NotImplementedError:
            seed = time.time()
    print 'seed: %s' % seed
    random.seed(seed)

现在，如果你在运行随机算法之前总是调用init_rand，那么默认情况下，你的算法会和之前一样工作，只不过它还会告诉你用了哪个种子。如果你遇到需要调试的bug，你只需用产生这个bug的种子来调用init_rand，这样你就能得到完全相同的结果，确保你可以100%复现这个问题。