时间戳

首页 > 解决方案 > Python 字符串的两种实现与 unicode 整数等价物列表的计算时间差异很大的原因

python - Python 字符串的两种实现与 unicode 整数等价物列表的计算时间差异很大的原因

问题描述

我注意到以下两个 Python 实现中的后者，它返回 Unicode 字符串中每个字符的整数表示列表，它需要的计算时间比第一个要短得多。我不清楚发生这种情况的原因。第一个实现简单地遍历一个字符串，将每个字符转换为其 Unicode 整数表示：[ord(c) for c in string]. 第二个对字符串进行编码并转换为列表：list(string.encode())。

我用短字符串 进行了测试，Hello world!后一种方法的执行速度是初始方法的两倍。然后我用这个字符串重新测试，乘以 1000，即。Hello world!Hello world!..., 后一个实现的执行速度提高了 5 倍。然后我记录了一些数据并绘制了时间效率图，证明两者都在线性时间执行，但后者的执行速度更快。

效率1

这是一个缩小的图表，我在其中采样了较长的字符串：

效率2

标签： pythontime-complexity

解决方案

首先，比较这两者并不完全有用，因为它们除了 7 位 ASCII 字符串之外是不等价的：

>>> s = '☃'
>>> [ord(c) for c in s]
[9731]
>>> list(s.encode())
[226, 152, 131]

但假设它们是等价的，你会看到一些优化良好的 C 代码和一些纯 python 字节码评估之间的区别。

呼叫经过list(s.encode())三个“快速”操作：

  1. UTF8 编码（本质上是一个对非 ASCII 字符进行一点翻译的 memcpy）
  2. __iter__在字节对象上（基本上将底层 uint8s 产生为整数）
  3. 来自大小可迭代的列表__init__（沿着快速预分配路径）

然后缓慢归结为评估列表理解中的字节码所花费的时间以及随着列表的增长需要动态重建列表存储（列表理解不能利用此处的大小提示，并且必须反复LIST_APPEND依赖list's internal调整大小）

>>> def f(s):
...     return [ord(c) for c in s]
... 
>>> import dis
>>> dis.dis(f)
  2           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f1e5ade2b30, file "<stdin>", line 2>)
              2 LOAD_CONST               2 ('f.<locals>.<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_FAST                0 (s)
              8 GET_ITER
             10 CALL_FUNCTION            1
             12 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x7f1e5ade2b30, file "<stdin>", line 2>:
  2           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                12 (to 18)
              6 STORE_FAST               1 (c)
              8 LOAD_GLOBAL              0 (ord)
             10 LOAD_FAST                1 (c)
             12 CALL_FUNCTION            1
             14 LIST_APPEND              2
             16 JUMP_ABSOLUTE            4
        >>   18 RETURN_VALUE

通过查看可迭代对象并查看是否有大小提示（假设没有嵌套迭代或条件的简单 listcomps），人们可能会看到具有常见列表理解的优化机会——尽管据我所知，没有人在 cpython 中尝试过这样的优化

您很可能会在 pypy 之类的东西中看到相当等价的性能，其中 JIT 可能会注意到 listcomp 的大小提示，但是如果无法访问您的分析代码，我很难验证这个假设

推荐阅读