python - Python中函数查找操作的时间复杂度是多少

Question

我想知道，由于一种常见的优化策略是将查找“缓存”在一个变量中，然后使用该变量调用方法/函数，查找操作的开销有多大？

这就是我所说的“缓存”查找的意思，以防它不是正确的术语:

class TestClass:

    def myMethod(self):
       printMethod = self.printMethod
       for i in range(0, 1000):
          printMethod(i)

    def printMethod(self, i):
       print i

Answer 1

节省的不是时间复杂度，而是实际时间。在命名空间中查找函数名只是在字典中查找键，这已经是 O(1)。查找对象的属性也是字典查找，同样是 O(1)。有一个用于按名称查找局部变量的优化操作码，但仍然不能比 O(1) 更快。

在您的示例中，查找 self.printMethod 查找本地 (self)，然后查找属性 (printMethod)。那是两次查找。如果您将它存储在本地，那么对本地变量 printMethod 的每次后续访问都只是一次查找，而不是两次。这仍然是 O(1)，但速度更快，因为它是一个更小的常量。

This question进一步讨论了名称查找在 Python 中的工作方式。