V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
lxl1531
V2EX  ›  Python

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

  •  
  •   lxl1531 · 2021-03-07 17:19:40 +08:00 · 2695 次点击
    这是一个创建于 1117 天前的主题,其中的信息可能已经有所发展或是发生改变。
    大佬们,面试时碰到这个问题,面试官问列表有 100W 个字符串元素,怎么更快的把它们拼成一个长串?

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

    然后面试官问我,怎么自己写个函数实现 join()的功能,我想了很久没想出来,请教大佬们这个问题何解
    17 条回复    2021-03-10 11:53:59 +08:00
    infun
        1
    infun  
       2021-03-07 17:28:08 +08:00
    for 的本质是不断调用 next()
    所以用生成器应该可以吧
    geelaw
        2
    geelaw  
       2021-03-07 17:33:57 +08:00 via iPhone   ❤️ 1
    是有更多“临时对象”所以才慢。定量考虑的话,join 需要 N 的时间时,朴素累加可能需要 N^2 的时间,我能想到的最快的累加也可能会需要 NlogN 的时间。

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

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

    如果只是希望实现相同的功能,不论时间,则用平衡分组连接比较好,这只需要 NlogN 的时间。
    BingoXuan
        3
    BingoXuan  
       2021-03-07 17:34:22 +08:00 via Android
    只能想到用 reduce
    westoy
        4
    westoy  
       2021-03-07 17:38:46 +08:00
    mmap?
    wangxn
        5
    wangxn  
       2021-03-07 17:41:54 +08:00 via iPhone
    这种函数肯定是用 C 实现的吧。基本思路是先分配需要的空间,然后把字符串数组一个个地往空间里面填。不过 Python 很难做到高效,否则不会用 C 来实现。
    des
        6
    des  
       2021-03-07 17:44:29 +08:00 via iPhone
    大概是字符串不可变导致的?
    每一次拼接就需要分配内存全部拷贝一次,如果是这样的话,解决方法自然就有了
    把内存提前准备好,避免拷贝或者少拷贝
    Vegetable
        7
    Vegetable  
       2021-03-07 18:05:30 +08:00
    也许是 ctypes.create_string_buffer(length)
    MicroBotter
        8
    MicroBotter  
       2021-03-07 18:43:18 +08:00
    Cpython 的源码库

    cpython/Objects/stringlib/join.h
    LeeReamond
        9
    LeeReamond  
       2021-03-07 18:56:23 +08:00 via Android
    我觉得这是很无聊的问题,因为并不存在许多解法,join 不行就 for,再不行 fstring,再不行直接进 c 改。这类属于实际开发中你会意识到这个问题,但你不会记住,因为可以通过简单实验得到结论。面试问这种也是面试造火箭的体现
    jimrok
        10
    jimrok  
       2021-03-07 19:36:02 +08:00
    面试实际是看你逻辑性是不是更好,表达是不是清晰。
    BiteTheDust
        11
    BiteTheDust  
       2021-03-07 19:39:11 +08:00
    我觉得你可以参考 C++中 vector 的扩容机制
    ipwx
        12
    ipwx  
       2021-03-07 19:45:55 +08:00
    1. 扫描 100W 个字符串,计算总长度。
    2. 申请这么长的内存。(这个不知道 python 怎么搞,大不了用 C++ 给面试官写
    3. 对每个字符串 dst[offset:offset+n[i]] = s[i](伪代码)
    zyb201314
        13
    zyb201314  
       2021-03-07 20:06:24 +08:00 via Android
    join()会不会先计算整个列表需要的空间,类似一次性申请足够空间合并所有字符串, 是否有字符串缓冲机制实现类似列表 append 就地增加字符串?
    而用 for 需要不断地申请字符串扩容和迁移,随着合并的字符串越多,迁移越来越慢.
    nalzok
        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
    geebos
        15
    geebos  
       2021-03-10 03:04:26 +08:00
    for 循环慢是因为字符串在 python 里面是常量,每次创建一个新的字符串都要重新分配内存,所以使用 for 循环的话因为每次循环都要创建一个新的字符串,所以会花费很多时间在内存分配上。

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

    可以遍历一遍字符串计算出需要的内存,一次分配好。或者像 #14 所说的每次把 buffer 翻倍,但是我觉得这样没必要,我们一般在所需内存不确定的时候才会使用这个方案,如果所需的内存是确定的话一次到位是更好地选择。
    geebos
        16
    geebos  
       2021-03-10 03:05:32 +08:00
    @geebos 补充一下,不仅仅是内存分配的时间,还有数据复制的时间
    ilikekotori
        17
    ilikekotori  
       2021-03-10 11:53:59 +08:00
    不知道是不是面试官想要的答案,可以用 io.StringIO 实现 join
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2940 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 15:12 · PVG 23:12 · LAX 08:12 · JFK 11:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.