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