目录

人生苦短 | 字典和集合进阶-列表和元组的性能以及内部实现

字典和集合基础

字典是一系列由键(key)或值(value)配对组成的元素的集合,在Python3.7+,字典被确定为有序,而3.6之前是无序的,其长度大小可变,元素可以任意地删减和改变。相比于列表和元组,字典的性能更优,特别是对于查找、添加和删除操作,字典都能在常数时间复杂度内完成。

在3.6中,字典有序是一个implementation detail,在3.7才正式成为语言特性,因为3.6中无法100%确保其有序性。

而集合和字典基本相同,唯一的区别,就是集合没有键和值的配对,是一系列无序的、唯一的元素组合。下面是字典和集合的创建几种方式:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>>>'''字典创建的方式'''
>>> d1 = {"name":'Dawn', 'age':20, 'gender':'male'}
>>> d2 = dict({"name":'Dawn', 'age':20, 'gender':'male'})
>>> d3 = dict([("name", 'Dawn'), ('age', 20), ('gender','male')])
>>> d4 = dict(name='Dawn', age=20, gender='male')
>>> d1 == d2 == d3 == d4
True
>>>'''集合创建的方式'''
>>> s1 = {1, 2, 3}
>>> s2 = set([1, 2, 3])
>>> s1 == s2
True
  1. 字典的访问:按键值、get(key, default)

  2. 集合的访问:**集合并不支持索引操作,因为集合本质上是一个哈希表,和列表不一样,**所以针对一个集合使用s[0]这种方式访问是错的。

  3. 元素是否在字典或集合里面:使用value in dict/set来判断

  4. 字典和集合的增加、删除、更新:

1
2
3
4
5
6
7
>>> s = {1,2,3}
>>> s.add(4)
>>> s
{1, 2, 3, 4}
>>> s.remove(4)
>>> s
{1, 2, 3}

集合的pop()操作是删除集合中最后的一个元素,可是集合本身是无序的,你无法知道会删除哪个元素,因此这个操作得谨慎使用。

  1. 字典和集合的排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
>>> d = {'b':1, 'a':3, 'c':2}
>>> dSortedByKey = sorted(d.items(), key=lambda x:x[0])
>>> dSortedByKey
[('a', 3), ('b', 1), ('c', 2)]
>>> dSortedByValue = sorted(d.items(), key=lambda x:x[1])
>>> dSortedByValue
[('b', 1), ('c', 2), ('a', 3)]	# 默认是升序排列
>>> dSortedByValue = sorted(d.items(), key=lambda x:x[1], reverse=True)
>>> dSortedByValue
[('a', 3), ('c', 2), ('b', 1)]	# 想要降序,reverse=True即可

>>> s = {3, 4, 2, 1}
>>> sorted(s)
[1, 2, 3, 4]
  1. 字典的键值和集合中的元素必须是要hashable,如下所示['education']就是不可哈希的,那么是错误的
1
d = {'name': 'jason', ['education']: ['Tsinghua University', 'Stanford University']}

字典和集合性能

字典和集合是进行过性能高度优化的数据结构,特别是对于查找、添加和删除操作。下面把它们和列表进行比较:

字典和列表比较

假如我们现在需要给定某件商品的ID,我们要找出其价格,假如使用列表存储并进行查找的话,代码和列表存储示例如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def find_product_price(products, product_id):
    for id, price in products:
        if id == product_id:
            return price
    return None

products = [
    (143121312, 100),
    (432314553, 30),
    ...
    (32421912367, 150)
]

find_product_price(products, 432314553) # 查找

假设products中有n个元素,而查找的过程中要遍历列表,那么时间复杂度为O(n)。假如用字典来存储我们这些数据,那么查找就会非常便捷高效,只需要O(1)的时间复杂度就可以完成,因为字典的内部组成是一张哈希表。使用字典存储结构如下所示:

1
2
3
4
5
6
7
products = {
  143121312: 100,
  432314553: 30,
  ...
  32421912367: 150
}
products[432314553]	# 查找

集合和列表进行比较

跟上述数据类似,只是这次我们要找出有多少不同的价格,假如使用列表数据结构来存储这些价格,那么需要$O(n^2)$的时间复杂度:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# list version
def find_unique_price_using_list(products):
    unique_price_list = []
    for _, price in products: # A
        if price not in unique_price_list: #B
            unique_price_list.append(price)
    return len(unique_price_list)

products = [
    (143121312, 100), 
    (432314553, 30),
    ...
    (32421912367, 150),
    (937153201, 30)
]
find_unique_price_using_list(products)

但是假如我们选择使用集合这个数据结构,由于集合是高度优化的哈希表,里面的元素不能重复,并且添加、删除操作只需O(1)的复杂度,那么总的时间复杂度就只有O(n):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# set version
def find_unique_price_using_set(products):
    unique_price_set = set()
    for _, price in products:
        unique_price_set.add(price)
    return len(unique_price_set)        

products = [
    (143121312, 100), 
    (432314553, 30),
    ...
    (32421912367, 150),
    (937153201, 30)
]
find_unique_price_using_set(products)

为了有一个更加直观的感受,下面对上述两种方法进行测试,测试代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import time
id = [x for x in range(0, 10000)]
price = [x for x in range(20000, 30000)]
products = list(zip(id, price))

# 计算列表版本的时间
start_using_list = time.perf_counter()
find_unique_price_using_list(products)
end_using_list = time.perf_counter()
print("使用列表测试的时间: {}".format(end_using_list - start_using_list))

# 计算集合版本的时间
start_using_set = time.perf_counter()
find_unique_price_using_set(products)
end_using_set = time.perf_counter()
print("使用集合方式测试的时间: {}".format(end_using_set - start_using_set))

