文档章节

zg手册 之 python2.7.7源码分析(3)-- list 对象和 dict 对象

 东昕
发布于 2014/08/26 13:30
字数 1588
阅读 128
收藏 3

list 对象

list 对象的定义

list对象内部是使用数组实现,在数组中存储的是指针,指向要保存的对象。

allocated是list中数组的大小,ob_size是当前已经使用的数组大小。

typedef struct {
    // 可变长对象中有 ob_size,保存当前已经使用的数组大小
    PyObject_VAR_HEAD
    PyObject **ob_item; // 数组的指针
    Py_ssize_t allocated; // 分配的数组长度
} PyListObject;


list 对象的缓存

list对象有缓存机制,对象在释放时会保存到空闲缓存池,待下一次申请的时候使用。 缓存池可以缓存80个list对象,缓存池满的时候list对象直接释放。

从list对象的创建和销毁过程了解它的缓存机制(为了关注重点,代码被简化过)。

// 缓存池的大小定义
#define PyList_MAXFREELIST 80

// 创建新的list对象
PyObject* PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    size_t nbytes = size * sizeof(PyObject *);
    // 如果缓存有空闲,直接从缓存中分配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;
    }
    if (size <= 0)
        op->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;
}

// 销毁list对象
static void list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_SAFE_BEGIN(op)
    if (op->ob_item != NULL) {
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
    // 保存list对象到空闲的缓存
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}


list 的插入,删除,添加操作

list的内部实现是数组,所以在插入和删除的操作会引起内部元素的移动。在添加操作时,如果目前list对象分配的内存没有使用完,则直接在尾部追加。

看下list的插入和添加操作。

// 插入操作
int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return ins1((PyListObject *)op, where, newitem);
}

static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
    // 判断是否重新分配长度
    if (list_resize(self, n+1) == -1)
        return -1;

    // 寻找插入点
    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;

    // 移动元素
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

// 添加操作
int PyList_Append(PyObject *op, PyObject *newitem)
{
    if (PyList_Check(op) && (newitem != NULL))
        return app1((PyListObject *)op, newitem);
    PyErr_BadInternalCall();
    return -1;}static int app1(PyListObject *self, PyObject *v){
    Py_ssize_t n = PyList_GET_SIZE(self);

    assert (v != NULL);
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) == -1)
        return -1;

    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
}


list对象总结

  1. list对象内部有定量的缓存,提高创建list对象的速度

  2. list对象的插入,删除操作成本较高,不适宜频繁操作。

  3. append操作速度较快。


dict 对象

dict对象的定义

dict对象的实现内部是散列表,散列函数采用的开放地址法,理论上算法的时间复杂度是 O(1) 。

dict对象在散列表小于8的时候,使用对象内部数组 ma_smalltable 的内存。

// 内部数组空间,创建长度较小的散列时使用
#define PyDict_MINSIZE 8

// 散列表的数据项
typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;} PyDictEntry;// dict 对象struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  // 使用的计数 + 伪删除的dummy计数
    Py_ssize_t ma_used;  // 使用的计数

    Py_ssize_t ma_mask;

    PyDictEntry *ma_table; // 散列表内存指针
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE]; // 内部优化,散列表较小时的内存
};


dict对象的缓存

dict对象也有缓存机制,对象释放时保存到缓存池中,待下一次申请的时候使用。缓存池可以缓存80个dict对象,缓存池满的时候dict对象直接释放。

从dict对象的创建和销毁过程了解它的缓存机制(为了关注重点,代码被简化过)。

// 缓存池的大小定义
#define PyDict_MAXFREELIST 80

// 创建 dict 对象
PyObject* PyDict_New(void)
{
    register PyDictObject *mp;
    // 创建 dummy对象,在删除的时候占位使用
    if (dummy == NULL) { /* Auto-initialize dummy */
        dummy = PyString_FromString("<dummy key>");
        if (dummy == NULL)
            return NULL;
    }
    // 判断如果缓存有空闲,使用缓存中的 dict对象
    if (numfree) {
        mp = free_list[--numfree];
        assert (mp != NULL);
        assert (Py_TYPE(mp) == &PyDict_Type);
        _Py_NewReference((PyObject *)mp);
        if (mp->ma_fill) {
            EMPTY_TO_MINSIZE(mp);
        } else {
            INIT_NONZERO_DICT_SLOTS(mp);
        }
        assert (mp->ma_used == 0);
        assert (mp->ma_table == mp->ma_smalltable);
        assert (mp->ma_mask == PyDict_MINSIZE - 1);
    } else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL)
            return NULL;
        EMPTY_TO_MINSIZE(mp);
    }
    mp->ma_lookup = lookdict_string;

    return (PyObject *)mp;
}

// 释放dict的函数
static void dict_dealloc(register PyDictObject *mp)
{
    register PyDictEntry *ep;
    Py_ssize_t fill = mp->ma_fill;
    PyObject_GC_UnTrack(mp);
    Py_TRASHCAN_SAFE_BEGIN(mp)
    for (ep = mp->ma_table; fill > 0; ep++) {
        if (ep->me_key) {
            --fill;
            Py_DECREF(ep->me_key);
            Py_XDECREF(ep->me_value);
        }
    }
    if (mp->ma_table != mp->ma_smalltable)
        PyMem_DEL(mp->ma_table);
    // 如果缓存还有空闲空间,则缓存释放的 dict 对象
    if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
        free_list[numfree++] = mp;
    else
        Py_TYPE(mp)->tp_free((PyObject *)mp);
    Py_TRASHCAN_SAFE_END(mp)
}


开放地址散列表的主要查找算法

dict 对象散列查找算法,首先比较key是否相同,不相同则探测下一个位置,一直到找到元素,或者查找失败。在查找失败的时候,返回第一个可用的位置。

