问题：

Python中的字符串更改时，字符串id不会更改。向字符串添加字符的复杂性

张承颜

2023-03-14

我认为每次更改字符串后，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

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

UPD：

将字符串文字“a”替换为值为“a”的变量不会改变常量ID的行为。因此，不能将s=a替换为s=a。但是用s='a替换s=s'a会导致每次循环迭代时更改id。

在用名为a的变量替换“a”字面值后，我认为将函数调用添加到循环体中可能会改变这种情况（因为函数可能会对变量产生副作用）。所以我尝试在声明和s=s之间调用“formal”函数（它没有任何作用）。这也没什么不同。最后，我尝试将非等长线添加到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个答案

从光启

2023-03-14

假设您使用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实现细节，因为该行为可能会在解释器的未来版本中发生变化。

类似资料：

python字符串连接不会更改字符串id[重复]

python中的字符串是不可变的对象。更改字符串应该会创建一个新对象，从而创建一个新id。出于某种原因，当我尝试执行一个简单的字符串连接时，有时id会改变，有时则不会。我注意到当我所做的更改很小时，它往往不会改变id，但这似乎不是一个足够好的解释。只是想知道为什么会发生这种情况。这是我闲置shell的截图。如果有人能解释一下，我会非常感激：） id有时更改，有时不更改的示例
在Python中更改字符串中的一个字符

问题内容： Python中替换字符串中字符的最简单方法是什么？例如：问题答案：不要修改字符串。与他们一起工作作为清单；仅在需要时才将它们转换为字符串。 Python字符串是不可变的（即无法修改）。有很多的原因。使用列表，直到你别无选择，然后将它们变成字符串。
字符串操作 - 改写字符串

SETRANGE key offset value 用value 参数覆写(overwrite)给定key 所储存的字符串值，从偏移量offset 开始。不存在的key 当作空白字符串处理。可以用作append：注意: 如果偏移量>字符长度, 该字符自动补0x00，注意它不会报错
更改Java字符串列表中的特定字符

背景故事：我需要根据我制作的字母表来排列单词。我之前做了大量的循环，但我从之前问题的答案中得到了一个想法，可以像这样映射它：所以词会变，苹果会变成苹果--- 这似乎覆盖了所有字符，因此输出为：我的大脑今天很模糊，我想我可以一直坚持到最后，直到找到某种解决方案，但这似乎不是一种有效的方法。有什么想法吗？此时，我从列表中提取一个单词，将其放入一个字符数组中，这样我就可以分别更改每个字符，然后
关于不可变字符串的更改ID

问题内容：关于id类型对象str（在python 2.7中）的某些事情使我感到困惑。该str类型是不可变的，因此我希望一旦创建它，它将始终具有相同的id。我相信我说的话不太好，所以我将发布一个输入和输出序列的示例。因此与此同时，它一直在变化。但是，在有一个指向该字符串的变量之后，情况发生了变化：因此，一旦变量保存了该值，它似乎就冻结了。确实，在和之后o，的输出再次更改。这是不相同的行
Java 7字符串-子字符串复杂性

直到Java6，我们在上有一个常量时间子字符串。在Java7中，为什么他们决定复制数组——并降低线性时间复杂度——而像这样的东西正是为此而准备的？

Python中的字符串更改时，字符串id不会更改。向字符串添加字符的复杂性

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档