1

假设我有一个函数，我想分析运行时的确切步数：

def function(L):
    print ("Hello")
    i = 0                 # 1 step
    while i < len(L):     # 3 steps
        print (L[i] + 1)
        i += 2            # 2 steps
    print ("Goodbye")

我想知道打印语句是否算作一个步骤？

4

2 回答 2

6

在这种情况下，“步骤”不是一个定义明确的术语——正如pswaminathan 指出的那样，通常我们关心的不是精确的数值，而是更广泛意义上的数学行为：随着问题规模变大（在在这种情况下，如果您增加输入的大小L）执行时间是否保持不变？线性增长？二次方？成指数的？

显式计算步数可能是该分析的一部分——它可能是一种对算法进行直观处理的好方法。但是我们没有一致的方法来确定什么是“步骤”，什么不是。您可能正在查看代码行——但在 Python 中，例如，列表推导式可以在一行中表达一个长而复杂的循环。或者您可以计算 CPU 指令，但是使用一种充满抽象的高级语言，这非常困难。所以你选择一个启发式——在像你的例子这样简单的代码中，“每行代码的每次执行都是一个步骤”是一个不错的规则。在这种情况下，您肯定会计算打印语句。如果您想更深入一点，可以按照tobias_k 的建议查看字节码, 以了解 Python 语法背后的指令是什么样的。

但没有单一的商定规则。你提到它是为了家庭作业；在这种情况下，只有您的讲师知道他们希望您使用什么定义。也就是说，您的问题的简单答案很可能是“是的，打印语句很重要”。

于 2013-07-14T20:30:55.550 回答
4

如果您的任务是计算确切的步骤数，那么是的，print将计为一个步骤。但也请注意，您的第二步print至少需要三个步骤：列表访问、添加和打印。

事实上，print（和其他“原子”语句）实际上可能值得很多“步骤”，具体取决于您如何解释步骤，例如 CPU 周期等。这对您的分配来说可能是多余的，但准确地说，它可能是值得一看生成的字节码。尝试这个：

import dis
print dis.dis(function)

这将为您提供函数中或多或少的原子步骤的完整列表，例如，加载函数、将参数传递给该函数、从堆栈中弹出元素等。据此，即使您的第一个print步骤也值得三个步骤（在 Python 2.6 中）：

2           0 LOAD_CONST               1 ('Hello')
            3 PRINT_ITEM          
            4 PRINT_NEWLINE

如何解释：第一个数字 ( 2) 是行号（即，以下所有说明仅针对该行）；中心数字 ( 0) 是跳转标签（由例如 if 语句和循环使用），后面是实际指令 ( LOAD_CONST)；右列包含这些指令的参数 ( 'Hello')。有关更多详细信息，请参阅此答案。

于 2013-07-14T20:31:28.110 回答