精华内容
下载资源
问答
  • 字典(dict)和集合(set)在 Python 被广泛使用,并且性能进行了高度优化,其重要性不言而喻。 字典集合基础 字典是一系列由键(key)和值(value)配对组成的元素的...而集合字典基本相同,唯一的区别,就是集

    字典(dict)和集合(set)在 Python 被广泛使用,并且性能进行了高度优化,其重要性不言而喻。

    字典和集合基础

    字典是一系列由键(key)和值(value)配对组成的元素的集合。python3.7之后,字典底层是2个数组,一个为一维数组,存放hash(key)取余后的值作为数组的索引,对应索引位置存放键值对在二维数组的索引位置。因此二维数组是一个有序的数组。

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

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

    字典和集合的创建方式通常有以下几种:

    d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
    d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'})
    d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')])
    d4 = dict(name='jason', age=20, gender='male') 
    d1 == d2 == d3 ==d4
    True
    
    s1 = {1, 2, 3}
    s2 = set([1, 2, 3])
    s1 == s2
    True
    

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

    s = {1, 'hello', 5.0}
    

    字典和集合的访问

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

    d = {'name': 'jason', 'age': 20}
    d['name']
    'jason'
    d['location']
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    KeyError: 'location'
    

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

    d = {'name': 'jason', 'age': 20}
    d.get('name')
    'jason'
    d.get('location', 'null')
    'null'
    

    集合并不支持索引操作,因为集合本质上是一个哈希表,和列表不一样。所以,下面这样的操作是错误的,Python 会抛出异常。

    s = {1, 2, 3}
    s[0]
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: 'set' object does not support indexing
    

    要判断一个元素在不在字典或集合内,我们可以用 value in dict/set 来判断(对于字典,只能使用key in dict 来判断)。

    s = {1, 2, 3}
    1 in s
    True
    10 in s
    False
    
    d = {'name': 'jason', 'age': 20}
    'name' in d
    True
    'location' in d
    False
    

    增加、删除、更新

    除了创建和访问,字典和集合也同样支持增加、删除、更新等操作。

    d = {'name': 'jason', 'age': 20}
    d['gender'] = 'male' # 增加元素对'gender': 'male'
    d['dob'] = '1999-02-01' # 增加元素对'dob': '1999-02-01'
    d
    {'name': 'jason', 'age': 20, 'gender': 'male', 'dob': '1999-02-01'}
    d['dob'] = '1998-01-01' # 更新键'dob'对应的值 
    d.pop('dob') # 删除键为'dob'的元素对
    '1998-01-01'
    d
    {'name': 'jason', 'age': 20, 'gender': 'male'}
    
    s = {1, 2, 3}
    s.add(4) # 增加元素4到集合
    s
    {1, 2, 3, 4}
    s.remove(4) # 从集合中删除元素4
    s
    {1, 2, 3}
    

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

    排序

    对于字典,我们通常会根据键或值,进行升序或降序排序。会返回一个列表,列表中的每个元素,是由原字典的键和值组成的元组。

    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]) # 根据字典值的升序排序
    d_sorted_by_key
    [('a', 2), ('b', 1), ('c', 10)]
    d_sorted_by_value
    [('b', 1), ('a', 2), ('c', 10)]
    

    而对于集合,其排序和前面讲过的列表、元组很类似,直接调用 sorted(set) 即可,结果会返回一个排好序的列表。

    s = {3, 4, 2, 1}
    sorted(s) # 对集合的元素进行升序排序
    [1, 2, 3, 4]
    

    字典和集合的性能

    字典和集合是进行过性能高度优化的数据结构,特别是对于查找、添加和删除操作。

    比如电商企业的后台,存储了每件产品的 ID、名称和价格。现在的需求是,给定某件商品的 ID,我们要找出其价格。

    如果我们用列表来存储这些数据结构,并进行查找,相应的代码如下:

    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
    

    假设列表有 n 个元素,而查找的过程要遍历列表,那么时间复杂度就为O(n)O(n)。即使我们先对列表进行排序,然后使用二分查找,也会需要O(logn)O(\log n)的时间复杂度,更何况,列表的排序还需要O(nlogn)O(n\log n)的时间。

    如果我们用字典来存储这些数据,那么查找就会非常便捷高效,只需O(1)O(1)的时间复杂度就可以完成。原因也很简单,刚刚提到过的,字典的内部组成是一张哈希表,你可以直接通过键的哈希值,找到其对应的值。

    products = {
      143121312: 100,
      432314553: 30,
      32421912367: 150
    }
    print('The price of product 432314553 is {}'.format(products[432314553])) 
    
    # 输出
    The price of product 432314553 is 30
    

    现在需求变成,要找出这些商品有多少种不同的价格。我们还用同样的方法来比较一下。

    如果还是选择使用列表,对应的代码如下,其中,A 和 B 是两层循环。同样假设原始列表有nn个元素,那么,在最差情况下,需要O(n2)O(n^2)的时间复杂度。

    # 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)
    ]
    print('number of unique price is: {}'.format(find_unique_price_using_list(products)))
    
    # 输出
    number of unique price is: 3
    

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

    # 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)
    ]
    print('number of unique price is: {}'.format(find_unique_price_using_set(products)))
    
    # 输出
    number of unique price is: 3
    

    下面的代码,初始化了含有 100,000 个元素的产品,并分别计算了使用列表和集合来统计产品价格数量的运行时间:

    import time
    id = [x for x in range(0, 100000)]
    price = [x for x in range(200000, 300000)]
    products = list(zip(id, price))
    
    # 计算列表版本的时间
    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: 41.61519479751587
    
    # 计算集合版本的时间
    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.008238077163696289
    

    字典和集合的工作原理

    不同于其他数据结构,字典和集合的内部结构都是一张哈希表。

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

    老版本 Python 的哈希表结构如下所示:

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

    不难想象,随着哈希表的扩张,它会变得越来越稀疏。

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

    它会存储为类似下面的形式:

    entries = [
    ['--', '--', '--']
    [-230273521, 'dob', '1999-01-01'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [1231236123, 'name', 'mike'],
    ['--', '--', '--'],
    [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', 'mike'],
    [-230273521, 'dob', '1999-01-01'],
    [9371539127, 'gender', 'male']
    ]
    

    插入操作

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

    • 若两者都相等,则表明这个元素已经存在,如果值不同,则更新值。
    • 若两者中有一个不相等,这种情况我们通常称为哈希冲突(hash collision),意思是两个元素的键不相等,但是哈希值相等。这种情况下,Python便会继续寻找表中空余的位置,直到找到位置为止。

    值得一提的是,通常来说,遇到这种情况,最简单的方式是线性寻找,即从这个位置开始,挨个往后寻找空位。当然,Python内部对此进行了优化,让这个步骤更加高效。(在数据结构对应的章节也有了解,可以0,1,2,3也可以0,1,-1,还可以0,1,4)

    查找操作

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

    删除操作

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

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

    虽然哈希冲突和哈希表大小的调整,都会导致速度减缓,但是这种情况发生的次数极少。所以,平均情况下,这仍能保证插入、查找和删除的时间复杂度为O(1)O(1)

    展开全文
  • python字典与集合

    2021-06-19 16:03:45
    集合字典基本相同,区别是没有键和值的配对,是一系列无序的、唯一的元素组合。集合不支持索引进行访问、操作,其本质上是一个哈希表,和列表不一样。 字典集合的工作原理,字典集合的内部结构都是一张哈希表 ...

    字典

    • 字典是一系列由键(key)和值(value)配对组成的元素的集合
    • 在python3.7+字典被确定为有序,其长度大小可变,元素可以任意的增删改。
    • 相比于列表和元组,字典性能更优秀,增删改查操作都可在常数时间复杂度内完成。
    '''字典的常用写法'''
    # 创建一个保护有数据的字典
    # 语法:
    #   {key:value,key:value,key:value}
    #   字典的值可以是任意对象
    #   字典的键可以是任意的不可变对象(int、str、bool、tuple ...),但是一般我们都会使用str
    d1 = {'name':'magic', 'age': 20}
    d2 = dict({'name':'magic', 'age': 20})
    d3 = dict([('name','magic'), ('age', 20)])
    d4 = dict(name='magic', age=20)
    print(d2)
    print(d1 == d2 == d3 ==d4) #True
    print(d1['name']) #magic
    #print(d1['name2']) 键不存在会抛出异常
    #d1.get('name2',None) 不存在时返回一个给定的默认值,解决键不存在抛出异常问题
    sorted(d1.items(),key=lambda x: str(x[0])) #根据字典键进行升序排序 排序的元素值需要同一类型
    sorted(d1.items(),key=lambda x: str(x[1])) #根据字典值进行升序排序  排序的元素值需要同一类型
    '''
    lambda匿名函数
    lambda x: x[0] 
    相当于
    def f(x):
        return x[0]
    '''
    #使用zip函数创建字典
    index = ['name', 'age', 'sex']
    data = [['小明', 22, '男'],['小丽', 18, 'nv']]
    d5 = dict(zip(index, data))
    print(d5)
    

    集合

    • 集合和字典基本相同,区别是没有键和值的配对,是一系列无序的、唯一的元素组合。
    • 集合不支持索引进行访问、操作,其本质上是一个哈希表,和列表不一样。
    '''集合的常用写法'''
    s1 = {1, 2, 3, 4, 'magic', 'two'}
    s2 = set([1, 2, 3, 4, 'magic', 'two'])
    print(s1 == s2) #True
    #s1[0] 通过索引下标访问,会抛出异常,集合不支持索引
    s5 = {1, 2, 3, 4, 5, 6} #排序的元素值需要同一类型
    sorted(s5) #对集合的元素进行升序排序
    
    '''通过value in dict/set来判断一个元素在不在字典或集合内'''
    print(1 in s1) #True
    print('name' in s1) #True
    print('magic' in s1) #False 字典这里是通过键key判断的
    

    字典和集合的工作原理

    字典和集合的内部结构都是一张哈希表
    字典表存储了哈希值(hash)、键和值这三个元素,集合没有键和值的配对,只有单一的元素

    老版本的python哈希表结构如下:

    哈希值(hash) 键(key) 值(value)
    hash0 key0 value0
    hash1 key1 value1
    hash2 key2 value2

    随着数据存储,它会原来越稀疏,它的存储会类似下面形式:

    data = [
    ['--']['--']['--']
    ['hash0']['key0']['value0']
    ['--']['--']['--']
    ['--']['--']['--']
    ['hash1']['key1']['value1']
    ['--']['--']['--']
    ['hash2']['key2']['value2']
    ]
    

    这样的设计结构会浪费存储空间,为了提高存储空间利用率
    现在的哈希表会把索引和哈希值、键、值分开,形成下面的新结构:
    indices索引表

    None index None index None index None index None index

    data数据表

    哈希值(hash) 键(key) 值(value)
    hash0 key0 value0
    hash1 key1 value1
    hash2 key2 value2

    在新的结构存储数据,就会形成下面的形式:

    indices = [None, 1 ,None , None , 0 ,None , 2]
    data = [
    123123213, 'name', 'magic'
    'hash--11', 'name', 'long'
    12312323, 'age' , 20
    ]
    

    1. 插入操作

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

    1. 若两者相等,则表明元素已存在,若值不同,则更新值
    2. 若两者不相等,这种情况即是哈希冲突(hash collision)了,在这种情况下,python会继续寻找表中空余位置插入

    解决哈希冲突的方法主要有两种,一种是开放寻址法,一种是链表法
    哈希冲突的发生,往往会减低操作的速度,因此随着元素不断插入,当剩余空间小于1/3时
    python会重新获取更大的内存空间,扩充哈希表,表内所有的元素位置都会被重新排放
    哈希冲突和调整大小都会降低效率,但这种情况发生次数极小,平均情况下,保证插入、查找和删除的时间复杂度为O(1)

    2. 查找操作
    和插入操作类似,计算键的哈希值hash(key),找到其位置,比较哈希表这个位置中元素的哈希值和键,
    与需要查找的元素是否相等,如果相等返回,如果不相等继续查找,直到找到空位或者抛出异常为止。

    2. 删除操作
    对于删除操作,python会暂时对这个位置的元素赋予一个特殊的值,等到重新调整哈希表的大小时,再将其删除。
    采用懒惰的处理方式,减少每次删除时间的复杂度,让其均摊。

    总结

    字典在python3.7+是有序的数据结构,集合是无序的,其内部的哈希表存储结构,保证了其查找、插入、删除操作的高效性。
    所以字典和集合通常运用在对元素的高效查找、去重等场景。

    展开全文
  • 列表 有序的可重复的可变对象集合 异构:对象可以是不同的数据类型 可变:增加,删除,或修改对象 符号:[ ] 元组 有序的可重复的不可变的对象集合 ...字典 无序的键值对集合(数据关联性) 可变 符号:{ } ...

    列表

    有序的可重复的可变对象集合
    异构:对象可以是不同的数据类型
    可变:增加,删除,或修改对象
    符号:[ ]
    处理:迭代处理

    def print_lol(the_list):
    	for each_item in the_list:
    		if isinstance(each_item,list):
    			print_lol(each_item)
    		else:
    			print(each_item)
    

    列表推倒(区别于列表迭代):

    mins = [1,2,3,5,7,7]
    secs = [m*60 for m in mins]
    secs
    

    可用isinstance()来产生递归函数,进而输出打印迭代数据

    元组

    有序的可重复的不可变的对象集合
    对象可以是不同的数据类型
    不可变:一旦创建就不能改变,元组是常量列表
    符号:( )

    seasons = ['springs','summers','fall','winters']
    list(enumerate(seasons))
    out:[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
    list(enumerate(seasons, start=1))
    out:[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]
    
    a = [1,23,5,74,85,5]
    q = enumerate(a)
    print(list(q))
    out:[(0, 1), (1, 23), (2, 5), (3, 74), (4, 85), (5, 5)]
    
    for m,n in enumerate(a)
    	print(m,n)
    #enumerte(a)就相当于一个元组,然后对元组进行迭代!
    

    集合

    无序的唯一对象集合
    可变
    { }
    处理:
    enumerate来产生具有索引的元组!

    字典

    无序的键值对集合(数据关联性)
    可变
    字典的键值不允许重复(智障!)
    符号:{ }
    处理:可用迭代法。items处理字典

    迭代

    • for()循环迭代
    • zip()可以打包并行迭代
    • enumerate()生成具有标量索引的元组迭代。
    展开全文
  • 列表是任意对象的序列,列表用[ ]表示。 将一组值打包到一个对象中,称为元组,元组用()表示。 ...列表和元组不同,集合是无序的,也不能通过索引进行访问。此外,集合中的元素不能重复。 ...

    列表是任意对象的序列,列表用[ ]表示。

    将一组值打包到一个对象中,称为元组,元组用()表示。

    元组和列表的大部分操作相同,但是列表是不固定的,可以随时插入、删除,而元组一旦确定就不能再更改,所以系统为了列表的灵活性就需要牺牲一些内存,而元组就更为紧凑(注意:元组在定义过程中,字符串必须用单引号括起来)

    与列表和元组不同,集合是无序的,也不能通过索引进行访问。此外,集合中的元素不能重复。

    字典就是一个关联数组或散列表,其中包含通过关键字索引,所以比集合访问更方便。字典是Python解释器中最完美的数据类型。

    展开全文
  • PYTHON学习笔记3 set集合

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 275
精华内容 110
关键字:

python集合与字典区别

python 订阅