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查找local(self)然后查找属性(printMethod).这是两次查找.如果将它存储在本地,那么对局部变量的每次后续访问printMethod只是一次查找而不是两次.那仍然是O(1),但它更快,因为它是一个较小的常数.

这个问题进一步讨论了名称查找在Python中的工作原理.