1. 首页
  2. 文章中心
  3. Python

Python 字典、集合 的性能 以及工作原理Python 字典、集合 的性能 以及工作原理

142 阅读 0 评论
我是靠谱客的博主 专注路人，最近开发中收集的这篇文章主要介绍Python 字典、集合 的性能 以及工作原理Python 字典、集合 的性能 以及工作原理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Python 字典、集合 的性能 以及工作原理

一、字典和集合的基础：

字典是一系列由键（key）和值（value）配对组成的元素的集合。

在 Python3.7+，字典被确定为有序;

相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。

集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

1.字典和集合的创建：

  1. 字典的创建：

    d1 = {'name': 'fe_cow', 'age': 18}
d2 = dict({'name': 'fe_cow', 'age': 18})
d3 = dict([('name', 'fe_cow'), ('age', 18)])
d4 = dict(name='fe_cow', age=18)
d1 == d2 == d3 == d4
# 输出结果:True

  2. 集合的创建：

    s1 = {1, 2, 3}
s2 = set([1, 2, 3])
s1 == s2
# 输出结果：True

Python 中字典和集合，无论是键还是值，都可以是混合类型

my_set = {6, '6', 6.66}

2.查看元素：

  1. 字典的操作：

    字典访问可以直接索引键，如果不存在，就会抛出异常：

    d1 = {'name': 'fe_cow', 'age': 18}
d1['name']
# 输出结果：fe_cow
d1 = {'name': 'fe_cow', 'age': 18}
d1['lh9']
# 抛出异常：
Traceback (most recent call last):
File "C:xxxxxxx", line 59, in <module>
d1['lh9']
KeyError: u'lh9'

    也可使用 get(key, default) 函数来进行索引。键不存在，调用 get() 函数可以返回一个默认值，如果没有设置默认值，会返回None：

    // 键存在, 直接使用get()函数进行索引，获取键对应的值
d1 = {'name': 'fe_cow', 'age': 18}
value = d1.get('name')
value
# 输出结果： fe_cow
// 键不存在，使用get()函数，设置默认值，返回默认值
d1 = {'name': 'fe_cow', 'age': 18}
value = d1.get('email', 'lh9')
value
# 输出结果： lh9
// 键不存在，使用get()函数，也没有设置默认值，返回None
d1 = {'name': 'fe_cow', 'age': 18}
value = d1.get('email')
value
# 输出结果：None

  2. 集合的操作：

    集合并不支持索引操作，因为集合本质上是一个哈希表，和列表不一样。

    s1 = {1, 2, 3}
s1[1]
# 抛出异常：
Traceback (most recent call last):
File "C:xxxxxxxx", line 59, in <module>
s1[1]
TypeError: 'set' object does not support indexing

3.判断一个元素是否在字典、集合中：

可以使用value in dict / set：

// 判断 1 这个元素是否在s1 集合中
s1 = {1, 2, 3}
1 in s1
# 输出结果： True
// 判断
6 这个元素是否在 S1 集合中
s1 = {1, 2, 3}
6 in s1
# 输出结果：False
// 判断"name" 是否在 d1字典中
d1 = {'name': 'fe_cow', 'age': 18}
'name' in d1
# 输出结果: True
// 判断 "email"， 是否在d1字典中
d1 = {'name': 'fe_cow', 'age': 18}
'email' in d1
# 输出结果：False

4.字典、集合的增删改操作：

// 创建d1字典
d1 = {'name': 'fe_cow', 'age': 18}
// 给d1字典，增加新的元素
d1['QQ'] = '280773872@qq.com'
// 给d1字典，增加新的元素
d1['mobile'] = '130xxxxxxxxx'
// 查看d1字典目前的值
d1
{"name": "fe_cow", "age": 18, "QQ": 280773872, "mobile"："130xxxxxxxxx"}
// 更新字典 d1 中 键"age" 所对应的值得
d1["age"] = 20
// 删除键为 "mobile" 的元素对
d1.pop("mobile")
"130xxxxxxxxx"
// 再次查看字典d1中的值
d1
{"name": "fe_cow", "age": 20, "QQ": 280773872}
// 创建集合
s1 = {1, 2, 3}
// 将元素 4 添加到集合s1中
s1.add(4)
// 查看当前s1集合中的值
{1, 2, 3, 4}
// 将 元素 4 从 s1集合中删除
s1.remove(4)
// 再次查看集合s1中的值
{1, 2, 3, 4}

