UDN-企业互联网技术人气社区

板块导航

浏览  : 970
回复  : 0

[资源分享] Python源码剖析—Set容器

[复制链接]
哥屋恩的头像 楼主
发表于 2016-10-28 13:16:17 | 显示全部楼层 |阅读模式
  Python的Set容器

  set与List对象相似,均为可变异构容器。但是其实现却和Dict类似,均为哈希表。具体的数据结构代码如下。

  1. typedef struct {
  2.     long hash;      /* cached hash code for the entry key */
  3.     PyObject *key;
  4. } setentry;
  5. /*
  6. This data structure is shared by set and frozenset objects.
  7. */
  8. typedef struct _setobject PySetObject;
  9. struct _setobject {
  10.     PyObject_HEAD
  11.     Py_ssize_t fill;  /* # Active + # Dummy */
  12.     Py_ssize_t used;  /* # Active */
  13.     /* The table contains mask + 1 slots, and that's a power of 2.
  14.      * We store the mask instead of the size because the mask is more
  15.      * frequently needed.
  16.      */
  17.     Py_ssize_t mask;
  18.     /* table points to smalltable for small tables, else to
  19.      * additional malloc'ed memory.  table is never NULL!  This rule
  20.      * saves repeated runtime null-tests.
  21.      */
  22.     setentry *table;
  23.     setentry *(*lookup)(PySetObject *so, PyObject *key, long hash);
  24.     setentry smalltable[PySet_MINSIZE];
  25.     long hash;                  /* only used by frozenset objects */
  26.     PyObject *weakreflist;      /* List of weak references */
  27. };
复制代码

  setentry是哈希表中的元素,记录插入元素的哈希值以及对应的Python对象。PySetObject是哈希表的具体结构:

  fill 被填充的键的个数,包括Active和dummy,稍后解释具体意思

  used 被填充的键中有效的个数,即集合中的元素个数

  mask 哈希表的长度的掩码,数值为容量值减一

  table 存放元素的数组的指针

  smalltable 默认的存放元素的数组

  当元素较少时,所有元素只存放在smalltable数组中,此时table指向smalltable。当元素增多,会从新分配内存存放所有的元素,此时smalltable没有用,table指向新分配的内存。

h.png


  哈希表中的元素有三种状态:

  active 元素有效,此时setentry.key != null && != dummy

  dummy 元素无效key=dummy,此插槽(slot)存放的元素已经被删除

  NULL 无元素,此插槽从来没有被使用过

  dummy是为了表明当前位置存放过元素,需要继续查找。假设a和b元素具有相同的哈希值,所以b只能放在冲撞函数指向的第二个位置。先删除a,再去查找b。如果a被设置为NULL,那么无法确定b是不存在还是应该继续探查第二个位置,所以a只能被设置为dummy。查找b的过程中,第一个位置为dummy所以继续探查,直到找到b;或者直到NULL,证明b确实不存在。

  Set中的缓存

  set中会存在缓存系统,缓存数量为80个_setobject结构。

  1. /* Reuse scheme to save calls to malloc, free, and memset */
  2. #ifndef PySet_MAXFREELIST
  3. #define PySet_MAXFREELIST 80
  4. #endif
  5. static PySetObject *free_list[PySet_MAXFREELIST];
  6. static int numfree = 0;
  7. static void
  8. set_dealloc(PySetObject *so)
  9. {
  10.     register setentry *entry;
  11.     Py_ssize_t fill = so->fill;
  12.     PyObject_GC_UnTrack(so);
  13.     Py_TRASHCAN_SAFE_BEGIN(so)
  14.     if (so->weakreflist != NULL)
  15.         PyObject_ClearWeakRefs((PyObject *) so);
  16.     // 释放每个setentry
  17.     for (entry = so->table; fill > 0; entry++) {
  18.         if (entry->key) {
  19.             --fill;
  20.             Py_DECREF(entry->key);
  21.         }
  22.     }
  23.     // 如果分配了内存存放setentry,则释放掉
  24.     if (so->table != so->smalltable)
  25.         PyMem_DEL(so->table);
  26.     // 缓存_setobject
  27.     if (numfree < PySet_MAXFREELIST && PyAnySet_CheckExact(so))
  28.         free_list[numfree++] = so;
  29.     else
  30.         Py_TYPE(so)->tp_free(so);
  31.     Py_TRASHCAN_SAFE_END(so)
  32. }
  33. }
