时间戳

首页 > 解决方案 > 当 Python 中的字符串更改时，字符串 id 不会更改。将字符添加到字符串的复杂性

python - 当 Python 中的字符串更改时，字符串 id 不会更改。将字符添加到字符串的复杂性

问题描述

我认为 Python 字符串的 id 每次更改字符串后都必须更改。但我发现真正的行为是不同的。例如，并非输出下面的所有代码字符串都不同：

In [1]: s = 'a' 
   ...: for i in range(20): 
   ...:     print(id(s)) 
   ...:     s += 'a' 

Out[1]: 139687167358256
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687049975984
   ...: 139687066878640
   ...: 139687066878640
   ...: 139687066878640
   ...: 139687066878640
   ...: 139687066878640

这就是为什么我决定 Python 内核正在尝试优化代码并开始对内存中的字符串进行奇怪的操作。这个假设的另一个论据是常量 ID 与大小为 2 的幂的段一起使用：

In [2]: s = 'a' 
   ...: prev = id(s) 
   ...: count = 1 
   ...: for i in range(150): 
   ...:     s += 'a' 
   ...:     cur = id(s) 
   ...:     if cur != prev: 
   ...:         print(len(s), count) 
   ...:         count = 1 
   ...:     else: 
   ...:         count += 1 
   ...:     prev = cur 

Out[2]: 2 1
   ...: 16 14
   ...: 32 16
   ...: 48 16
   ...: 64 16
   ...: 80 16
   ...: 96 16
   ...: 112 16
   ...: 128 16
   ...: 144 16

但在这一切中还有另一件奇怪的事情。让我们看看随着字符串大小的增加，段大小会发生什么：

In [3]: s = 'a' 
   ...: prev = id(s) 
   ...: count = 1 
   ...: for i in range(10 ** 9): 
   ...:     s += 'a' 
   ...:     cur = id(s) 
   ...:     if cur != prev: 
   ...:         print(len(s), count) 
   ...:         count = 1 
   ...:     else: 
   ...:         count += 1 
   ...:     prev = cur 

Out[3]:
   ...: 2 1
   ...: 16 14
   ...: 32 16
   ...: 48 16
   ...: 64 16
   ...: 80 16
   ...: 96 16
   <...>
   ...: 448 16
   ...: 464 16
   ...: 472 8
   ...: 504 32
   ...: 536 32
   ...: 568 32
   ...: 600 32
   ...: 648 48
   ...: 1048 400
   ...: 1272 224
   ...: 1336 64
   ...: 1416 80
   ...: 1512 96
   ...: 1544 32
   ...: 1832 288
   ...: 1864 32
   ...: 1880 16
   ...: 1992 112
   ...: 2040 48
   ...: 2104 64
   ...: 2152 48
   ...: 2216 64
   ...: 39512 37296
   ...: 752776 713264
   ...: 753592 816
   ...: 1511352 757760
   ...: 3026872 1515520
   ...: 6057912 3031040
   ...: 6062008 4096
   ...: 6066104 4096
   ...: 6070200 4096
   <...>
   ...: 8396728 4096
   ...: 16797624 8400896
   ...: 16801720 4096
   <...>
   ...: 33537976 4096
   ...: 33542072 4096
   ...: 67088312 33546240
   ...: 67092408 4096
   ...: 67096504 4096
   ...: 67100600 4096
   ...: 67104696 4096
   ...: 67108792 4096
   ...: 67112888 4096
   ...: 134229944 67117056
   ...: 268464056 134234112
   ...: 536932280 268468224

最后，我们可以尝试近似将 char 添加到字符串末尾的复杂性。再一次，我想，在循环中向字符串添加 n 个字符的复杂性是 O(n^2)。但我的实验表明它是 O(n)：

In [4]: def foo(n): 
   ...:     c = time() 
   ...:     s = 'a' 
   ...:     for i in range(n): 
   ...:         s += 'a' 
   ...:     return time() - c 

In [5]: foo(10 ** 6) / foo(10 ** 3)                                                                                                                                                                                                                
Out[5]: 1124.5325443786983

