当Python中字符串发生变化时，字符串id不会发生变化。在字符串中添加char的复杂性

Question

我以为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内核试图优化代码 并开始对内存中的字符串进行奇怪的操作。这个假设的另一个论据是，constant-ids是和大小为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

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

UPD:

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

2. 将字符串文字'a'替换为变量'a'并不会改变常量ids的行为。所以不替换 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...>

4. 如果我们用 s += 'a' 但是，如果调用哈希函数，从 s 之后，每次迭代时id都会改变。

Answer 1

假设你使用的是Python 3。这种行为不是由Python语言指定的.

事实上, Python 3标准规定:

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

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

关于 id, Python标准规定:

返回对象的 "身份"。这是个整数，保证是 "身份"。惟妙惟肖 在该对象的 辈子. 两个寿命不重叠的对象可以有相同的id()值。

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

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

CPython解释器内部回收内存中的字符串对象，以提高速度（主要是为了避免分配）。解释器内部循环使用字符串对象来提高速度（主要是为了避免分配）。副作用 是一个可能更好的复杂度。然而，其他的 Python 实现可能不会执行这个技巧。例如。PyPy不.

因此，请使用 str.join() 或 io.StringIO 用于快速连接(如Python标准规定的那样)，而不是依赖未定义的行为或CPython实现细节，如 这种行为可能会在未来版本的解释器中发生变化。.