Python 数据结构

本文介绍 Python 数据结构的一些基本实现与基本算法。

一、队列、堆、栈相关

1.可迭代对象赋值给多个变量：

1
2
data = ['a','b','c',(2016,4,20)]
a,b,c,date = data

对应个数不同也可以用占位符或者 运算符来解决, 可以放在中间，最前，最后，代表若干个变量，哪怕没有对应元素也返回一个列表。

1
2
_,_,_,date = data
*letter,date = data

可以用 * 运算符实现字符串的分割：

1
2
3
4
5
6
7
8
9
>>> line = 'nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false'
>>> uname, *fields, homedir, sh = line.split(':')
>>> uname
'nobody'
>>> homedir
'/var/empty'
>>> sh
'/usr/bin/false'
>>>

也可以在迭代可变长度的序列时使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
records = [
    ('foo', 1, 2),
    ('bar', 'hello'),
    ('foo', 3, 4),
]

def do_foo(x, y):
    print('foo', x, y)

def do_bar(s):
    print('bar', s)

for tag, *args in records:
    if tag == 'foo':
        do_foo(*args)
    elif tag == 'bar':
        do_bar(*args)

2. 队列

from collections import deque

使用 q = deque（maxlen=N) 函数会构造一个最长长度为 N 的队列，主要方法就是 

1
2
3
4
q.append()
q.appendleft()  # 从队列头添加
q.pop()
q.popleft()     # 从队列头删除并返回
  1. 堆

python 的 heapq 模块中提供了堆结构

heapq.nlargest(N,list,key=def)
heapq.nsmallest(N,list,key=def) # 用来返回list前 N 个最大/最小的元素列表。

还可以传入比较函数：

1
2
3
4
5
6
7
8
9
10
portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

堆结构最重要的特征是 heap[0] 永远是最小的元素，所以用 heapq.headpop(list) 方法可以不断的得到最小元素。

用 heapq 模块实现一个优先级队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        # 这里 进入队列的是一个元组，元组的序列按照 -priority,自身索引来进行排序
        # 优先级越高的元组越‘小’，先出队列，优先级相同的，先进队列的 index 越小，先出队列
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

class Item:
    def __init__(self, name):
         self.name = name
    def __repr__(self):
         return 'Item({!r})'.format(self.name)

>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')

二、字典相关

1. collections 中的字典

collections 中的 defaultdict 工厂函数用来构造自动初始化每个 key 刚开始对应值的字典。例如 defaultdict(list) 构造出每个键对应值都是一个空列表的字典，defaultdict(set) 构造出每个键对应值都是一个空集合的字典，类似于setdefault()函数但更为方便，不用害怕在没有键的情况下取值而报错，在循环是甚至不需要知道key值是什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
d = {} # 传统字典
d.setdefault('a', []).append(1)

d = defaultdict(list)
d['a'].append(1)

d = {}  # 传统的字典，需要先判断 key 是否存在
for key, value in pairs:
    if key not in d:
        d[key] = []
    d[key].append(value)

d = defaultdict(list) 
# defaultdict 不需要判断key是否存在直接在 value 对应的list中进行操作
for key, value in pairs:
    d[key].append(value)

OrderedDict 可以在迭代操作时保留元素被插入时的顺序，因为其内部维护着一个根据 Key 插入
顺序排序的双向链表，每次当新元素插入时被放在链表的尾部，对已经存在的Key重复赋值不会改变其顺序，因此 OrderedDict 的大小是普通字典的两倍。

2. 字典运算

zip() 函数用来封装字典，比如：

1
2
3
4
5
6
7
8
9
10
11
12
prices = {
    'ACME': 45.23,
    'AAPL': 612.78,
    'IBM': 205.55,
    'HPQ': 37.20,
    'FB': 10.75
}

min_price = min(zip(prices.values(), prices.keys()))
#zip() 封装 prices 的values和keys将键值倒转，然后min对新key取最小值，当新key值相同时，对value进行比较
#类似的，也可以用 sort() 函数进行排序
#但需要注意的是：zip() 函数返回的不是一个字典，而是一个一次性迭代器，只能访问一次

对字典的 keys() 和 values() 进行集合运算：

1
2
3
4
5
6
7
8
9
10
# Find keys in common
a.keys() & b.keys()
# Find keys in a that are not in b
a.keys() - b.keys() 
# Find (key,value) pairs in common
a.items() & b.items() 
# 返回一个排除掉 key 为 z,w 的 a 字典
c = {key:a[key] for key in a.keys() - {'z', 'w'}}
# 字典的 .keys()/.items() 返回的对象都支持集合相关的操作(但不是集合)
# .values() 由于不能保证元素的唯一性并不能进行集合操作，需要强制转换成set()

消除重复元素并保留顺序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ddef dedupe(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
# 对于 Hashable 类型元素，进行利用集合和生成器，然后将返回的生成器转换成list类型即可。
            seen.add(val)
# 对于非 Hashable 类型的元素，比如字典类型，需要传入参数将其转换为 Hashable 类型

>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> list(dedupe(a))
[1, 5, 2, 9, 10]

>>> a = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]
>>> list(dedupe(a, key=lambda d: (d['x'],d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(a, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]

三、杂项

1. 切片命名

a = slice(start,stop,step) 可以对切片范围进行命名，此时list(a)和 list[start:stop:step] 是等价的。

slice() 函数创建的对象有 a.atart,a.stop,a.step 等相应属性。
a.indices(size) 方法会返回一个基于切片a且符合size大小的三元组，所有值都会被适当的缩小以满足边界限制。

2. collections.Counter

collections.Counter(list) 用来为list计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
words = [
    'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
    'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the',
    'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into',
    'my', 'eyes', "you're", 'under'
]
from collections import Counter
word_counts = Counter(words)
print(word_counts.most_common(3))
# 打印出现频率最高的三个单词
print(word_counts['look'])
# Counter 对象类似一个字典，Key为list中的hashable对象，value 为出现次数
morewords = ['why','are','you','not','looking','in','my','eyes']
word_counts.update(morewords)
# update() 方法可以更新统计的list
  1. loading