我无法解释这种行为，尤其是当字符串变得足够长时。那么有人可以帮我解决这个问题吗？如有可能，请详细说明。

升级版：

  1. 元组似乎不会发生这种情况。它们的 id 在每次循环迭代时都会发生变化。

  2. 用值为 'a' 的变量替换字符串文字 'a' 不会改变常量 ID 的行为。所以不替换s += 'a'为s = s + 'a'. 但！替换s = s + 'a'为s = 'a' + s导致在每次循环迭代中更改 id。

  3. 在用变量调用替换“a”文字后，a我认为在循环体中添加函数调用可能会改变这种情况（因为函数可能对变量有副作用a）。a所以我试图在声明和s = s + a行之间调用“正式”函数（没有任何作用） 。它并没有什么不同。最后，我尝试将非恒定长度线添加到s，但随机长度：

In [4]: s = 'a' 
   ...: prev = id(s) 
   ...: count = 1 
   ...: for i in range(10 ** 8): 
   ...:     s = s + 'a' * randint(1, 100) 
   ...:     cur = id(s) 
   ...:     if cur == prev: 
   ...:         count += 1 
   ...:     else: 
   ...:         print(len(s), count) 
   ...:         count = 1 
   ...:     prev = cur 


Out[4]:
   ...: 37 1
   ...: 76 1
   ...: 154 1
   ...: 187 1
   ...: 268 1
   ...: 288 1
   ...: 305 1
   ...: 344 2
   ...: 380 1
   ...: 438 1
   ...: 527 1
   ...: 612 2
   ...: 639 1
   ...: 817 2
   ...: 888 2
   ...: 984 3
   ...: 1077 2
   ...: 1166 2
   ...: 1267 2
   ...: 1378 2
   ...: 1641 5
   ...: 1777 2
   ...: 2164 9
   ...: 2509 5
   ...: 2750 6
   ...: 3394 14
   ...: 3674 5
   ...: 4030 5
   ...: 4077 3
   ...: 4569 10
   ...: 4868 5
   ...: 5700 14
   ...: 6840 23
   ...: 8278 25
   ...: 136672 2541
   ...: 19397763 381558
   ...: 19398587 18
   ...: 19402713 84
   ...: 19406810 81
   ...: 19410889 81
   ...: 19415002 82
   ...: 19419075 83
   ...: 19423225 80
   ...: 19427293 70
   ...: 19431357 88
   <And so on...>
  1. 如果我们将使用s += 'a'但从s之后调用哈希函数，则 id 将在每次迭代中发生变化。

标签： pythonstringoptimizationtime-complexityimmutability

解决方案

假设您使用 Python 3，Python 语言未指定此行为。

实际上，Python 3 标准规定：

字符串是Unicode 代码点的不可变序列。[...] 也没有可变字符串类型，但str.join()或 io.StringIO可用于有效地从多个片段构造字符串。

从用户的角度来看，必须尊重可变性。但是，如果这不会引入有关 Python 标准的副作用，解释器可以使用一些技巧在内部重用对象。

关于id，Python 标准规定：

返回对象的“身份”。这是一个整数，保证在其生命周期内对于该对象是唯一且恒定的。具有非重叠生命周期的两个对象可能具有相同的 id() 值。

CPython 实现细节：这是对象在内存中的地址。

所以，诀窍是：id调用一次迭代的结果可能等于也可能不等于前一次迭代的结果。这是未定义的，因为所引用的对象s与前一次迭代中引用的对象不同（因为不再引用前一个字符串，它可以被释放并结束其生命周期）。

CPython 解释器在内部循环内存中的字符串对象以更快（主要是为了避免分配）。由此产生的副作用可能是更好的复杂性。但是，替代 Python 实现可能无法执行此技巧。例如，PyPy 不会。

因此，请使用str.join()orio.StringIO进行快速连接（如 Python 标准所述），不要依赖未定义的行为或 CPython 实现细节，因为这种行为可能会在解释器的未来版本中发生变化。

推荐阅读