注意：集合的 pop() 操作是删除集合中最后一个元素，可是集合本身是无序的，你无法知道会删除哪个元素。

4.字典、集合的排序：

// 创建字典d1
d1 = {'b': 1, 'a': 2, 'c': 10}
// 按照字典中的key进行升序排序
d1_sort_key = sorted(d1.items(), key=lambda x: x[0])
// 按照字典中的value进行升序排序
d1_sort_value = sorted(d1.items(), key=lambda x: x[1])
// 查看d1_sort_key 排序的结果
d1_sort_key
[('a', 2), ('b', 1), ('c', 10)]
// 查看d1_sort_value 排序的结果
d1_sort_value
[('b', 1), ('a', 2), ('c', 10)]

返回了一个列表，列表中的每个元素，是由原字典的键和值组成的元组。

// 创建一个集合
s1 = {2, 1, 4，3}
//对集合s1 进行升序排序
sorted(s1)
[1, 2, 3, 4]

直接调用sorted(set)，结果会返回一个排号好序的列表。

二、字典和集合性能：

1.字典的性能：

举个栗子，假设我们有每件商品的ID、名称、价格，现在的需求，给出商品的ID，找出对应的价格：

def func1(products, product_id):
"""通过商品的ID，获取到商品的价格函数"""
for id, price in products:
if id == product_id:
return price
return None
products = [
(1, 10),
(2, 20),
(3, 30)
]
print('Price of goods is {}'.format(func1(products, 2)))
# 输出
Price of goods is 20
  1. 这个栗子，假设products 列表中有n个元素，查找的过程要遍历列表，那么时间复杂度就为O(n)。
  2. 尽管我们先对列表进行排序，然后使用二分查找，也需要O(logn)的时间复杂度。

如果我们使用字典来存储这些数据，那么查找就非常的高效，举个栗子：

products = {1: 10, 2: 20, 3: 30}
print('Price of goods is {}'.format(products[2]))
# 输出
Price of goods is 20
  1. 只需O(1)的时间复杂度。
  2. 因为字典内部组成是一张哈希表，可以通过键的哈希值，找到对应的值。

2.集合的性能：

现在的需求，找出商品有多少种不同的价格，我们还是用上面列表的栗子：

def func1(products):
"""处理商品有多少种不同价格"""
my_list = []
# 遍历products 列表, 取出每个元素, 因为我们不需要商品的ID，使用 "_" 占位
for _, price in products:
# 如果 遍历出来的价格, 不在my_list 中， 说明有新的价格
if price not in my_list:
my_list.append(price)
return len(my_list)
products = [
(1, 10),
(2, 20),
(3, 30),
(4, 10)
]
print('Kind of product price is: {}'.format(func1(products)))
# 输出
Kind of product price is: 3
  1. 使用列表进行处理，用到 两层循环，如果原始列表有 n 个元素，需要O(n ^ 2)时间复杂度。

上面同样的需求，使用集合举个栗子：

def func1(products):
"""处理商品有多少种不同价格"""
my_set = {}
# 遍历products 列表, 取出每个元素, 因为我们不需要商品的ID，使用 "_" 占位
for _, price in products:
my_set.add(price)
return len(my_set)
products = [
(1, 10),
(2, 20),
(3, 30),
(4, 10)
]
print('Kind of product price is: {}'.format(func1(products)))
# 输出
Kind of product price is: 3
  1. 由于集合是高度优化的哈希表，里面元素不能重复，并且添加和查找操作只需O(1)的复杂度，那么总的时间复杂度是O(n)。

三、字典和集合的工作原理：

前面的栗子，可以看出，字典和集合的高效性。因为字典、集合内部的数据结构都是一张哈希表。

  1. 对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。
  2. 对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。

哈希表结构：

