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

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，默认情况下您的算法将像以前一样工作，除了它还会告诉您它使用了哪个种子。如果您有需要调试的错误，那么您只需使用生成错误的种子调用 init_rand，您将获得完全相同的行为，从而获得 100% 的重现性。