Python中函数查找操作的时间复杂度是什么？

Question

我想知道，由于一种常见的优化策略是“缓存”变量内的查找结果，然后使用该变量调用方法/函数，那么查找操作的成本有多高？

这就是我所说的“缓存”查找结果的意思：

class TestClass:

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

    def printMethod(self, i):
       print i

- Deleteman

---

你是在问当这种方法被缓存时查找它的代价有多大，还是没有被缓存时的代价？ - BrenBarn

从大O表示法来看，它是O(1)。这是你想知道的吗？ - John Zwinck

我认为它们具有不同的时间复杂度，因为在计时两种方法时存在差异。 - Deleteman

Answer 1

节省的不是时间复杂度，而是实际时间。在命名空间中查找函数名只是在字典中查找键，已经是O(1)了。在对象上查找属性也是一个字典查找，同样是O(1)。有一种优化的操作码可以通过名称查找本地变量，但仍然不能比O(1)更快。

在您的示例中，查找self.printMethod首先查找本地变量（self），然后查找属性（printMethod）。那是两个查询。如果将其存储在本地，则每次访问本地变量printMethod时只需要一个查找，而不是两个。这仍然是O(1)，但速度更快，因为它是一个较小的常数。 这个问题有一些进一步讨论Python中名称查找的工作原理。

- BrenBarn

Answer 2

以下是您可以使用的代码来计算时间差：

http://pastebin.com/svBN5NZ9

以下是计时结果：

In [2]: %timeit Class1().runCached(10000)
1000 loops, best of 3: 1.74 ms per loop

In [3]: %timeit Class1().runNormal(10000)
100 loops, best of 3: 2.92 ms per loop

In [4]: %timeit Class10().runCached(10000)
1000 loops, best of 3: 1.7 ms per loop

In [5]: %timeit Class10().runNormal(10000)
100 loops, best of 3: 6.01 ms per loop

In [6]: %timeit Class100().runCached(10000)
1000 loops, best of 3: 1.7 ms per loop

In [7]: %timeit Class100().runNormal(10000)
10 loops, best of 3: 42.9 ms per loop

一般来说，缓存方法更快，方法查找时间取决于类继承层次的深度。

但请注意，如果您使用像pypy这样的跟踪JIT，则可能会得到不同的结果，因为跟踪实际上可能会为您缓存方法指针。

- ErikR

Answer 3

两个O(1)操作可能需要非常不同的时间。实例属性查找(self.printMethod)和本地变量都是O(1)，但本地变量访问被优化，因此不需要字典查找，所以速度更快。来看看在CPython中访问本地变量与实例变量的字节码:

>>> import dis
>>> class MyClass:
...   def printMethod(self):
...     pass
...   def code(self):
...     pm = self.printMethod
...     self.printMethod()
...     pm()
...
>>> dis.dis(MyClass.code)
  5           0 LOAD_FAST                0 (self)
              3 LOAD_ATTR                0 (printMethod)
              6 STORE_FAST               1 (pm)

  6           9 LOAD_FAST                0 (self)
             12 LOAD_ATTR                0 (printMethod)
             15 CALL_FUNCTION            0
             18 POP_TOP

  7          19 LOAD_FAST                1 (pm)
             22 CALL_FUNCTION            0
             25 POP_TOP
             26 LOAD_CONST               0 (None)
             29 RETURN_VALUE
>>>

您可以看到访问pm只需要一个简单的LOAD_FAST操作，它从本地堆栈帧中的固定数字偏移量加载值，而访问self.printMethod则需要额外的LOAD_ATTR操作。

当然，建立本地变量的值需要时间，因此必须多次使用它（如您代码示例中所示），才能看到任何性能上的好处。

正如@user5402所指出的，由于编译器的优化，您使用的实现方式可能会有所不同。

- holdenweb