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

• 資深大佬 : infun

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

• 資深大佬 : geelaw

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

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

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

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

• 資深大佬 : BingoXuan

  只能想到用 reduce

• 資深大佬 : westoy

  mmap?

• 資深大佬 : wangxn

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

• 資深大佬 : des

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

• 資深大佬 : Vegetable

  也许是 ctypes.create_string_buffer(length)

• 資深大佬 : MicroBotter

  Cpython 的源码库

  cpython/Objects/stringlib/join.h

• 資深大佬 : LeeReamond

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

• 資深大佬 : jimrok

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

• 資深大佬 : BiteTheDust

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

• 資深大佬 : ipwx

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

• 資深大佬 : zyb201314

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

• 資深大佬 : nalzok

  每次把 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

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

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

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

• 資深大佬 : geebos

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

• 資深大佬 : ilikekotori

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