 |
1
GlobalNPC Mar 7, 2021
for 的本质是不断调用 next()
所以用生成器应该可以吧 |
 |
2
geelaw Mar 7, 2021 via iPhone  1
是有更多“临时对象”所以才慢。定量考虑的话，join 需要 N 的时间时，朴素累加可能需要 N^2 的时间，我能想到的最快的累加也可能会需要 NlogN 的时间。
什么叫做“自己实现 join 的功能”？ 如果你要求相同的时间复杂度且不能用 Python 的 join 恐怕不行，因为 join 是 Python 自己实现的，可以想象它先算好最终长度，然后分配内存，最后写入数据。 如果只是希望实现相同的功能，不论时间，则用平衡分组连接比较好，这只需要 NlogN 的时间。 |
 |
3
BingoXuan Mar 7, 2021 via Android
只能想到用 reduce
|
 |
4
westoy Mar 7, 2021
mmap?
|
 |
5
wangxn Mar 7, 2021 via iPhone
这种函数肯定是用 C 实现的吧。基本思路是先分配需要的空间，然后把字符串数组一个个地往空间里面填。不过 Python 很难做到高效，否则不会用 C 来实现。
|
 |
6
des Mar 7, 2021 via iPhone
大概是字符串不可变导致的？
每一次拼接就需要分配内存全部拷贝一次，如果是这样的话，解决方法自然就有了 把内存提前准备好，避免拷贝或者少拷贝 |
 |
7
Vegetable Mar 7, 2021
也许是 ctypes.create_string_buffer(length)
|
 |
8
MicroBotter Mar 7, 2021
Cpython 的源码库
cpython/Objects/stringlib/join.h |
 |
9
LeeReamond Mar 7, 2021 via Android
我觉得这是很无聊的问题，因为并不存在许多解法，join 不行就 for，再不行 fstring，再不行直接进 c 改。这类属于实际开发中你会意识到这个问题，但你不会记住，因为可以通过简单实验得到结论。面试问这种也是面试造火箭的体现
|
 |
10
jimrok Mar 7, 2021
面试实际是看你逻辑性是不是更好，表达是不是清晰。
|
 |
11
BiteTheDust Mar 7, 2021
我觉得你可以参考 C++中 vector 的扩容机制
|
 |
12
ipwx Mar 7, 2021
1. 扫描 100W 个字符串，计算总长度。
2. 申请这么长的内存。（这个不知道 python 怎么搞，大不了用 C++ 给面试官写 3. 对每个字符串 dst[offset:offset+n[i]] = s[i]（伪代码） |
 |
13
zyb201314 Mar 7, 2021 via Android
join()会不会先计算整个列表需要的空间,类似一次性申请足够空间合并所有字符串, 是否有字符串缓冲机制实现类似列表 append 就地增加字符串?
而用 for 需要不断地申请字符串扩容和迁移,随着合并的字符串越多,迁移越来越慢. |
 |
14
nalzok Mar 7, 2021
每次把 buffer 的大小翻倍？这样可以把合并 N 个等长字符串的 amortized cost 从 O(N^2) 降低为 O(N)
参见： https://cs.stackexchange.com/questions/63752/amortized-time-cost-of-insertion-into-an-array-list |
 |
15
geebos PRO for 循环慢是因为字符串在 python 里面是常量，每次创建一个新的字符串都要重新分配内存，所以使用 for 循环的话因为每次循环都要创建一个新的字符串，所以会花费很多时间在内存分配上。
如果自己实现的话，问题的关键就是如何避免重复分配内存。 可以遍历一遍字符串计算出需要的内存，一次分配好。或者像 #14 所说的每次把 buffer 翻倍，但是我觉得这样没必要，我们一般在所需内存不确定的时候才会使用这个方案，如果所需的内存是确定的话一次到位是更好地选择。 |
 |
17
ilikekotori Mar 10, 2021
不知道是不是面试官想要的答案，可以用 io.StringIO 实现 join
|
Select Language