Python的数据结构整理
一、字典
别名：maps, hashmaps, lookup tables, associative arrays
创建：a={'a':'b'}
优点：对于查找，插入，更新以及删除，时间复杂度为O(1)
变种：
1.collections.OrderedDict
可以记住插入顺序的字典
importcollections
d=collections.OrderedDict(a=1,b=2)
d
Out[3]: OrderedDict([('a', 1), ('b', 2)])
d['c']=3
d
Out[5]: OrderedDict([('a', 1), ('b', 2),('c', 3)])
2.collections.defaultdict
如果没有查到对应的key值，返回默认值的字典
d=collections.defaultdict(list)
d['a'].append(1)
d
Out[12]: defaultdict(list, {'a': [1]})
3.collections.ChainMap
可以当作一个字典去查找多个字典
a={'a':1}
b={'b':2}
chain=collections.ChainMap(a,b)
chain['a']
Out[17]: 1
4. types.MappingProxyType
给字典提供一个只读的视图对象
writable = {'a':1}
import types
read_only = types.MappingProxyType(writable)
read_only['a']
Out[21]: 1
read_only['a']=2
Traceback (most recent call last):
File"<ipython-input-22-5f97afe708c4>", line 1, in <module>
read_only['a']=2
TypeError: 'mappingproxy' object does not support item assignment
writable['b']=2
read_only['b']
Out[24]: 2
二、序列
1.list
可变的动态序列
A=[1,2,3]
2.tuple
不可变的容器
A=(1,2,3)
3.array.array
提供基本的类型序列，存储在里面的序列都是已确定好类型,其实就是C的数组
import array
arr = array.array('f', (1,2,3))
arr
Out[27]: array('f', [1.0, 2.0, 3.0])
4.str
字符串
A=’dad’
5.bytes
不可变的单字节序列
arr=bytes((0,1,))
arr
Out[29]: b'\x00\x01'
6.bytearray
可变的单字节序列
arr=bytearray((0,1,))
arr
Out[31]: bytearray(b'\x00\x01')
7.collections.namedtuple
带名字的tuple，tuple的元素每个都具有自己的名字
tuple1 = collections.namedtuple('test','ab')(1,2)
tuple1
Out[34]: test(a=1, b=2)
三、集合
1.set
无序，内部元素唯一的集合，查找效率是O(1)
A={1,2,3}
2.frozenset
不可变集合
a=frozenset({1,2,3})
3.collections.Counter
内部存储着元素更新次数的集合
a=collections.Counter()
a.update({'a':2})
a
Out[43]: Counter({'a': 2})
a.update({'a':1,'b':2})
a
Out[45]: Counter({'a': 3, 'b': 2})
四、Stacks
1.collections.deque
兼具效率和健壮性的栈
a=collections.deque()
a.append('a')
a.append('b')
a.pop()
Out[49]: 'b'
2.queue.LifoQueue
内置了锁功能的栈，可用于生产者消费者模式的并行
import queue
a=queue.LifoQueue()
a.put('a')
a.put('b')
a.get('a')
Out[54]: 'b'
五、Queues
1.queue.Queue
内置了锁功能的队列，可用于生产者消费者模式的并行
a=queue.Queue()
a.put('a')
a.put('b')
a.get()
Out[61]: 'a'
2. multiprocessing.Queue
可在Job间共享的队列
import multiprocessing
a=multiprocessing.Queue()
a.put('a')
a.put('b')
a.get()
Out[66]: 'a'
六、Prioritity Queues
1.heapq
内部保证相对有序的队列
import heapq
q=[]
heapq.heappush(q,(2,'b'))
heapq.heappush(q,(1,'a'))
heapq.heappush(q,(3,'c'))
while q:
print(heapq.heappop(q))
(1, 'a')
(2, 'b')
(3, 'c')
2. queue.PriorityQueue
支持并发的优先队列
q=queue.PriorityQueue()
q.put((2,'b'))
q.put((1,'a'))
q.put((3,'c'))
while not q.empty():
print(q.get())
(1, 'a')
(2, 'b')
(3, 'c')