登录  /  注册

Python列表的长度调节方法(附代码)

不言
发布: 2018-12-12 10:24:06
转载
8786人浏览过

本篇文章给大家带来的内容是关于python列表的长度调节方法(附代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

Python 的列表(list)是一个非常灵活的数组,可以随意调整长度。正是因为这种便利,使得我们会情不自禁地去修改数组以满足我们的需求,其中相比于insert, pop 等等而言, append 用法更常见。

有像这样使用:

>>> test = []
>>> test.append(1)
>>> test.append({2})
>>> test.append([3])
>>> print test

# 输出 
[1, set([2]), [3]]
登录后复制

也有像这样使用的:

test = []

for i in range(4):
    test.append(i)
print test

# 输出 
[0, 1, 2, 3]
登录后复制

这样用很开心,也很满足。

但其实只要遇到能够动态修改数据长度场景,我们都应该马上反应过来一点,那就是内存管理的问题。

如果运行效率和便捷性同时满足的话,那简直就是大大的福音呀。

然而,上帝为你开启一扇窗的同时肯定也已经关上了一扇门了!

吝啬的初始化

深受预分配知识的熏陶,我们也是觉得 list 在初始化是有分配一定的长度的,要不然每次都申请内存那得多 ”low“ 啊。

然后实际上 list 真的就是这么 ”low“:

import sys

test = []
test_1 = [1]
print sys.getsizeof(test)
print sys.getsizeof(test_1) - sys.getsizeof(test)

# 输出 
72     # 空列表内存大小,也是 list 对象的总大小
8       # 代表增加一个成员,list 增加的大小
登录后复制

我们的猜测是,list 在定义之后,会预先分配好一个一定大小的池用来塞数据,以避免动不动就申请内存。

但是在上面的实验看出,一个成员的列表,比一个空列表,长度仅仅只是大了 8 字节,如果真的存在这样一个预分配的池,那么在预分配个数之内添加成员,两者的内存大小应该是保持不变才对。

所以可以猜测这块 list 应该是没有这样的一个预分配内存池。这里需要来个实锤

PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes;

    if (size  PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
        
    // list对象指针的缓存
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    
    // list 成员的内存申请
    nbytes = size * sizeof(PyObject *);
    if (size ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}
登录后复制

当我们在执行 test = [1] 时,实际上只做了两件事:

根据成员的数目,构建相应长度的空列表;(上述代码)

一个个将这些成员塞进去;

可能有童鞋会觉得,在塞成员的那一步,说不定会触发什么机制使它变大?

很可惜,因为初始化用的方法是 PyList_SET_ITEM, 所以这里是木有的触发什么机制,只是简单的数组成员赋值而已:

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
登录后复制

所以整个 list 的初始化,还真的就是木有预分配的内存池,直接按需申请,一个萝卜一个坑,实在得狠;

可变长的关键

初始化过程是这样还可以理解,如果运行中还这样的话,那就有点说不过去了。

试想下,在文章开头用  append 的例子中,如果每 append 一个元素就申请一次内存,那么list 可能要被吐槽到怀疑人生了, 所以很明显,在对于内存的申请,它还是有自己的套路的。

在 list 里面,不管是 insert 、pop 还是 append,都会遇到 list_resize,故名思义,这个函数就是用来调整 list 对象的内存占用的。

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    # 确定新扩展之后的占坑数
    new_allocated = (newsize >> 3) + (newsize  PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;

    # 申请内存
    items = self->ob_item;
    if (new_allocated ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}
登录后复制

在上面的代码中,频繁看到两个名词:newsize 和 new_allocated, 这里需要解释下,newsize 并不是 增加/减少 的个数,而是 增加/减少 之后的成员总数目。比方说:

a = [1, 2, 3]
a.append(1)
登录后复制

上面的 append 触发list_resize 时, newsize 是 3 + 1, 而不是 1;这边比较重要,因为在 pop 这类减少列表成员时候,就是传入缩减后的总数目。

在 list 的结构定义中,关于长度的定义有两个,分别是 ob_size(实际的成员数),allocated(总成员数)

它们之间的关系就是:

 0 <p>所以 new_allocated 就很好理解了,这个就是新的总坑数。</p><p>当名词含义理解得差不多时,我们就能顺藤摸瓜知道一个列表在list_resize 之后,大小会变成怎样?</p><p>方法其实从上面注释和代码都说得很明白了,这里再简单整理下:</p><p>先确定一个基数:new_allocated = (newsize &gt;&gt; 3) + (newsize </p><p>判断下 new_allocated + newsize 有没有超过  PY_SIZE_MAX, 如果超过了,直接报错;</p><p>最终确定新的总坑数是:new_allocated + newsize, 如果 newsize 是 0, 那么总坑数直接为 0 ;</p><p>下面演示下:</p><pre class="brush:php;toolbar:false">#coding: utf8
import sys

test = []
raw_size = sys.getsizeof(test)

test.append(1)
print "1 次 append 减去空列表的内存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "2 次 append 减去空列表的内存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "3 次 append 减去空列表的内存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "4 次 append 减去空列表的内存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "5 次 append 减去空列表的内存大小:%s " % (sys.getsizeof(test) - raw_size)

test.append(1)
print "6 次 append 减去空列表的内存大小:%s " % (sys.getsizeof(test) - raw_size)
登录后复制
# 输出结果
1 次 append 减去空列表的内存大小:32
2 次 append 减去空列表的内存大小:32
3 次 append 减去空列表的内存大小:32
4 次 append 减去空列表的内存大小:32
5 次 append 减去空列表的内存大小:64
6 次 append 减去空列表的内存大小:64
登录后复制

开始简单的代入法一步步算:

其中:

new_allocated =  (newsize >> 3) + (newsize 0)

当原allocated >= newsize 并且 newsize >=  原allocated  / 2 时,不改变  allocated 不申请内存直接返回

第 n 次 append 列表原长度 新增成员数 原 allocated newsize new_allocated
1 0 1 0 0 + 1 = 1 3 + 1 = 4
2 1 1 4 1 + 1 = 2 无需改变
3 2 1 4 2 + 1 = 3 无需改变
4 3 1 4 3 + 1 = 4 无需改变
5 4 1 4 4 + 1 = 5 3 + 5 = 8
6 5 1 8 5 + 1 = 6 无需改变

通过上面的表格,应该比较清楚看到什么时候会触发改变 allocated,并且当触发时它们是如何计算的。为什么我们需要这样关注 allocated?理由很简单,因为这个值决定了整个 list 的动态内存的占用大小;

扩容是这样,缩容也是照猫画虎。反正都是算出新的 allocated, 然后由 PyMem_RESIZE 来处理。

总结

综上所述,在一些明确列表成员或者简单处理再塞入列表的情况下,我们不应该再用下面的方式:

test = []

for i in range(4):
    test.append(i)
print test
登录后复制

而是应该用更加 pythonic 和 更加高效的列表推导式:test = [i for i in range(4)]。

以上就是Python列表的长度调节方法(附代码)的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:segmentfault网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号