static PyDictEntry *lookdict(PyDictObject *mp, PyObject *key, register long hash)
{
    register size_t i;
    register size_t perturb;
    register PyDictEntry *freeslot;
    register size_t mask = (size_t)mp->ma_mask;
    PyDictEntry *ep0 = mp->ma_table;
    register PyDictEntry *ep;
    register int cmp;
    PyObject *startkey;

    // 查找散列位置
    i = (size_t)hash & mask;
    ep = &ep0[i];
    if (ep->me_key == NULL || ep->me_key == key)
        return ep;

    // 判断散列位置是否为删除后的占位对象
    if (ep->me_key == dummy)
        freeslot = ep;
    else {
        // 散列hash匹配,进一步查找
        if (ep->me_hash == hash) {
            startkey = ep->me_key;
            Py_INCREF(startkey);
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
            Py_DECREF(startkey);
            if (cmp < 0)
                return NULL;
            if (ep0 == mp->ma_table && ep->me_key == startkey) {
                if (cmp > 0)
                    return ep;
            }
            else {
                return lookdict(mp, key, hash);
            }
        }
        freeslot = NULL;
    }

    // 在探测链上寻找匹配项
    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = (i << 2) + i + perturb + 1;
        ep = &ep0[i & mask];
        if (ep->me_key == NULL)
            return freeslot == NULL ? ep : freeslot;
        if (ep->me_key == key)
            return ep;
        if (ep->me_hash == hash && ep->me_key != dummy) {
            startkey = ep->me_key;
            Py_INCREF(startkey);
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
            Py_DECREF(startkey);
            if (cmp < 0)
                return NULL;
            if (ep0 == mp->ma_table && ep->me_key == startkey) {
                if (cmp > 0)
                    return ep;
            }
            else {
                return lookdict(mp, key, hash);
            }
        }
        else if (ep->me_key == dummy && freeslot == NULL)
            freeslot = ep;
    }
    return 0;
}


dict 对象总结

  1. dict对象采用开放地址散列法。

  2. dict对象内部有定量的缓存,提高创建dict对象的速度。

  3. 对于长度较小的dict对象,直接使用对象内部的内存,无需二次分配内存,性能较好。


原文链接: zg手册 之 python2.7.7源码分析(3)-- list 对象和 dict 对象


© 著作权归作者所有

粉丝 12
博文 22
码字总数 16965
作品 0
浦东
架构师
私信 提问
zg手册 之 python2.7.7源码分析(5)-- python的作用域和名空间

在 python 中, module,作用域,名空间这几个概念与虚拟机的运行机制有紧密的联系, 这里先了解 module,作用域,和名空间,为后面分析虚拟机的运行做准备。 module 在python中一个文件对应...

东昕
2014/10/26
126
1
zg手册 之 python2.7.7源码分析(1)-- python中的对象

源代码主要目录结构 Demo: python 的示例程序 Doc: 文档 Grammar: 用BNF的语法定义了Python的全部语法,提供给解析器使用 Include: 头文件,在用c/c++编写扩展模块时使用 Lib: Python自...

东昕
2014/07/08
157
0
zg手册 之 python2.7.7源码分析(2)-- python 的整数对象和字符串对象

python 中的内置对象 python 中常用的内置对象有:整数对象,字符串对象,列表对象,字典对象。这些对象在python中使用最多,所以在实现上提供缓存机制,以提高运行效率。 整数对象 (PyIntOb...

东昕
2014/08/08
283
0
zg手册 之 python2.7.7源码分析(4)-- pyc字节码文件

什么是字节码 python解释器在执行python脚本文件时,对文件中的python源代码进行编译,编译的结果就是byte code(字节码) python虚拟机执行编译好的字节码,完成程序的运行 python会为导入的模...

东昕
2014/09/20
126
0
[Python源码学习]之对象创建与销毁

接前面Python源码笔记之内存管理,尝试看看Python的对象的创建与销毁。 Python的对象类型还挺多,在Python源码笔记之数据类型中试图列一个表出来,最终未果。 不敢贪多,看4个内建对象。 创建...

晨曦之光
2012/05/08
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

IT兄弟连 HTML5教程 HTML5表单 小结及习题

小结 HTML表单提交的方法有get方法和post方法,get方法的作用是从指定的资源请求数据,post方法的作用是向指定的资源提交要被处理的数据。HTML表单一直都是Web的核心技术之一,有了它我们才能...

老码农的一亩三分地
25分钟前
14
0
向maven工程中导入自己封装好的jar包方法

1.打开cmd窗口 输入并执行:mvn install:install-file -DgroupId=com.test   -DartifactId=ptest -Dversion=0.1  -Dfile=E:\test\test-0.1.0.jar    -Dpackaging=jar注:Dgr......

gantaos
27分钟前
3
0
【jQuery基础学习】09 jQuery与前端(这章很水)

本文转载于:专业的前端网站➨【jQuery基础学习】09 jQuery与前端(这章很水) 这章主要是将如何将jQuery应用到网站中,或者说其实就是一些前端知识,对于我这种后端程序来说其实还是蛮有用的...

前端老手
39分钟前
11
0
深度科技与金山云完成兼容互认证 共同促进我国软件生态发展

近日,深度科技与金山云完成兼容互认证工作,经双方共同严格测试,深度操作系统ARM服务器版软件V15与金山云分布式数据库软件DragonBase V1.0相互兼容、稳定运行,可以为企业级应用提供全面保...

后浪涛涛
40分钟前
8
0
Less导入选项

Less 提供了CSS @import CSS规则的几个扩展,以提供更多的灵活性来处理外部文件。 语法: @import (keyword) "filename"; 以下是导入指令的相关详情: reference,使用较少的文件但不输出。 ...

凌兮洛
56分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部