对于超过 64 个字符的字符串，什么会影响 Python 的字符串比较性能？

27 人关注

我试图评估比较两个字符串是否会随着其长度的增加而变慢。我的计算表明，比较字符串应该花费一个摊销后的恒定时间，但我的Python实验产生了奇怪的结果。

下面是一个字符串长度（1到400）与时间的关系图，单位是毫秒。自动垃圾收集被禁用， gc.collect 在每次迭代之间运行。

我每次都要比较100万个随机字符串，按以下方式计算匹配度。在取所有测量时间的最小值之前，这个过程要重复50次。

for index in range(COUNT):
    if v1[index] == v2[index]:
        matches += 1
    else:
        non_matches += 1
是什么原因导致了长度64左右的突然增加？
Note:假设v1和v2是两个长度为n的随机字符串列表，COUNT是它们的长度，可以用下面的片段来尝试重现该问题。
timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
  "from __main__ import COUNT, v1, v2", number=50)
Further note:我做了两个额外的测试：用is而不是==来比较字符串，完全抑制了这个问题，而且性能大约是210ms/1M的比较。
既然有人提到了交互，我确保在每个字符串后面添加一个空白，这应该可以防止交互；这并没有改变什么。那么是不是除了打断之外还有其他原因呢？


           
            
             你也许应该包括Python的确切版本，以防它有什么不同。


           
            
             Mike Dunlavey
            
            ：


           
            
             由于字符串是随机的，比较过程几乎总是在第一个字符处停止。
             
              new
             
             摄取它们，用随机内容填充它们，等等。


           
            
             @MikeDunlavey:Python 不会在逐个字符的基础上比较字符串 - 它使用字符串的哈希值来进行比较。


           
            
             @Mike,我不是在为创作计时，只是在进行比较。


           
            
             我很难相信Y轴是正确的。它不应该用200
             
              milliseconds
             
             来比较两个长度为5的字符串。
             
              也许
             
             早在2012年的时候，就已经有了微秒的时间。在我的英特尔i7处理器（64位）上，超过25个字符需要不到一纳秒的时间（当它们匹配时，所以没有发生短路）。有些东西闻起来很不对劲......只要运行它，伙计们。
             
              %time 'asdfsdsfsadfdsf' == 'asdfsdsfsadfdsf'


         
          python


         
          string


         
          performance


         
          time-complexity


          
           
            
            
             Martijn Pieters
            
           
           
            发布于
            
            2012-09-29


          
           已采纳


          
           
            Python
            
             可以
            
            '实习'短字符串；将它们存储在一个特殊的缓存中，并重新使用该缓存中的字符串对象。
           
           
            然后，当比较字符串时，它首先会测试是否是同一个指针（例如，一个内部的字符串）。
           
           if (a == b) {
    switch (op) {
    case Py_EQ:case Py_LE:case Py_GE:
        result = Py_True;
        goto out;
// ...
只有当该指针比较失败时，它才会使用大小检查和memcmp来比较字符串。
通常只对标识符（函数名、参数、属性等）进行内部处理，但对在运行时创建的字符串值不进行内部处理。
另一个可能的罪魁祸首是字符串常量；代码中使用的字符串字面在编译时被存储为常量，并在整个过程中重复使用；同样，只创建一个对象，身份测试在这些对象上会更快。
对于不相同的字符串对象，Python测试等长、等首字符，然后在内部C字符串上使用memcmp()函数。如果你的字符串是not如果是在内部或其他方面重复使用相同的对象，所有其他的速度特性都归结为memcmp()函数。


           
            
             
              我以为是这样的，但我的机器上的互换模式似乎非常不规则：重复
              
               id('ss')
              
              会得到相同的结果，但重复
              
               id('ssssss')
              
              每次都会得到不同的结果。而重复
              
               id('sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss')
              
              也会得到同样的结果。你知道为什么吗？也许我应该把它作为一个单独的问题来问。


           
            
             
              在我的Python 2.7.3中，
              
               id('ss')
              
              每次都给出不同的结果，而在长字符串上的
              
               id('ssssss')
              
              和
              
               id
              
              始终返回相同的数字。


           
            
             
              @larsmans 我也在OS X上使用python 2.7.3。我不确定的是，"短字符串 "是否是内部的，而长字符串则不是。因为
              
               id(LONG_STRING)
              
              对于某些长度的字符串也会给我同样的结果。


           
            
             
              Martijn Pieters
             
             ：


           
            
             
              将字符串存储在一个变量中；替换并不总是使字符串不朽；它会为新的字符串重新使用内存地址。有时运行
              
               id('onestring')
              
              然后
              
               id('anotherstring')
              
              也会得到相同的内存地址。


           
            
             
              Martijn Pieters
             
             ：


           
            
             
              @larsmans:
              
               _
              
              被设置为
              
               id()
              
              的返回值，而不是你调用它的字符串字面。）


          
           
            
             我只是在胡乱猜测，但你问的是 "什么可能"，而不是什么会，所以这里有一些可能性。