笔记大全

Python列表和集合效率源码对比分析

更新时间：2023-08-03

前言

在Python中，列表和集合是两种常用的数据结构。列表是一个有序的可变容器，可以存储任意类型的元素，而集合是一个无序的可变容器，存储唯一的元素。在实际应用中，选择使用列表还是集合，需要根据具体的需求和场景来决定。本文将从效率的角度对比分析Python列表和集合的源码实现。

列表（list）的源码分析

Python的列表是通过动态数组实现的。在列表的源码实现中，可以看到一个叫做PyObject**的数组，用于存储列表中的元素。这个数组在Python的内存管理中与其他对象共享，可以动态调整大小以容纳更多的元素。在插入和删除元素时，列表会根据需要自动调整大小。经过测试，在末尾添加和删除元素的操作上，列表的效率是比较高的。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item; // 存储列表中的元素
    Py_ssize_t allocated; // 已分配的元素数量
} PyListObject;

集合（set）的源码分析

Python的集合是通过哈希表实现的。在集合的源码实现中，可以看到一个叫做setentry*的结构体，用于存储集合中的元素。这个结构体中有一个指针数组，每个指针指向一个bucket链表，用于处理哈希冲突。在对集合执行增删改查操作时，可以通过哈希计算快速定位到要操作的元素。由于哈希表的特性，集合在判断元素唯一性和查找操作上具有较高的效率。

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size; // 集合中元素的数量
    Py_hash_t hash; // 集合的哈希值
    setentry *table; // 指针数组，存储bucket链表的头节点指针
    Py_ssize_t mask; // 指针数组大小减一，用于计算哈希值
    Py_ssize_t used; // 已使用的bucket数量
    setentry *(*insert)(PySetObject *, PyObject *, Py_hash_t) // 插入元素操作
} PySetObject;

列表和集合的效率对比

根据列表和集合的源码分析，可以总结出以下几点列表和集合的效率对比： 1. 插入和删除操作：列表通过动态数组实现，在末尾插入和删除元素的操作具有较高效率，而集合通过哈希表实现，插入和删除操作的效率与哈希冲突的数量和哈希算法有关。通常情况下，集合的插入和删除操作效率较高。 2. 查找操作：列表在查找操作时需要遍历整个列表，时间复杂度为O(n)，而集合可以通过哈希计算快速定位到要查找的元素，时间复杂度接近O(1)。因此，集合在查找操作上具有较高的效率。 3. 元素唯一性：列表中可以存储重复的元素，而集合中的元素必须是唯一的。在判断元素唯一性时，集合通过哈希表进行快速查找，效率较高。总的来说，列表适合在需要保留元素的顺序和允许重复元素的场景下使用，而集合适合在需要判断元素唯一性和进行快速查找的场景下使用。在性能方面，集合在插入、删除和查找操作上通常具有较高的效率，而列表在一些特定的操作上可能更加高效。在实际应用中，根据不同的需求选择合适的数据结构可以提高程序的执行效率。

c语言编程笔录