Python 的字符串拼接函数 join()是怎么实现的

大佬们，面试时碰到这个问题，面试官问列表有 100W 个字符串元素，怎么更快的把它们拼成一个长串?

我说用''.join()传入列表作拼接；然后面试官问为什么 join 比 for 循环内字符串一个一个累加要速度快，我说是因为累加会有额外的中间临时变量，导致性能损失。

然后面试官问我，怎么自己写个函数实现 join()的功能，我想了很久没想出来，请教大佬们这个问题何解

join

字符

面试

函数

17 条回复 • 2021-03-10 11:53:59 +08:00

infun

2021-03-07 17:28:08 +08:00

for 的本质是不断调用 next()
所以用生成器应该可以吧

geelaw

2021-03-07 17:33:57 +08:00 via iPhone

是有更多“临时对象”所以才慢。定量考虑的话，join 需要 N 的时间时，朴素累加可能需要 N^2 的时间，我能想到的最快的累加也可能会需要 NlogN 的时间。

什么叫做“自己实现 join 的功能”？

如果你要求相同的时间复杂度且不能用 Python 的 join 恐怕不行，因为 join 是 Python 自己实现的，可以想象它先算好最终长度，然后分配内存，最后写入数据。

如果只是希望实现相同的功能，不论时间，则用平衡分组连接比较好，这只需要 NlogN 的时间。

BingoXuan

2021-03-07 17:34:22 +08:00 via Android

只能想到用 reduce

westoy

2021-03-07 17:38:46 +08:00

mmap?

wangxn

2021-03-07 17:41:54 +08:00 via iPhone

这种函数肯定是用 C 实现的吧。基本思路是先分配需要的空间，然后把字符串数组一个个地往空间里面填。不过 Python 很难做到高效，否则不会用 C 来实现。

des

2021-03-07 17:44:29 +08:00 via iPhone

大概是字符串不可变导致的？
每一次拼接就需要分配内存全部拷贝一次，如果是这样的话，解决方法自然就有了
把内存提前准备好，避免拷贝或者少拷贝

Vegetable

2021-03-07 18:05:30 +08:00

也许是 ctypes.create_string_buffer(length)

MicroBotter

2021-03-07 18:43:18 +08:00

Cpython 的源码库

cpython/Objects/stringlib/join.h

LeeReamond

2021-03-07 18:56:23 +08:00 via Android

我觉得这是很无聊的问题，因为并不存在许多解法，join 不行就 for，再不行 fstring，再不行直接进 c 改。这类属于实际开发中你会意识到这个问题，但你不会记住，因为可以通过简单实验得到结论。面试问这种也是面试造火箭的体现

jimrok

2021-03-07 19:36:02 +08:00

面试实际是看你逻辑性是不是更好，表达是不是清晰。

BiteTheDust

2021-03-07 19:39:11 +08:00

我觉得你可以参考 C++中 vector 的扩容机制

ipwx

2021-03-07 19:45:55 +08:00

1. 扫描 100W 个字符串，计算总长度。
2. 申请这么长的内存。（这个不知道 python 怎么搞，大不了用 C++ 给面试官写
3. 对每个字符串 dst[offset:offset+n[i]] = s[i]（伪代码）

zyb201314

2021-03-07 20:06:24 +08:00 via Android

join()会不会先计算整个列表需要的空间,类似一次性申请足够空间合并所有字符串, 是否有字符串缓冲机制实现类似列表 append 就地增加字符串?
而用 for 需要不断地申请字符串扩容和迁移,随着合并的字符串越多,迁移越来越慢.

nalzok

2021-03-07 20:20:28 +08:00

每次把 buffer 的大小翻倍？这样可以把合并 N 个等长字符串的 amortized cost 从 O(N^2) 降低为 O(N)

参见： https://cs.stackexchange.com/questions/63752/amortized-time-cost-of-insertion-into-an-array-list

geebos

2021-03-10 03:04:26 +08:00

for 循环慢是因为字符串在 python 里面是常量，每次创建一个新的字符串都要重新分配内存，所以使用 for 循环的话因为每次循环都要创建一个新的字符串，所以会花费很多时间在内存分配上。

如果自己实现的话，问题的关键就是如何避免重复分配内存。

可以遍历一遍字符串计算出需要的内存，一次分配好。或者像 #14 所说的每次把 buffer 翻倍，但是我觉得这样没必要，我们一般在所需内存不确定的时候才会使用这个方案，如果所需的内存是确定的话一次到位是更好地选择。

geebos

2021-03-10 03:05:32 +08:00

@geebos 补充一下，不仅仅是内存分配的时间，还有数据复制的时间

ilikekotori

2021-03-10 11:53:59 +08:00

不知道是不是面试官想要的答案，可以用 io.StringIO 实现 join