《Python源码剖析》读书笔记-4 List对象


第4章 Python中的List对象

  • List对象定义为

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements. The number
    * currently in use is ob_size.
    * Invariants:
    * 0 <= ob_size <= allocated
    * len(list) == ob_size
    * ob_item == NULL implies ob_size == allocated == 0
    * list.sort() temporarily sets allocated to -1 to detect mutations.
    *
    * Items must normally not be NULL, except during construction when
    * the list is not yet visible outside the function that builds it.
    */

    Py_ssize_t allocated;
    } PyListObject;
    • ob_size和allocated的区别在于,ob_size是当前List中使用到的元素个数,也就是List的实际长度;而allocated是List的容量,和STL中vector的capacity类似。所以有0<=ob_size<=allocated.
  • 创建list用PyList_New,其中也用到了缓冲池技术,与整数对象一样。而且所使用的链表都叫做free_list。这两个free_list定义在不同的.c文件中,并且用static关键字限定其作用域只在当前文件,所以没有命名冲突。

  • PyList_Insert里需要注意三点:

    • 在非末尾插入一个元素,会带来大量的元素拷贝操作,低效;
    • 插入时的下标处理了负数情况,所以python才可以支持arr.insert(-1,5)这种语法;
    • 插入时会调用到list_resize,在list_resize中,当list中预分配的内存不够时需要扩展内存,而当预分配的内存使用情况不足一半时,也会收缩内存。
  • PyList_SetItem与list_subscript的区别

    • PyList_SetItem是C API,不对下标做负数逆序处理;list_subscript对应了python中的__getitem__函数,可以从下面看出:

      1
      2
      3
      4
      5
      6
      static PyMethodDef list_methods[] = {
      {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
      {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
      ...
      {NULL, NULL} /* sentinel */
      };
    • 当在python源码中调用arr[-1]时,其实是调用了list_subscript函数,此函数会对输入的下标参数做负数逆序处理。

    • 所以在python源码中,可以放心的使用负数下标,而当我们利用python的C API写一些扩展时,则必须要保证传入PyList_SetItem中的下标参数不越界。

评论