Python中快速字符串修改

Question

这是一个部分理论性的问题：

我有一个字符串（比如说是UTF-8编码的），我需要修改它，让每个字符（不是字节）变成两个字符，比如：

"Nissim" becomes "N-i-s-s-i-m-"


"01234" becomes "0a1b2c3d4e" 

依此类推。我觉得简单地在循环中拼接字符串可能会太慢（这确实是个瓶颈，因为这个操作需要频繁进行）。

我可能会使用一个数组（提前分配好空间），或者尝试自己写一个C语言模块来处理这个问题。

有没有人对这种情况有更好的想法呢？

（注意，这个问题总是和多字节编码有关，必须解决UTF-8的问题），

哦，还有，我用的是Python 2.5，所以这里不能用Python 3的新特性。

谢谢

Answer 1

这可能是一个有效的Python解决方案：

s1="Nissim"
s2="------"
s3=''.join([''.join(list(x)) for x in zip(s1,s2)])

Answer 2

试着用re模块来构建结果。这个模块会在后台处理那些复杂的字符串连接，所以性能应该没问题。下面是一个例子：

 import re
 re.sub(r'(.)', r'\1-', u'Nissim')

 count = 1
 def repl(m):
     global count
     s = m.group(1) + unicode(count)
     count += 1
     return s
 re.sub(r'(.)', repl, u'Nissim')

Answer 3

@gnosis，注意那些好心的回复者说你应该测量时间：是的，你应该这样做（因为程序员的直觉在性能方面往往不太准确），但是，像所有提供的timeit示例那样只测量一个案例，忽略了一个重要的考虑因素——大O表示法。

你的直觉是对的：一般来说（虽然最近的Python版本在某些特殊情况下可以稍微优化一下，但效果有限），通过循环使用+=来构建字符串（或者使用reduce等）必须是O(N**2)，因为会产生很多中间对象的分配，并且不可避免地会重复复制这些对象的内容；而使用连接、正则表达式和上面回答中没有提到的第三种选择（cStringIO.StringIO实例的write方法）是O(N)的解决方案，因此除非你确切知道你要处理的字符串长度有合理的上限，否则这些才是值得考虑的方案。

那么，你处理的字符串长度上限是什么？如果你能给我们一个大概念，基准测试可以在代表性的长度范围内进行（例如，"大多数情况下少于100个字符，但有时可能几千个字符"将是一个很好的性能评估规范：换句话说，不需要非常精确，只要能反映你的问题空间即可）。

我还注意到，似乎没有人关注到你规格中的一个关键且困难的点：这些字符串是Python 2.5的多字节、UTF-8编码的str，插入必须发生在每个“完整字符”之后，而不是每个字节之后。大家似乎都在“循环遍历字符串”，这给的是每个字节，而不是你明确指定的每个字符。

在多字节编码的字节str中，实际上没有好的快速方法来“循环遍历字符”；最好的办法是.decode('utf-8')，得到一个unicode对象——处理这个unicode对象（在这里循环确实可以正确遍历字符！），然后在最后.encode回去。一般来说，最好的方法是始终使用unicode对象，而不是编码的str，在代码的核心部分；只有在输入输出时（如果必须，因为你需要与只支持字节字符串而不支持真正Unicode的子系统进行通信）才进行编码和解码。

所以我强烈建议你考虑这种“最佳方法”，并相应地重构你的代码：到处使用unicode，只有在必要时在边界处进行编码/解码。对于“处理”部分，使用unicode对象会让你比使用麻烦的多字节编码字符串开心得多！-)

编辑：忘了评论你提到的一个可能的方法——array.array。如果你只是追加到你正在构建的新数组的末尾，那确实是O(N)（一些追加会使数组超出之前分配的容量，因此需要重新分配和复制数据，但是，就像列表一样，适度的指数级过度分配策略允许append的时间复杂度摊销为O(1)，因此N次追加的时间复杂度为O(N)）。

然而，通过在数组中间重复insert操作来构建数组（就像列表一样）是O(N**2)，因为每次O(N)的插入都必须移动所有O(N)后面的项（假设之前存在的项数和新插入的项数是成比例的，这似乎符合你的具体要求）。

所以，一个array.array('u')，通过重复append操作（而不是 insert！-），是解决你问题的第四种O(N)方法（除了我之前提到的三种：join、re和cStringIO）——这些是值得基准测试的，等你澄清感兴趣的长度范围后，如我上面提到的。