--+-------------------------------+
| 哈希值(hash)
键(key)
值(value)
--+-------------------------------+
0 |
hash0
key0
value0
--+-------------------------------+
1 |
hash1
key1
value1
--+-------------------------------+
2 |
hash2
key2
value2
--+-------------------------------+
. |
...
__+_______________________________+

举个栗子，有一个这样的字典：

d1 = {'b': 1, 'a': 2, 'c': 10}

那么它的存储类似于：

hash_list = [
['--', '--', '--']
[-321898392189, 'b', 1],
['--', '--', '--'],
['--', '--', '--'],
[3213212321, 'c', 10],
['--', '--', '--'],
[3213213, 'a', 2]
]

随着哈希表扩张，会变得越来越稀疏，也非常的浪费空间。为了提高存储空间利用率，可以把索引和哈希值、键、值单独分开：

Indices
----------------------------------------------------
None | index | None | None | index | None | index ...
----------------------------------------------------
Entries
--------------------
hash0
key0
value0
---------------------
hash1
key1
value1
---------------------
hash2
key2
value2
---------------------
...
---------------------

上述的栗子，在新的哈希表结构下的存储形式：

indices = [None, 0, None, None, 2, None, 1]
hash_list = [
[-321898392189, 'b', 1],
[3213212321, 'c', 10],
[3213213, 'a', 2]
]

1.插入操作的原理：

  1. 每次向字典或集合插入一个元素时，Python 会首先计算键的哈希值（hash(key))。
  2. 再和 mask = PyDicMinSize - 1 做与操作，计算这个元素应该插入哈希表的位置 index = hash(key) & mask。
  3. 如果哈希表中此位置是空的，那么这个元素就会被插入其中。

    两者都相等，则表明这个元素已经存在，如果值不同，则更新值；

    若两者中有一个不相等，这种情况我们通常称为哈希冲突，意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止；

2.查找操作的原理：

  1. Python 会根据哈希值，找到其应该处于的位置。
  2. 比较哈希表这个位置中元素的哈希值和键，与需要查找的元素是否相等。

    如果相等，则直接返回；

    如果不等，则继续查找，直到找到空位或者抛出异常为止；

3.删除操作原理：

  1. 删除操作，Python 会暂时对这个位置的元素，赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。

扩展：

  • 哈希冲突的发生，往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入，当剩余空间小于 1/3 时，Python 会重新获取更大的内存空间，扩充哈希表。不过，这种情况下，表内所有的元素位置都会被重新排放。

四、思考：

字典的键可以是一个列表吗？

d1 = {'name': 'fe_cow', ['list_key']: ['my_list', 'my_list_01']}

回答：

  • 用列表作为 Key 在这里是不被允许的，因为列表是一个动态变化的数据结构，字典当中的 key 要求是不可变的，key 首先是不重复的，如果 Key 是可以变化的话，那么随着 Key 的变化，这里就有可能就会有重复的 Key，那么这就和字典的定义相违背；

最后

以上就是专注路人为你收集整理的Python 字典、集合 的性能 以及工作原理Python 字典、集合 的性能 以及工作原理的全部内容，希望文章能够帮你解决Python 字典、集合 的性能 以及工作原理Python 字典、集合 的性能 以及工作原理所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(94)

相关文章

Python学习笔记四（元组、字典）
Python学习笔记四（元组、字典）
python 零散记录(四) 强调字典中的键值唯一性 字典的一些常用方法
python 零散记录(四) 强调字典中的键值唯一性 字典的一些常用方法
Python学习之路-----字典操作
Python学习之路-----字典操作
Python基础 字典的相关操作2.2.3 字典
Python基础 字典的相关操作2.2.3 字典
Python 字典、集合 的性能 以及工作原理Python 字典、集合 的性能 以及工作原理
Python 字典、集合 的性能 以及工作原理Python 字典、集合 的性能 以及工作原理
【python】字典的key值是通过什么原理导致唯一性的
【python】字典的key值是通过什么原理导致唯一性的
Python 字典的key值唯一特性
Python 字典的key值唯一特性
python 字典字典的常见操作
python 字典字典的常见操作

评论列表共有 0 条评论

立即
投稿
返回
顶部