python 字典和集合

旧城等待， 2022-01-26 08:21 293阅读 0赞

字典和集合在 Python 被广泛使用，并且性能进行了高度优化。

## 基础 ##

是一系列无序元素的组合，其长度大小可变，元素可以任意地删减和改变，这里的元素，是一对键（key）和值（value）的配对,

相对于列表和元组，字典的性能更优，主要是体现在查找、添加和删除；

和list比较，dict有以下几个特点：

> **查找和插入的速度极快，不会随着key的增加而变慢；**
> 
> **需要占用大量的内存，内存浪费多。**

而list相反：

> 查找和插入的时间随着元素的增加而增加；
> 
> 占用空间小，浪费内存很少。

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

### 字典基础操作 ###

> 创建：
> 
> d1 = \{'name': 'tom', 'age': 18, 'gender': 'male'\}
> 
> d2 = dict(\{'name': 'tom', 'age': 18, 'gender': 'male'\})
> 
> d3 = dict(\[('name', 'tom'), ('age', 20), ('gender', 'male')\])
> 
> d4 = dict(name='jason', age=20, gender='male')
> 
> print(d1,d2,d3,d4)
> 
> print(d1\['name'\])  \#查找
> 
> d1\['age'\] = 20    \#修改
> 
> del d1\['name'\]    \#删除
> 
> d1.pop("age")   
> 
> \# 合并
> 
> dic1 = \{"name": "tom"\}
> 
> dic2 = \{"age": "18"\}
> 
> dic1.update(dic2)
> 
> d1.setdefault("name") \# 如果有这个值则输出，若没有则创建并使用默认值none
> 
> d1.get("name")        \# 如果有这个值则输出，若没有返回默认值none
> 
> \# 创建一个新的字典，默认值是\`123\`
> 
> a = dic.fromkeys(\["k1", "k2", "k3"\], "123")
> 
> print(a)
> 
> d = \{'b': 1, 'a': 2, 'c': 10\}
> 
> d\_sorted\_by\_key = sorted(d.items(), key=lambda x: x\[0\]) \# 根据字典键的升序排序
> 
> d\_sorted\_by\_value = sorted(d.items(), key=lambda x: x\[1\]) \# 根据字典值的升序排序

### 集合基础操作 ###

集合创建：

> s1 = \{1, 2, 3\}
> 
> s2 = set(\[1, 2, 3\])
> 
> print(s1 == s2, s1, s2)
> 
> \# True \{1, 2, 3\} \{1, 2, 3\}
> 
> n = \{"alex",'eric','tony'\}
> 
> n.add("bill")    \# 添加
> 
> n.clear()        \#清空
> 
> n.copy()        \#复制
> 
> \# 输出s1中存在，s2中不存在
> 
> s1 = \{"alex",'eric','tony','李四','李四11'\}
> 
> s2 = \{"alex",'eric','tony','张三'\}
> 
> v = s1.difference(s2)
> 
> print(v)  \# 输出s1中存在，s2中不存在
> 
> \# \{'李四', '李四11'\}
> 
> v = s1.symmetric\_difference(s2) \# 输出两集合不同的元素
> 
> s1.symmetric\_difference\_update(s2)  \# 输出两个几个不同的元素并清空s1，并将不同的元素复制到s1
> 
> v = s1.intersection(s2)        \# 两个集合相同的元素（交集）
> 
> s1.intersection\_update(s2)      \# 取交集，然后对s1清空，然后在重新复制
> 
> v = s1.union(s2)                \# 并集
> 
> s1.discard('alex')              \# 移除
> 
> v = s1.issubset(s2)            \# 判断s1 是否是 s2的子集
> 
> v = s1.issuperset(s2)          \# s1 是否是 s2的父集
> 
> v = s1.pop()                    \# 随机删除一个元素，并取值
> 
> s1.remove('alex')              \# 移除
> 
> s1.update(\{'alex','123123','fff'\}) \# 批量添加，有相同的部分不改
> 
> s = \{3, 4, 2, 1\}
> 
> sorted(s) \# 对集合的元素进行升序排序
> 
> \[1, 2, 3, 4\]

**set运算**

> a = \{1,2,3,4,5\}
> 
> b = \{2,3,4,5,6\}
> 
> print(a.union(b))      \#并集
> 
> print(a-b)              \#差集
> 
> print(a&b)              \#求交集
> 
> print(a^b)              \#对称差集
> 
> print(a.issubset(b))    \#a是b的子集 看返回值的真假
> 
> print(a.issuperset(b))  \#a是否包含b 看返回值的真假

## 字典和集合的性能 ##

列表中查找

> 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)
> 
> \]
> 
> print('The price of product 432314553 is \{\}'.format(find\_product\_price(products, 432314553)))
> 
> \# 输出
> 
> The price of product 432314553 is 30

字典中查找

上面结果可以看出 字典在查找方面更优，列表查找时间复杂度为：O(n),即使使用二分查找，也需要O(logn)的时间复杂度。字典的时间复杂度为O(1).

## 列表和集合去重性能对比 ##

> import time
> 
> id = \[x for x in range(0, 100000)\]
> 
> price = \[x for x in range(200000, 300000)\]
> 
> products = list(zip(id, price))
> 
> 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)
> 
> 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)
> 
> \# 计算列表版本的时间
> 
> start\_using\_list = time.perf\_counter()
> 
> find\_unique\_price\_using\_list(products)
> 
> end\_using\_list = time.perf\_counter()
> 
> print("time elapse using list: \{\}".format(end\_using\_list - start\_using\_list))
> 
> \# 输出
> 
> \# time elapse using list: 54.833863215
> 
> \# 计算集合版本的时间
> 
> start\_using\_set = time.perf\_counter()
> 
> find\_unique\_price\_using\_set(products)
> 
> end\_using\_set = time.perf\_counter()
> 
> print("time elapse using set: \{\}".format(end\_using\_set - start\_using\_set))
> 
> \# 输出
> 
> \# time elapse using set: 0.009784918000001142

可以看出，仅数十万的数据，两者的差距如此之大。

## 字典和集合的工作原理 ##

上面可以看出，字典和集合性能在查找、插入、和删除的性能很高效

原因在于，字典和集合的内部结构是一张哈希表。

对于字典而言，这张表存储了哈希值（hash）、键、和值，三个元素

对集合来说，哈希表内没有键和值的配对，只有单一的元素

新版本python hash涉及结构发生了改变，大幅提高了空间利用率

**插入操作**

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

而如果此位置已被占用，Python 便会比较两个元素的哈希值和键是否相等。

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

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