测试的结果如下,很明显集合这种方式会更高效:

1
2
使用列表测试的时间: 0.770091052909779
使用集合方式测试的时间: 0.0012316425773241102

字典和集合推荐初始化方法

同列表和元组初始化方法一样,字典和集合的初始化方法有以下几种,那么更高效的是第一种初始化方法,原理同列表那的类似。

1
2
3
4
5
# 字典第一种初始化方法
d = {'name': 'Dawn', 'age': 20, 'gender': 'male'}

# 字典第二种初始化方法
d = dict({'name': 'Dawn', 'age': 20, 'gender': 'male'})

上述的测试效果如下:

1
2
3
4
5
>>> import timeit
>>> timeit.timeit("d = {'name': 'Dawn', 'age': 20, 'gender': 'male'}",number=100000)
0.0157328343314731
>>> timeit.timeit("d = dict({'name': 'Dawn', 'age': 20, 'gender': 'male'})",number=100000)
0.045083716705413224

字典和集合的内部实现

上面演示了字典和集合与列表的性能比较,那么为什么字典和集合能够如此高效,特别是查找、插入和删除操作。这与字典和集合的内部结构都是一张哈希表密不可分。其中对于字典而言,这张表存储了哈希值(hash)、键和值这3个元素,而对于集合来说区别就是哈希表内只有单一的元素。

字典的内部实现

字典是通过哈希表实现的,也就是说,字典是一个数组,而数组的索引是键值经过哈希函数处理后得到的。如我们有如下这样的一个字典:

1
{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}

那么实际上存储中这是一个数组,如下所示,即键值经过哈希函数得到的哈希值为(哈希值,键,值)在数组中存储的索引:

1
2
3
4
5
6
7
8
9
entries = [
...
[-1749738411985517803, 'gender', 'male'], 
...
[-1129878167999217704, 'dob', '1999-01-01'],
...
[-599462501662173341, 'name', 'mike'],
...
]

然而这种方式显然非常浪费存储空间,为了提高存储空间的效率。Python内部实现中,将存储字典的数组初始大小设置为8,并且数组的索引在原来直接得到的哈希值的基础之上加上了掩码,改变后的索引=哈希值&掩码,即index=hash(key)&mask,其中mask=PyDict_MINSIZE - 1,PyDict_MINSIZE 为Python内部实现中存储字典的数组的长度,初始值为8,当存放的数据量超过数组的大小的2/3,那么会调整数组的长度,PyDict_MINSIZE 值也会变化,并且所有元素的位置都会重新计算,重新存储。那么对于刚刚的例子来说,会初始一个大小为8的数组,此时mask为7,那么通过&操作后得到的索引情况如下所示:

1
2
3
4
5
6
>>> hash('name')&7
3
>>> hash('dob')&7
0
>>> hash('gender')&7
5

那么数组的存储情况如下所示:

1
2
3
4
5
6
7
8
9
entries = [
...
[-1749738411985517803, 'gender', 'male'], 
...
[-1129878167999217704, 'dob', '1999-01-01'],
...
[-599462501662173341, 'name', 'mike'],
...
]

其中['---','---','---']表示为空,这样子就在一定程度上提高了空间利用率。下面我们具体来讲一下针对插入、查找、删除操作的内部流程。

插入操作

跟上述所阐述的类似,向字典中插入时,会首先计算键的哈希值,即hash(key),再和mask进行与操作,计算这个元素应该插入数组的位置index = hash(key)&mask。如果该位置为空,那么则将值被插入其中,而如果此位置已被占用,Python便会判断这两个的键值是否相等,如果相等,则表明这个元素已经存在,如果值不同则更新值,假如不相等,那么就是哈希冲突。这种情况下,便会寻找表中空余的位置,直到找到位置为止。最简单的方式就是线性寻址,当然,Python内部对此进行了优化,让这个步骤更加高效。

1
2
3
4
5
6
7
index = hash(key) & mask # mask = PyDicMinSize - 1
if slot[index] is empty: 
    slot[index] -> value
else if key is old key: 
    slot[index] -> new value
else 
	find a new index: slot[new index] -> new value

查找操作

与插入操作类似,Python会根据index = hash(key)&mask找到index位置,假如index位置为空,那么抛出异常,假如不为空比较这个位置的键值和查找的键值是否相等,如果相等,则直接返回,如果不等,则按照上述哈希冲突的方法继续查找,直到找到或者找到空位为止。

1
2
3
4
5
6
7
index = hash(key) & mask # mask = PyDicMinSize - 1
if slot[index] is empty: 
    raise KeyError
if slot[index] is not empty and slot[index].key == key: 
    return slot[index] 
else:
    find all slot until find or find null(raise KeyError)

删除操作

对于删除操作,同样会进行同查找的步骤。但是当找到之后,并不是真正的删除而是暂时会对这个位置赋予一个特殊的值,等待重新调整哈希表的大小时,再将其删除。

集合的内部实现

集合和字典的实现原理都是一样的,都是将实际的值放到一个数组中,不同的地方在于hash函数操作的对象,对于字典而言,hash函数操作的是key,而对于集合来说是直接操作它的元素。所以集合中的对象必须是hashable的。这里就不再赘述了。

  1. index = hash(key) & mask # mask = PyDicMinSize - 1
  2. if slot[index] is empty: slot[index] -> value
  3. else if key is old key: slot[index] -> new value
  4. else find a new index: slot[new index] -> new value

本文参考内容

  1. 个人博客_Python 容器
  2. 伯乐在线_深入 Python 字典的内部实现
  3. 极客时间_Python核心技术与实战