8. Python3 中的数据结构

Python更多的数据结构

  • 集合(set)
  • 堆(heap)
  • 双向队列(double-ended queue)

在Python内置的数据类型中,tuple,string,list,dict这四种传统的数据类型基本上够用了,可还是不够灵活高效。可变数据类型只有list和dict两种,dict的键值对应的表达也太死板,所以在list的基础上衍生出来了set、heap、deque等高级丢丢的数据结构(当然功能也更加细化)。


8.1. 集合 set

没有重复元素,不能使用索引访问的数据结构哦,支持集合操作(交intersection、并union、差difference、对称差symmetric_difference)。不恰当的比喻,集合就是一个大罐子。

  1. 与list的关系。set(lst)将列表转换成set;list(st)将set转换成list对象。
  2. 元素的加入:add(st,value)
  3. 元素的删除(remove,指定元素)和弹出(pop,最小元素)

8.2 堆 heap

python中的堆 是一种按照某种顺序排列的数据结构(比喻为水桶,最轻的水果飘在最上面)。加入一个元素后自动排序,剔除一个元素也自动排序。加入值相当与lst.append().sort(),读取值相当与lst[0] . 简单的说,heap= list+sort

  1. 与list的关系。heap就是一种特殊排序的list(heap是基于树的排序),可通过heapify(lst)强制将list转换成heap(注意,未排序,只是可以用后面的heapq模块中的函数操作了)
  2. 由于不存在heap数据结构的对象,所以正常的堆(heap)的操作都需要将heap作为参数传入函数(list的所有操作,堆heap均可用,只是会破坏其排序结构)。
>>> from heapq import *
>>> from _heapq import heappop
>>> heap =[] # an empty list, is also a heap
>>> for i in range(10):
...     heappush(heap,10-i) #  push a value
... 
>>> print(heap)
[1, 2, 5, 4, 3, 9, 6, 10, 7, 8]
>>> heappop(heap)          # pop the minimal value
1
>>> print(heap)
[2, 3, 5, 4, 8, 9, 6, 10, 7]
>>> heapreplace(heap,6.5) # pop at first, and push another value
2
>>> print(heap)
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]
>>> type(heap) # heap is a list in the implementation
<class 'list'>
  1. 更多操作,最大(小)的n个值
>>> heap
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]
>>> nlargest(3,heap) # 返回最大的多个值
[10, 9, 8]
>>> nsmallest(2,heap)# 返回最小的n个值
[3, 4]
>>> heap                    # 不是 inplace操作,heap没变
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]

8.3 双端队列(double-ended queue)

我理解为管道操作,可以两边塞,也可以两边掏。像list一样从中间取一个值,当然可以(如果你非常想要这么做,这不是queue的主要职责)!

>>> from collections import deque
>>> q = deque(list(range(6)))
>>> print(q)
deque([0, 1, 2, 3, 4, 5])
>>> q.append('x') 
>>> q.appendleft('-1')
>>> print(q)
deque(['-1', 0, 1, 2, 3, 4, 5, 'x'])
>>> print(q.pop())
x
>>> print(q.popleft())
-1
>>> print(q)
deque([0, 1, 2, 3, 4, 5])
>>> q.rotate(3)
>>> print(q)
deque([3, 4, 5, 0, 1, 2])
>>> q.rotate(-1)
>>> print(q)
deque([4, 5, 0, 1, 2, 3])
>>> type(q)
<class 'collections.deque'>
>>> q[2] = 10
>>> print(q)
deque([4, 5, 10, 1, 2, 3])

小节

  • 针对list的各种不足,提出了set,heap,deque三种新的数据结构。
  • set能够有效剔除重复数据,同是提供了一套的集合的逻辑操作运算(用的很多,但是自己用list实现是很麻烦的事情)。
  • heap 在与动态更新list数据的时候能够很快的给出排序结果,也就是在push的时候数据的放置位置是按照大小判定的。
  • deque 内在实现就是list,除了操作的便捷性以外(这就够了,不然纯c的天下何须python),我没有发现特别的优势。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,765评论 18 399
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题 本文经过大量细致的优化后,收录于我的新书《编程之法》第六章中,新书...
    Helen_Cat阅读 7,455评论 1 39
  • 国家电网公司企业标准(Q/GDW)- 面向对象的用电信息数据交换协议 - 报批稿:20170802 前言: 排版 ...
    庭说阅读 11,145评论 6 13
  • 娉婷小苑中,婀娜曲池东。 朝佩皆垂地,仙衣尽带风。 七贤宁占竹,三品且饶松。 肠断灵和殿,先皇玉座空。 假如我是棵...
    掬枫阅读 269评论 5 2
  • 文/梁山 人常说:“世界上有三种人最亲人,第一,妈妈。第二,姐姐。第三,姑姑。”确实如此,在我的五十多年的生活...
    长城脚下人家福遇缘阅读 1,080评论 0 1