我正在尝试用Python实现我自己的str.join
方法,例如:
''.join(['aa','bbb','cccc'])
返回'aabbbcccc'
。我知道使用join方法进行字符串连接将导致线性(结果的字符数)复杂性,我想知道如何做到这一点,因为在for循环中使用'+'
运算符将导致二次复杂性,例如:
res=''
for word in ['aa','bbb','cccc']:
res = res + word
由于字符串是不可变的,因此在每次迭代时复制一个新字符串,从而产生二次运行时间。然而,我想知道如何在线性时间内完成,或者找到''.join
是如何精确工作的
我在任何地方都找不到线性时间算法,也找不到str.join(iterable)的实现。非常感谢您的帮助
将
str
作为实际的str
连接是一种转移注意力的做法,而且not what Python itself does:Python操作可变的bytes
,而不是str
,这也消除了对know string internals的需要。具体来说,str.join
将其参数转换为字节,然后pre-allocates和mutates its result这直接对应于:
str
参数编码/解码到bytes
或从bytes
进行编码/解码的包装器len
求和bytesarray
来构造结果值得注意的是,虽然元素迭代和元素复制基本上是两个嵌套循环,但它们在不同的对象上进行迭代。该算法仍然只接触每个字符/字节三次/一次
相关问题 更多 >
编程相关推荐