在这种情况下，为什么使用查找表比计算它慢？

Question

我有两个函数，其中输入delta_E只能是3个可能的值，0、4、8。我的第一个函数使用numpy的指数函数直接计算它。你知道吗

def acceptance_prob(delta_E, beta):
    return np.exp(-delta_E*beta)

而我的第二个函数创建一个字典，预先计算3个不同的值：

def acceptance_prob2(delta_E, beta):
    prob = {i: np.exp(-i*beta) for i in range(0,9,4)}
    return prob[delta_E]

使用magic命令%timeit进行基准测试

%timeit -n 1000000 acceptance_prob(4,5)
3.02 µs ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit -n 1000000 acceptance_prob2(4,5)
10.9 µs ± 37.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

显示预计算的方法比使用np.exp()慢了3倍多，我不明白。据我所知，计算机语言通常使用泰勒级数展开来计算指数函数，所以预先计算它们并查找它们而不是每个循环都计算它们会更快吗？你知道吗

Answer 1

我不认为你是在用你认为的方式测试时间复杂性。第二个函数不仅仅是查找值。它预先计算三个值，然后查找其中一个。如果您在函数之前预计算值，然后将这些值传递给函数，您将更直接地测试查找时间。你知道吗

比如：

def acceptance_prob2(delta_E, prob):
    return prob[delta_E]

prob = {i: np.exp(-i*beta) for i in range(0,9,4)}
%timeit -n 1000000 acceptance_prob2(4, prob)

Answer 2

试试这个：

def acceptance_prob(delta_E, beta):
    return np.exp(-delta_E*beta)

PRECOMPUTED_BETA = 5
PRECOMPUTED_PROB = {i: np.exp(-i*PRECOMPUTED_BETA) for i in range(0,9,4)}
def acceptance_prob2(delta_E, beta):
    if beta==PRECOMPUTED_BETA:
        return PRECOMPUTED_PROB[delta_E]
    return acceptance_prob(delta_E, beta)

使用magic命令%timeit进行基准测试的结果是：

%timeit -n 1000000 acceptance_prob(4,5)
1.09 µs ± 9.66 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit -n 1000000 acceptance_prob2(4,5)
107 ns ± 0.322 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

但这是一个更普遍的解决方案：

In [15]: class Memoize:
    ...:     def __init__(self, f):
    ...:         self.f = f
    ...:         self.memo = {}
    ...:     def __call__(self, *args):
    ...:         if not args in self.memo:
    ...:             self.memo[args] = self.f(*args)
    ...:         #Warning: You may wish to do a deepcopy here if returning objects
    ...:         return self.memo[args]
    ...:

In [16]: @Memoize
    ...: def acceptance_prob3(delta_E, beta):
    ...:     return np.exp(-delta_E*beta)
    ...:

In [17]: %timeit -n 1000000 acceptance_prob3(4,5)
245 ns ± 1.19 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [18]: