数据结构与算法 (02)

继续 Python Cookbook, 还是偏向技巧性的, 应用性的, 这一遍过完, Python 作为我的第一生产力, 应该是没有啥争议的了, 当然, 不过完, 也是我的第一生产了, 第二是 SQL .

查询最大 或 最小 的 N 个元素

需求

从集合中, 获取最大或最小的 N 个元素列表

方案

应用 堆 heap 这个结构. 内置的 heapq 模块有两个函数: nlargest() 和 nsmallest() 可以完美解决这个问题.

import heapq

nums = [1,8,2,7,-4,18,23,666,2]

print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3,nums))

[666, 23, 18]
[-4, 1, 2]

两个函数都能接受一个关键字参数, 用于更加复杂的数据结构中. 就是字典按值排序的场景哦.

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}
            ]
# 按照某个字段的值来排序, 这里按照 price 作为排序依据
print(heapq.nsmallest(3, portfolio, key=lambda s: s['price']))
print('--'*35)
print(heapq.nlargest(3, portfolio, key=lambda s: s['price']))

[{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}]
----------------------------------------------------------------------
[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'IBM', 'shares': 100, 'price': 91.1}]

如果我们想在一个集合中查找最大 或 最小 N 个元素, 则 heapq 这个模块提供了很高效的性能解决方案. 因为在底层实现最, 首先会将集合数据进行排序后, 放到一个列表中. 当然 堆的底层实现, 也不难, 这里就不展示底层了.

nums = [1, 8, 23, 7, -4, 23, 38, 2]

# 将列表数据进行 堆排序
heap = list(nums)
heapq.heapify(heap)

print(heap)

[-4, 1, 23, 2, 8, 23, 38, 7]

堆这种数据结构最为重要的特征是 heap[0] 永远是最小的元素. 而剩余的元素可以很容易通过调用 heap.heappop() 方法得到. 该方法是, 首先将第一个元素弹出来, 然后用下个最小元素来代替被弹出的元素. (这种操作的时间复杂度仅 (O(log N))

比如, 想要查询最小的 3 个元素

# 每次都 pop 出最小的元素
print(heapq.heappop( heap))
print(heapq.heappop(heap))
print(heapq.heappop(heap))

-4
1
2

当要查找的元素的个数相对比较小的时候, 函数 nlargest() 和 nsmallest() 是比较合适的. 但如果只是想最大 或 最小这种极值, min() 和 max() 会更快哦. 合理利用就好. 堆结构的实现, 我感觉还是比较有意思的, 后面专门写一篇原理实现, 手动来封装一个 堆呢.

实现一个优先级队列

需求

实现一个按优先级排序的队列, 并在该队列上, 每次 pop 操作总是返回优先级最高的那个元素.

方案

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0
        
    def push(self, item, priority):
        # 负号的目的是使元素按优先级从高到低排序, index 是为了插入顺序排序
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1
        
    def pop(self):
        return heapq.heappop(self._queue)[-1]
    
    

class Item:
    def __init__(self, name):
        self.name = name
        
    # __repr__() 在 print(实例对象)时会被调用
    
    def __repr__(self):
        return f"Item({self.name})"
    
    
# test
q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)

print(q.pop())
print(q.pop())
print(q.pop())
print(q.pop())

Item(bar)
Item(spam)
Item(foo)
Item(grok)

可以看出, 第一个 pop () 是返回优先级最高的元素. 如果级别相同, 则按照它们被插入到队列的顺序返回.

这些例子还是对 heapq 这个模块, 封装了 堆这种数据结构的认识. heapq.heappush() 和 heapq.heappop () 分别在队列 _queue 上插入和删除第一个元素. 且队列 _queue 总是保证第一个元素拥有最高优先级. heappop() 方法总是返回 "最小的" 的元素. push 和 pop 的时间复杂度都是 (O(log N)), 即便是 N 很大, 运行的速度也很快, 所 堆这个结构, 以后多用就对了.

字典中一键映射多值

需求

实现在一个字典中, 一个键对应多个值 (multidict)

方案

字典和其他容器, 如 list 进行嵌套即可.

组织数据的时候, 我常用 [{}, {}, {}, {}] 这样的方式来组织数据哦

d = {
    'a': [1, 2, 3],
    'b': [4, 5]
}
e = {
    'a': {1, 2, 3},
    'b': {4, 5}
}

这是平时工作中, 会经常用的, 如 列表嵌套字典, 或者 字典嵌套列表等...看实际需求来自由组合即可. 当然, 如果想保持元素的插入顺序, 则使用列表, 如过想对元素去重则可使用 集合 set

可使用 collections.defaultdict 来构造这样的字典. (自己实现也行的) defaultdict 的一个特点是, 它会自动初始化每个 key 刚开始对应的值.

from collections import defaultdict

d = defaultdict(list)

d['a'].append(1)
d['a'].append(2)
d['b'].append(4)
print(d)

d = defaultdict(set)

d['a'].add(1)
d['a'].add(2)
d['b'].add(4)
print(d)

defaultdict(<class 'list'>, {'a': [1, 2], 'b': [4]})
defaultdict(<class 'set'>, {'a': {1, 2}, 'b': {4}})

defautdict 会自动给将要被访问的 key 即便不存在, 创建映射的实体. 类似于 sql 中的主键更新. 当然也可以在普通的字典上用 setdefault() 方法得了代替

d = {}

d.setdefault('a', []).append(1)
d.setdefault('a', []).append(2)
d.setdefault('b', []).append(4)

print(d)

{'a': [1, 2], 'b': [4]}

我其实平时就是这样来用的, 有点变扭, 不够优雅, 每次调用还得创建一个新的初始值实例, 感觉怪怪的.

d = {}
for key, value in pairs:
    # if key not in d:
    if not d.get(key):
        d[key] = []
    d[key].append(value)

一般做词频统计之类的就会类似的操作, 当然我更喜欢用 get() 方法, 没取到就返回 None, 而不报错, 增强鲁棒性嘛.

但现在如果用 defaultdict 来实现则就非常优雅了.

from collections import defaultdict

d = defaultdict(list)
for key, value in pairs:
    d[key].append(value)

这种写法确实挺香的呀.

字典排序

需求

创建一个字典, 在迭代或序列化这个字典的时候能够控制元素的顺序

方案

可用 collections 中的 OrderedDict 类. 在进行迭代操作时候, 它会保持元素被插入的顺序.

from collections import OrderedDict

d = OrderedDict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grok'] = 4

print(d)

for key in d:
    print(key, d[key])

OrderedDict([('foo', 1), ('bar', 2), ('spam', 3), ('grok', 4)])
foo 1
bar 2
spam 3
grok 4

比较有意思的是, 在 3.8 版本以后, 字典已经是有序的了, 而我还在 3.6 似乎跟不上潮流了哦. 字典有序, 其实应用场景还是蛮多的, 有时候序列化的时候, 就期望字段是有序的.

# d 已经是 OrderedDict 有序了
import json 

json.dumps(d)

'{"foo": 1, "bar": 2, "spam": 3, "grok": 4}'

dumps () 和 loads() 总是分不清也没关系, 每次使用前试试就知道了呀

刚也是在 3.8以后的版本已经实现字典排序了. 这里的 OrderedDict 内部维护着一个根据键插入顺序排序的 双向链表. 元素插入, 则会被放到链表的尾部. 对一个已存在的键重复赋值则不会改变键的顺序.

OrderedDict 的大小是普通字典的 2倍. 如果数据非常大的话, 那就要考虑性能了. 虽然我也不知道3.8以后的字典字典有序是咋实现的, 但肯定性能是不如之前无序的.

字典内运算

需求

在一个字典中执行一些计算操作 (max, min, sort ...) 等

方案

针对键, 值 灵活应用计算函数即可.

# 股票价格
prices = {
    'ACME': 45.23,
    'AAPL': 612.78,
    'IBM': 255.55,
    'HPQ': 37.20,
    'FB': 10.57
}

现在要对 值 进行操作, 可用 zip() 函数, 将键值反转.

# 查找最小, 最大股票价格 和 对应的股票代码
min_price = min(zip(prices.values(), prices.keys()))
print('min_price', min_price)

max_price = max(zip(prices.values(), prices.keys()))
print('max_price', max_price)

min_price (10.57, 'FB')
max_price (612.78, 'AAPL')

类似的, 用 zip() 和 sorted() 函数来对字典进行排序

sorted(zip(prices.values(), prices.keys()))

[(10.57, 'FB'),
 (37.2, 'HPQ'),
 (45.23, 'ACME'),
 (255.55, 'IBM'),
 (612.78, 'AAPL')]

需要注意的是, zip() 函数创建的是一个 只能访问一次 的迭代器. 其实 sort 这块而言, 更常用的是, 对字典进行安值排序, 不用之前的 OrderedDict 类来完成.

#  字典按值降序
sorted(d.items(), key=lambda arr: arr[1], reverse=True)

[('grok', 4), ('spam', 3), ('bar', 2), ('foo', 1)]

按值降序, 还是我之前遇到的一个笔试题, 当时没用 sorted, 自己写了个冒泡排序, 然后拼接字典, 感觉当时还蛮厉害的. 工作中, 还是用内置函数吧, 毕竟一行代码就搞定了.

要对值进行操作呢, values() 可能也不会满足需求, 这时候就需要 key 这个参数来获取对应的极值了.

print(min(prices, key=lambda k: prices[k]))

print(max(prices, key=lambda k: prices[k]))

print(prices[max(prices, key=lambda k: prices[k])])

FB
AAPL
612.78

zip() 函数, 轻松将字典的 键 - 值 进行反转, 这种操作还是蛮厉害的. 操作完, 又可以通过 zip () 可逆回来的.

查询两字典的相同点

需求

寻找两个字典中的相同点 (相同键, 相等值...)

a = { 'x' : 1, 'y' : 2, 'z' : 3 }
b = { 'w' : 10, 'x' : 11, 'y' : 2 }

找寻键, 值的相同点, 可以通过 keys(), 或 values() 或 items() 的返回结果上进行 集合操作.

# find keys in commom 交集
print(a.keys() & b.keys())

# find keys in a that are not in b  即 a 的对称差集
print(a.keys( ) - b.keys())

# find (key, value) pairs in common 交集
print(a.items() & b.items())

{'x', 'y'}
{'z'}
{('y', 2)}

这种集合操作, 也可用来过滤字典元素. 如这个,字典推导式来实现过滤某些键

# 字典推导式
{key: a[key] for key in a.keys() - {'z', 'w'}}

{'x': 1, 'y': 2}

我觉得, Python 中, 引入集合, 这就已经是非常强大了, 个人观点哈.

小结

• 多用堆 heap 这种结构, heapq.nlargest(), heapqnsmallest(), heapq.heappop(), heappush() 复杂 (O(logN))
• 字典一键多值 collections.defaultdict , 还有字典键值反转 zip() , 按值降序 sorted 函数等应用
• 字典的 keys(), values(), items() 配合 聚合函数的 key, 字典key 的集合 set 运算, 交并补等骚操作