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

Question

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

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

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

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

同时使用魔术命令%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)

使用魔术命令%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]: