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"", line 1, in

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=

2.frozenset

不可变集合

a=frozenset()

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')