复制代码


  freelist缓存只会对_setobject结构本身起效,会释放掉额外分配的存储键的内存。

  Set中查找元素

  set中元素查找有两个函数,在默认情况下的查找函数为set_lookkey_string。当发现查找的元素不是string类型时,会将对应的lookup函数设置为set_lookkey,然后调用该函数。

  1. static setentry *
  2. set_lookkey_string(PySetObject *so, PyObject *key, register long hash)
  3. {
  4.     register Py_ssize_t i;
  5.     register size_t perturb;
  6.     register setentry *freeslot;
  7.     register size_t mask = so->mask;
  8.     setentry *table = so->table;
  9.     register setentry *entry;
  10.     /* Make sure this function doesn't have to handle non-string keys,
  11.        including subclasses of str; e.g., one reason to subclass
  12.        strings is to override __eq__, and for speed we don't cater to
  13.        that here. */
  14.       
  15.     /*
  16.     * 元素不是string,设置lookup = set_lookkey并调用
  17.     */
  18.     if (!PyString_CheckExact(key)) {
  19.         so->lookup = set_lookkey;
  20.         return set_lookkey(so, key, hash);
  21.     }
  22.     // 元素是字符串
  23.     i = hash & mask;
  24.     entry = &table[i];
  25.     // 插槽为空,或者插槽上的key的内存地址与被查找一致
  26.     if (entry->key == NULL || entry->key == key)
  27.         return entry;
  28.     // 第一个插槽为dummy,需要继续调用冲撞函数查找
  29.     if (entry->key == dummy)
  30.         freeslot = entry;
  31.     // 第一个插槽为其他元素,检查是否相等
  32.     else {
  33.         if (entry->hash == hash && _PyString_Eq(entry->key, key))
  34.             return entry;
  35.         freeslot = NULL;
  36.     }
  37.     /* In the loop, key == dummy is by far (factor of 100s) the
  38.        least likely outcome, so test for that last. */
  39.     /* 第一个插槽为dummy,继续查找 */
  40.     for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
  41.         // 冲撞函数
  42.         i = (i << 2) + i + perturb + 1;
  43.         entry = &table[i & mask];
  44.         if (entry->key == NULL)
  45.             return freeslot == NULL ? entry : freeslot;
  46.         if (entry->key == key
  47.             || (entry->hash == hash
  48.             && entry->key != dummy
  49.             && _PyString_Eq(entry->key, key)))
  50.             return entry;
  51.         // 记录第一个为dummy的插槽,当key不存在是返回该插槽
  52.         if (entry->key == dummy && freeslot == NULL)
  53.             freeslot = entry;
  54.     }
  55.     assert(0);          /* NOT REACHED */
  56.     return 0;
  57. }
复制代码


  查找函数最后返回的插槽有三种情况:

  key存在,返回此插槽

  key不存在,对应的插槽为NULL,返回此插槽

  key不存在,对应的插槽有dummy,返回第一个dummy的插槽

  set_lookkey与此类似,只不过比较元素时需要调用对应的比较函数。

  set的重新散列

  为了减少哈希冲撞,当哈希表中的元素数量太多时需要扩大桶的长度以减少冲撞。Python中当填充的元素大于总的2/3时开始重新散列,会重新分配一个有效元素个数的两倍或者四倍的新的散列表。

  1. static int
  2. set_add_key(register PySetObject *so, PyObject *key)
  3. {
  4.     register long hash;
  5.     register Py_ssize_t n_used;
  6.     if (!PyString_CheckExact(key) ||
  7.         (hash = ((PyStringObject *) key)->ob_shash) == -1) {
  8.         hash = PyObject_Hash(key);
  9.         if (hash == -1)
  10.             return -1;
  11.     }
  12.     assert(so->fill <= so->mask);  /* at least one empty slot */
  13.     n_used = so->used;
  14.     Py_INCREF(key);
  15.     if (set_insert_key(so, key, hash) == -1) {
  16.         Py_DECREF(key);
  17.         return -1;
  18.     }
  19.     // 填充的元素 > 2/3 总数量
  20.     if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
  21.         return 0;
  22.     // 新分配的内存为2倍或者4倍有效元素的个数。
  23.     // 可以知道一般情况下,有效元素占新分配元素的 1/6
  24.     // 再占满一半才需要再次分配(2/3 - 1/6 = 1/2)
  25.     return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
  26. }
复制代码


  (完)

原文作者:Blog My Minds  来源:开发者头条
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部