use*_*964 82 python string algorithm string-concatenation
我正在研究CTCI的一个问题.
第1章的第三个问题是你带一个字符串如
'Mr John Smith '
并要求您用以下内容替换中间空格%20:
'Mr%20John%20Smith'
作者在Python中提供了这个解决方案,称之为O(n):
def urlify(string, length):
'''function replaces single spaces with %20 and removes trailing spaces'''
counter = 0
output = ''
for char in string:
counter += 1
if counter > length:
return output
elif char == ' ':
output = output + '%20'
elif char != ' ':
output = output + char
return output
我的问题:
我理解这是从左到右扫描实际字符串的O(n).但是Python中的字符串不是不可变的吗？如果我有一个字符串,我用+操作符添加另一个字符串,它是否分配必要的空格,复制原始字符串,然后复制附加字符串？
如果我有一个n长度为1 的字符串集合,则需要:
1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2
或者是O(n ^ 2)时间,是吗？或者我错误地认为Python如何处理追加？
或者,如果你愿意教我如何钓鱼:我将如何为自己找到这个？我试图将谷歌作为官方消息来源我一直没有成功.我找到了https://wiki.python.org/moin/TimeComplexity但这对字符串没有任何意义.
use*_*ica 76
在CPython中,Python的标准实现,有一个实现细节,通常是O(n),在字节码评估循环调用的代码中++=实现,或者使用两个字符串操作数.如果Python检测到左参数没有其他引用,则调用realloc通过调整字符串的大小来尝试避免复制.这不是你应该依赖的东西,因为它是一个实现细节,因为如果realloc最终需要经常移动字符串,性能会降低到O(n ^ 2).
没有奇怪的实现细节,由于涉及的二次复制量,算法是O(n ^ 2).像这样的代码只有在带有可变字符串的语言中才有意义,比如C++,甚至在你想要使用的C++中也是如此+=.
njz*_*zk2 36
作者依赖于恰好在这里进行的优化,但不是明确可靠的.strA = strB + strC通常是O(n),发挥功能O(n^2).但是,确保整个过程非常容易O(n),使用数组:
output = []
# ... loop thing
output.append('%20')
# ...
output.append(char)
# ...
return ''.join(output)
简而言之,append操作是分摊的 O(1)(尽管你可以O(1)通过预先将数组预分配到正确的大小来使其变得强大),然后进行循环O(n).
然后join也是O(n),但这没关系因为它在循环之外.
cri*_*007 25
我在Python Speed上找到了这段文字>使用最好的算法和最快的工具:
字符串连接最好用
''.join(seq)一个O(n)进程完成.相反,使用'+'或'+='运算符可以导致O(n^2)进程,因为可以为每个中间步骤构建新的字符串.CPython 2.4解释器在某种程度上缓解了这个问题; 但是,''.join(seq)仍然是最好的做法