字典和集合

2024-01-10 18:53:16

相较于列表和元组,字典的性能更加快,特别在于其增加,修改,删除等操作.字典都能快速完成.而集合与字典的区别主要在于,集合没有键和值的配对.是一个无序的.唯一的元素组合.

创建字典

d1 = {"name": "wp", "age": 18}
d2 = dict({'name': "wp", "age": 18})
d3 = dict([("name", "wp"), ("age", 18)])
d4 = dict(name="wp", age=18)
if d1 == d2 == d3 == d4:
    print('ok')
# ok

创建集合

    s1 = {1,2,3}
    s2 = set([1,2,3])
    if s1 == s2:
        print('ook')

python中字典和集合,无论是健还是值,都可以是混合的类型

s3 = {1, "wp", 18.5}

元素访问

    d1 = {"name": "wp", "age": 18}
    d2 = dict({'name': "wp", "age": 18})
    d3 = dict([("name", "wp"), ("age", 18)])
    d4 = dict(name="wp", age=18)
    print(d1["name"])
    # wp

如果没有这个键,则会直接报异常,当然也可以使用get(key,default)函数来进行索引,当健不存在时,咱们可以给其定义一个默认值

    print(d1.get("age"))
    # 18
    print(d1.get('wwww',"null"))
    # null

集合不支持索引操作,因为集合的本质是一个哈希表,和列表并不一样.所以无法使用s[0]去访问元素,如果要判断元素是否在集合内,只能使用value in dict/set 来判断

元素增删改

    d1 = {"name": "wp", "age": 18}
    d1['gender'] = "male"
    print(d1)
    # {'name': 'wp', 'age': 18, 'gender': 'male'}
    d1.pop("age")
    print(d1)
    # {'name': 'wp', 'gender': 'male'}
    d1['name'] = "wp1"
    print(d1)
    #{'name': 'wp1', 'gender': 'male'}

    s1 = {1, 2, 3}
    s1.add(4)
    print(s1)
    # {1, 2, 3, 4}
    
    s1.remove(4)
    print(s1)
    # {1, 2, 3}

排序

    d = {'b': 1, "c": 3, "a": 10}
    d_sort_by_Key = sorted(d.items(), key=lambda x: x[0])
    print(d_sort_by_Key)
    # [('a', 10), ('b', 1), ('c', 3)]
    d_sort_by_value = sorted(d.items(),key=lambda x:x[1])
    print(d_sort_by_Key)
    # [('a', 10), ('b', 1), ('c', 3)]

这里返回的是一个列表,列表中每个元素,是由原来字典中key,value组成的元组

但是集合的排序就简单的多,只需要使用sorted()函数即可

    s1 = {1,4,2,6}
    sorted(s1)
    print(s1)
    # {1, 2, 4, 6}

字典与集合的性能对比

字典和集合都是通过性能高度优化过的数据结构,但是还是有必要在看一下,在一定数据量的前提下二者的性能对比

假设现在又100000个元素商品,并分别计算使用列表和集合来统计产品价格数量的运行时间

# 列表
def find_unique_price_using_list(products):
    unique_price_list = []
    for _, price in products:  # A
        if price not in unique_price_list:
            unique_price_list.append(price)
        return len(unique_price_list)


# 集合
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)

if __name__ == '__main__':
    id = [x for x in range(0, 100000)]
    price = [x for x in range(200000, 300000)]
    produces = list(zip(id, price))
    start_using_list = time.perf_counter()
    find_unique_price_using_list(produces)
    end_using_list = time.perf_counter()
    print("list time {}".format(end_using_list - start_using_list))
    # list time 4.9999999999980616e-06

    start_using_list1 = time.perf_counter()
    find_unique_price_using_set(produces)
    end_using_list1 = time.perf_counter()
    print("set time {}".format(end_using_list1 - start_using_list1))
    # set time 0.008161099999999998

可以看到10w的数据量就有了如此大的性能差异

字典与集合的工作原理

字典与集合内部的数据结构都是一张哈希表

对于字典而言,这张表存储了哈希值(hash),键和值这3个元素\
对于集合而言,区别就在于表中没有键和值的配对,只有单一的元素

老版本的哈希表结构⬇


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

这种表的最大缺点就是,随着哈希表的扩张,他会变得越来越稀疏,如果数据是这样的话

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

那么他的哈希表结构就是这样

entries = [
['--', '--', '--']
[-230273521, 'dob', '1999-01-01'],
['--', '--', '--'],
['--', '--', '--'],
[1231236123, 'name', 'wp'],
['--', '--', '--'],
[9371539127, 'gender', 'male']
]

这样的设计非常的浪费空间,所以现在为了提高存储空间的利用率,现在的哈希表除了字典本身的结构,会把索引和哈希值,健,值单独分开

Indices
----------------------------------------------------
None | index | None | None | index | None | index ...
----------------------------------------------------

Entries
--------------------
hash0   key0  value0
---------------------
hash1   key1  value1
---------------------
hash2   key2  value2
---------------------
        ...
---------------------

indices = [None, 1, None, None, 0, None, 2]
entries = [
[1231236123, 'name', 'wp'],
[-230273521, 'dob', '1999-01-01'],
[9371539127, 'gender', 'male']
]

插入操作

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

若两者都相等，则表明这个元素已经存在，如果值不同，则更新值。
若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。

这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止。值得一提的是，通常来说，遇到这种情况，最简单的方式是线性寻找，即从这个位置开始，挨个往后寻找空位。让这个步骤更加高效。

查找操作

查找操作和前面的插入操作类似，Python 会根据哈希值，找到其应该处于的位置；然后，比较哈希表这个位置中元素的哈希值和键，与需要查找的元素是否相等。如果相等，则直接返回；如果不等，则继续查找，直到找到空位或者抛出异常为止。

删除操作

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

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

码农公寓

相关文章