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
Alerta
V2EX  ›  Python

Python 中的 List 是封装了顺序存储结构还是链表存储结构?

  •  
  •   Alerta · 2018-08-29 21:43:25 +08:00 · 6639 次点击
    这是一个创建于 2260 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近在重温大学的数据结构突然想到一个问题,我们平时在使用的 List 到底是封装了顺序存储结构还是单链还是其他的结构,毕竟每一种结构都有其使用场景

    另外想请教一下,Python 里面有相关的顺序存储结构或者链的相关库吗,可以方便直接拿来用的
    
    23 条回复    2018-09-03 18:00:32 +08:00
    dbow
        1
    dbow  
       2018-08-29 21:47:58 +08:00
    数组实现的
    zhengxiaowai
        2
    zhengxiaowai  
       2018-08-29 21:48:58 +08:00
    collections
    Alerta
        3
    Alerta  
    OP
       2018-08-29 21:51:58 +08:00
    @zhengxiaowai collections 没有链表的实现方式吧? https://docs.python.org/2/library/collections.html
    zhzer
        4
    zhzer  
       2018-08-29 22:04:00 +08:00 via Android
    结合顺序和链表的一种动态类型,类似 stl 的 vector
    bobuick
        5
    bobuick  
       2018-08-29 22:07:15 +08:00
    楼上说的没错 +1

    单单的数组当然不行了,py 是不是静态类型的。
    Alerta
        6
    Alerta  
    OP
       2018-08-29 22:49:33 +08:00
    @bobuick 最后一句你是想说 py 不是静态类型?
    d18
        7
    d18  
       2018-08-29 22:58:14 +08:00
    cpython 就是动态数组,一个 struct,里面有动态数组和类似 size,used 之类的属性。不够了就 realloc。
    jython 是用了 arraylist,其实也是动态数组。
    n2ex2
        8
    n2ex2  
       2018-08-29 23:16:22 +08:00 via Android
    肯定是链表,不然怎么 append。
    wwqgtxx
        9
    wwqgtxx  
       2018-08-29 23:31:01 +08:00
    @n2ex2 自己看看 python list 的实现,还真的不是链表
    https://github.com/python/cpython/blob/3.7/Include/listobject.h#L23
    wwqgtxx
        10
    wwqgtxx  
       2018-08-29 23:35:12 +08:00
    至于 append 怎么实现的,基本上就是和 c++的 vector 一样,开个大数组,不够用就再扩容呗
    https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L301
    扩容因子在这里定义的
    https://github.com/python/cpython/blob/3.7/Objects/listobject.c#L59

    @n2ex2
    Alerta
        11
    Alerta  
    OP
       2018-08-30 00:20:08 +08:00 via iPhone
    @wwqgtxx 老哥 看源码看得不是很明白 可以解释一下吗
    lance6716
        12
    lance6716  
       2018-08-30 00:53:25 +08:00 via Android
    @Alerta 哪里没看明白,不看异常检查的话就是调整 list 长度,调整引用计数,执行 append
    lance6716
        13
    lance6716  
       2018-08-30 01:01:57 +08:00 via Android
    @wwqgtxx 不是很明白扩容里面的 growth pattern 具体指什么,算不出这个序列
    wwqgtxx
        14
    wwqgtxx  
       2018-08-30 06:36:16 +08:00 via iPhone
    @lance6716 就是说他的容量递增永远是按照这个序列来
    0, 4, 8, 16, 25, 35, 46, 58, 72, 88,
    至于这个序列就是从 (newsize >> 3) + (newsize < 9 ? 3 : 6) 算出来的呀
    lance6716
        15
    lance6716  
       2018-08-30 09:49:09 +08:00 via Android
    我想错了…白打了这么多字就不删了,给不明白的同学看看

    初始化长度为 0,当想要 resize 为 1 的时候,实际 allocated 为 1+0+3=4
    resize 为 5,allocated 为 5+0+3=8
    resize 为 9,allocated 为 9+1+6=16
    resize 为 17,allocated 为 17+2+6=25
    @wwqgtxx
    zhengxiaowai
        16
    zhengxiaowai  
       2018-08-30 10:17:27 +08:00
    @Alerta deque
    bany
        17
    bany  
       2018-08-30 10:45:01 +08:00
    动态数组实现的。在 Python 中 list 的操作涉及到 list 长度改变的,在底层( CPython )中都会调用 list_resize(PyListObject *self, Py_ssize_t newsize) 这个方法,这个方法也是 list 长度改变的核心算法实现;如果是当前 list 的长度大于了之前申请的内存空间了,那么新的长度通过这个表达式得出 new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)(也就是#14 楼说的那个序列值),然后在动态申请内存;
    Alerta
        18
    Alerta  
    OP
       2018-08-30 10:48:18 +08:00
    @bany 那这个动态 list 的插入删除操作是用顺序结构还是用链式结构来实现的呀请问
    bany
        19
    bany  
       2018-08-30 11:12:20 +08:00   ❤️ 1
    @Alerta 这里是 list.insert 的实现,我把关键的实现挑出来:
    ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
    {
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;

    /* 这里重新计算长度 */
    if (list_resize(self, n+1) < 0)
    return -1;

    if (where < 0) {
    where += n;
    if (where < 0)
    where = 0;
    }
    if (where > n)
    where = n;
    /* items 可以理解为一个数组,items 这个数组里存放的是 PyObject 这样的结构体(也就是 Python 中的数据) */
    items = self->ob_item;
    /* where 是要插入的位置 */
    for (i = n; --i >= where; )
    /* 将要插入位置之后的元素往后移一位 */
    items[i+1] = items[i];
    Py_INCREF(v);
    /* 插入元素 */
    items[where] = v;
    return 0;
    }

    这里是通过数组实现的,也就是顺序结构。
    Alerta
        20
    Alerta  
    OP
       2018-08-30 14:43:58 +08:00
    @bany 要是我插入删除操作多的话,现在有没有一些库是支持链表实现的呀
    Alerta
        21
    Alerta  
    OP
       2018-08-30 14:47:35 +08:00
    为什么 Python 标准库没有内置链表的库??是因为 python 里面有什么神奇的地方吗
    Alerta
        22
    Alerta  
    OP
       2018-08-30 15:01:06 +08:00
    thautwarm
        23
    thautwarm  
       2018-09-03 18:00:32 +08:00
    python list 类似 arraylist,
    python 中链表实现多用 nested list/tuple.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2738 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 15:19 · PVG 23:19 · LAX 07:19 · JFK 10:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.