python - 为什么 int(len(str(k))) 比循环 (while) 快

Question

我想知道为什么这个功能:

def digit(k):
    return len(str(k))

比这个快吗？ :

def digit(k):
    i = 0
    while k != 0:
        k = k // 10
        i += 1
    return i

为什么在 C 中是相反的？

Answer 1

让我们看看如果我们将您的 Python 代码尽可能逐字地翻译成 C 会发生什么。我们可以使用 Cython 轻松做到这一点:

# save this in a file named "testmod.pyx" and compile it with Cython and a
# C compiler - details vary depending on OS and Python installation

from libc.stdio cimport snprintf
from libc.string cimport strlen

def c_digit_loop(k_):
    cdef unsigned int k = k_
    cdef int i = 0
    while k != 0:
        k = k // 10
        i += 1
    return i

def c_digit_str(k_):
    cdef unsigned int k = k_
    cdef char strbuf[32] # more than enough for any 'unsigned int'
    snprintf(strbuf, sizeof(strbuf), "%u", k);
    return strlen(strbuf);

您从中获得的机器代码并没有达到最佳状态，但它已经足够接近以进行快速测试了。这使我们可以直接使用 timeit 比较性能，如下所示:

# save this in a file named 'test.py' and run it using the
# same CPython you compiled testmod.pyx against

import timeit
from testmod import c_digit_loop, c_digit_str

def py_digit_loop(k):
    i = 0
    while k != 0:
        k = k // 10
        i += 1
    return i

def py_digit_str(k):
    return len(str(k))

def test1(name):
    print(name, timeit.timeit(name+"(1234567)", "from __main__ import "+name,
                              number=10000))

test1("py_digit_loop")
test1("py_digit_str")
test1("c_digit_str")
test1("c_digit_loop")

当我运行这个程序时，这是我在计算机上输入的输出。我手动排列了数字，以便更容易通过肉眼进行比较。

py_digit_loop 0.004024484000183293
py_digit_str  0.0020454510013223626
c_digit_str   0.0009924650003085844
c_digit_loop  0.00025072999960684683

这证实了您最初的断言:循环比在 Python 中转换为字符串慢，但在 C 中则相反。但请注意，在 C 中转换为字符串仍然比在 Python 中转换为字符串更快。

要准确地知道为什么会发生这种情况，我们需要比我今天早上想做的更深入地挖掘 Python 解释器的内部结构，但我已经足够了解它的内部结构，可以在大纲。 CPython 解释器效率不高。即使对小整数的操作也涉及引用计数和在堆上构建临时对象。在 Python 中执行基本算术的循环每次迭代需要一个或两个临时对象(取决于 0、1、2 ……是否是“内部”)。通过转换为字符串并获取其长度来进行计算只涉及为整个计算创建一个临时对象，即字符串。与这些暂存对象相关的簿记工作使实际计算的成本相形见绌，对于这两种 Python 实现。

基于 C 字符串的实现执行的步骤几乎与基于 Python 字符串的实现执行的步骤完全相同，但它的暂存对象是堆栈上的 char 数组，而不是完整的 Python 字符串对象，这一切本身显然有利于 40-50% 的加速。

基于 C 循环的实现为实际循环编译为 8 条机器指令。没有内存访问。甚至没有硬件除法指令(这就是 strength reduction 的魔力)。然后还有数百条处理 Python 对象模型的指令。这 0.00025 秒中的大部分仍在开销。