python - 在 python 中进行字符串插入的有效方法？

Question

我目前正在编写一个解析器，用于检测一堆源文件中的某些标识符。这些标识符随后将通过添加前缀来重命名，以使其唯一。此重命名过程只能在处理完所有文件后发生，因为其中一些文件是链接的(例如，类和类的实例化需要获得相同的类标识符)。

此过程的第一步之一是暂时删除所有不必要的代码(字符串和括号内容 + 行/ block 注释)以使解析更容易且耗时更少。这些片段被切割存储在双端队列中，作为具有以下结构的命名元组:(索引，值)。在解析器和重命名器完成它们的工作后，这些片段被粘贴回原来的位置(由于文件更改而产生偏移)。

前面的代码处理得很快，但是当我尝试通过将所有修剪过的片段插入文件内容来重建文件时出现问题:

while self.trimmedCode:
    key, value = self.trimmedCode.pop()
    parsedContent = ''.join((parsedContent[:key],value,parsedContent[key:]))

一些文件包含大量字符串/注释，使得重建过程非常缓慢(150,000 次插入需要 6 分钟)。我的问题？我怎样才能使在索引处的插入更有效率？

由于字符串是不可变的，我试图通过在执行所有插入之前将字符串转换为字符列表来实现性能提升。这将 while 循环的速度提高了大约 10%。然而，随后的连接操作抵消了获得的优势:

charList = list(parsedContent)

while self.trimmedCode:
    key, value = self.trimmedCode.pop()
    charList[key:key] = value

parsedContent = ''.join(charList)

我的问题:是否有更有效的方法来完成这项任务(使用 Python 2.7)？

编辑:分析器统计

相关分析器统计数据:
信息:buildRenamedCopy 重建文件并包含 while 循环，其中 insertString 执行连接操作。此测试是在一组较小的文件(+- 600 个文件)上运行的

ncalls     tottime  percall  cumtime  percall filename:lineno(function)  
1284       9.998    0.008    137.834  0.107   file.py:146(buildRenamedCopy)  
180923     59.810   0.000    110.459  0.001   file.py:142(insertString)  
182213     50.652   0.000    50.657   0.000   {method 'join' of 'str' objects}  

Answer 1

您的代码缓慢的原因是插入到列表中是 O(N)(其中 N 是列表的长度)。这是因为列表中插入点之后的所有值都需要移动，以便为您插入的新值腾出空间。

您可以通过用新字符串(插入的值加上前一个字符)替换给定位置的现有值来解决此问题，而不是执行增加列表的切片赋值。这仅在每个 key 都小于之前的所有键时才有效(也就是说，如果您按降序遍历键)。

这是您的代码的最小修改版本，应该具有改进的渐近性能(从 O(N^2) 到 O(N)):

charList = list(parsedContent)

while self.trimmedCode:
    key, value = self.trimmedCode.pop()
    charList[key] = value + charList[key] # the change is here! No O(N) slice assignment!

parsedContent = ''.join(charList)

请注意，您可能还可以将 while 和 pop 替换为更简单明了的 for 循环:

for key, value in reversed(trimmedCode):

如果您使用生成器函数生成要连接成更大块的字符串序列，而不是将原始字符串拆分为单个字符，您可能会获得更好的性能。这不是渐进的性能变化，但可能会带来很大的常数因子改进。这是对此的尝试:

def insert_gen(orig_string, insertions):
    prev_key = 0
    for key, value in insertions:
        yield orig_string[prev_key:key] # yield text from the previous insert to this one
        yield value                     # yield the "inserted" text
        prev_key = key
    yield orig_string[prev_key:]        # yield trailing text (after last insert)

你会像这样使用它:

parsedContent = "".join(insert_gen(parsedContent, self.trimmedCode))