0

我正在使用 Python 来解决 Project Euler 问题。许多需要缓存过去计算的结果以提高性能，导致代码如下：

pastResults = [None] * 1000000
def someCalculation(integerArgument):
    # return result of a calculation performed on numberArgument
    # for example, summing the factorial or square of its digits
for eachNumber in range(1, 1000001)
    if pastResults[eachNumber - 1] is None:
        pastResults[eachNumber - 1] = someCalculation(eachNumber)
        # perform additional actions with pastResults[eachNumber - 1]

反复递减是否会对程序性能产生不利影响？有一个空的或虚拟的第零元素（因此从零开始的数组模拟从一开始的数组）会通过消除重复递减来提高性能吗？

pastResults = [None] * 1000001
def someCalculation(integerArgument):
    # return result of a calculation performed on numberArgument
    # for example, summing the factorial or square of its digits
for eachNumber in range(1, 1000001)
    if pastResults[eachNumber] is None:
        pastResults[eachNumber] = someCalculation(eachNumber)
        # perform additional actions with pastResults[eachNumber]

我也觉得模拟一个基于 1 的数组会使代码更容易理解。这就是为什么我不将范围从零for eachNumber in range(1000000)设为someCalculation(eachNumber + 1)不合逻辑的原因。

来自第零个空元素的额外内存有多重要？我还应该考虑哪些其他因素？我更喜欢不限于 Python 和 Project Euler 的答案。

编辑：应该is None代替is not None.

4

1 回答 1

3

并不是关于性能问题的真正答案，而是关于缓存先前计算的值的一般提示。执行此操作的常用方法是为此使用映射（Python dict），因为这允许使用更复杂的键而不仅仅是整数，如浮点数、字符串甚至元组。此外，如果您的密钥相当稀疏，您也不会遇到问题。

pastResults = {}
def someCalculation(integerArgument):
    if integerArgument not in pastResults:
        pastResults[integerArgument] = # calculation performed on numberArg.
    return pastResults[integerArgument]

此外，无需使用循环“按顺序”执行计算。只需为您感兴趣的值调用函数，该if语句将注意，当递归调用时，该函数仅对每个参数调用一次。

最终，如果你经常使用它（就像 Project Euler 的情况一样），你可以为自己定义一个函数装饰器，如下所示：

def memo(f):
    f.cache = {}
    def _f(*args, **kwargs):
        if args not in f.cache:
            f.cache[args] = f(*args, **kwargs)
        return f.cache[args]
    return _f

它的作用是：它接受一个函数并定义另一个函数，该函数首先检查是否可以在缓存中找到给定的参数，否则计算原始函数的结果并将其放入缓存中。只需将@memo注释添加到您的函数定义中，这将为您处理缓存。

@memo
def someCalculation(integerArgument):
    # function body

这是someCalculation = memo(someCalculation). 但是请注意，这并不总是很好。首先，参数必须是可散列的（没有列表或其他可变类型）；其次，如果您传递与结果无关的参数（例如，调试内容等），您的缓存可能会不必要地增长，因为所有参数都用作键。

于 2013-09-22T21:18:15.427 回答