2022-04-30  6f93ebcc77208ff8f926e6bc29916f4d 99+   1 小时   7.3 k0次访问

Python实战之数据结构和算法

傍晚时分，你坐在屋檐下，看着天慢慢地黑下去，心里寂寞而凄凉，感到自己的生命被剥夺了。当时我是个年轻人，但我害怕这样生活下去，衰老下去。在我看来，这是比死亡更可怕的事。——–王小波

写在前面

  • 博文为《Python Cookbook》读书笔记整理
  • 博文内容涉及：
    • 解构序列赋值给多个变量
    • 解构可迭代对象赋值给多个变量
    • 保留最后N个元素
    • 查找最大或最小的N个元素
    • 实现一个优先级队列
    • 字典中的键映射多个值
    • 字典排序.
    • 查找两字典的相同点
    • 删除序列相同元素并保持顺序
    • 序列中出现次数最多的元素
    • 通过某个关键字排序一个字典列表
    • 排序不支持原生比较的对象.
    • 通过某个字段将记录分组
    • 映射名称到序列元素
    • 转换并同时计算数据
    • 合并多个字典或映射
  • 理解不足小伙伴帮忙指正

傍晚时分，你坐在屋檐下，看着天慢慢地黑下去，心里寂寞而凄凉，感到自己的生命被剥夺了。当时我是个年轻人，但我害怕这样生活下去，衰老下去。在我看来，这是比死亡更可怕的事。——–王小波

数据结构和算法

Python内置了许多非常有用的数据结构，比如列表(list)、集合(set)以及字典(dictionary)、元组(tuple)。在collections模块中也包含了针对各种数据结构的解决方案。

将序列分解为单独的变量

我们有一个包含N个元素的元组或序列,现在想将它分解为N个单独的变量。

1
2
3
4
5
6
7
8
9
10
11
12
┌──(liruilong㉿Liruilong)-[/mnt/e/docker]
└─$ python3
Python 3.9.10 (main, Jan 16 2022, 17:12:18)
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> p = (4,5)
>>> x,y = p
>>> x
4
>>> y
5
>>>

居然可以这样，长见识了，类似于JavaScript ES6中的解构赋值,如果当成函数对象来看，可以看做是拆包

1
2
3
4
5
6
7
>>> data = [ 'ACME',50,91.1,(2012,12,21)]
>>> n,s,p,d = data
>>> n,s
('ACME', 50)
>>> d
(2012, 12, 21)
>>>

当然，也支持深层次解构

1
2
3
4
5
6
7
>>> data = [ 'ACME',50,91.1,(2012,12,21)]
>>> name,shares,price,(year,mon,day)=data
>>> year
2012
>>> mon,day
(12, 21)
>>>

如果元素的数量不匹配，将得到一个错误提示。

1
2
3
4
5
6
>>> p = (4,5)
>>> x,y,z = p
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: not enough values to unpack (expected 3, got 2)
>>>

实际上不仅仅只是元组或列表，只要对象恰好是可迭代的，那么就可以执行分解操作。这包括字符串、文件、迭代器以及生成器。

1
2
3
4
5
6
7
>>> s = 'love'
>>> a,b,c,d = s
>>> a,b
('l', 'o')
>>> d
'e'
>>>

当做分解操作时，想丢弃某些特定的值。可以用 ‘_’充当占位符，，这个在JavaScript ES6和Golang也都支持。

1
2
3
4
5
>>> data = [ 'ACME',50,91.1,(2012,12,21)]
>>> _,_,a,_=data
>>> a
91.1
>>>

从任意长度的可迭代对象中分解元素

需要从某个可选代对象中分解出N个元素，但是这个可迭代对象的长度可能超过N，这会导致出现分解的值过多(too many values to unpack)的异常。

1
2
3
4
5
6
7
>>> record=('Dave','davedexample.com','773-555-1212','1847-555-1212')
>>> name,email,*phone_numbers = record
>>> name
'Dave'
>>> phone_numbers
['773-555-1212', '1847-555-1212']
>>>

类似于Java方法传值的可变参数一样，但是要比java高级的多，java的可变参数只能最后一个,python 则可以在任意位置

1
2
3
4
5
6
7
>>> record=('Dave','davedexample.com','1224965096@qq.com','773-555-1212')
>>> name,*email,phone = record
>>> name
'Dave'
>>> email
['davedexample.com', '1224965096@qq.com']
>>>

* 式的语法在选代一个变长的元组序列时尤其有用

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)

字符串拆分是的使用 : ''.split('')

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'
>>> sh
'/usr/bin/false'
>>> fields
['*', '-2', '-2', 'Unprivileged User']
>>>

也可 '*' 和 '_' 两个连用，丢弃多个变量

1
2
3
4
>>> uname,*_,homedir,sh=line.split(':')
>>> sh
'/usr/bin/false'
>>>

求和递归

1
2
3
4
items=[1,10,7,4,5,9]
def sum(items): 
    head,*tail=items 
    return head+sum(tail) if tail else head

保存最后N个元素(队列)

我们希望在迭代或是其他形式的处理过程中对最后几项记录做一个有限的历史记录统计。

保存有限的历史记录可算是collections.deque的完美应用场景了

打印满足条件的最后5条记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#deque(maxlen=N)创建了一个固定长度的双端队列
from collections import deque

def search(lines, pattern, history=5):
    previous_lines=deque(maxlen=history)
    for line in lines:
        if pattern in line:
            # 生成器
            yield line, previous_lines
        previous_lines.append(line)
# Example use on a file
if __name__ == '__main__':
    with open('somefile.txt') as f:
        for line, prevlines in search(f,'python',5):
            for pline in prevlines:
                print(pline, end='')
            print(line, end='')
            print('-1'*20)

deque(maxlen=N)创建了一个固定长度的双端队列

1
2
3
4
5
6
7
8
>>> from collections import deque
>>> q = deque()
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3])
>>>

尽管可以在列表上手动完成这样的操作(append、del)，但队列这种解决方案要优雅得多，运行速度也快得多。从队列两端添加或弹出元素的复杂度都是O(1)。这和列表不同，当从列表的头部插入或移除元素时，列表的复杂度为O(N)

找到最大或最小的N个元素

我们想在某个集合中找出最大或最小的N个元素。

heapq模块中有两个函数nlargest()和nsmallest(),当所要找的元素数量相对较小时，函数nlargest()和nsmallest()才是最适用的,nlargest()和nsmallest()的实际实现会根据使用它们的方式而有所不同，可能会相应作出一些优化措施(比如，当N的大小同输入大小很接近时，就会采用排序的方法)。

1
2
3
4
5
6
7
>>> import heapq
>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]
>>> heapq.nlargest(3,nums)
[42, 37, 23]
>>> heapq.nsmallest(3,nums)
[-4, 1, 2]
>>>

这两个函数都可以接受一个参数key，从而允许它们工作在更加复杂的数据结构之上

1
2
3
4
5
6
7
8
9
10
11
import  heapq

portfoli = [
    {'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}
]
print(heapq.nsmallest(2,portfoli,key=lambda s: s['price']))
print(heapq.nlargest(2,portfoli,key=lambda s: s['shares']))
1
2
[{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}]
[{'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'ACME', 'shares': 75, 'price': 115.65}]

如果正在寻找最大或最小的N个元素，且同集合中元素的总数目相比，N很小，那么heapq.heapify(heap)函数可以提供更好的性能。这些函数首先会在底层将数据转化成列表，且元素会以堆的顺序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> nums
[1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heap=list(nums)
>>> heapq.heapify(heap)
>>> heap
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
>>> heapq.heappop(heap)
-4
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
>>>

堆最重要的特性就是heap[0]总是最小那个的元素。此外，接下来的元素可依次通过heapq.heappop方法轻松找到。该方法会将第一个元素(最小的)弹出，然后以第二小的元素取而代之(这个操作的复杂度是O(logN)，N代表堆的大小)

想找到最小或最大的元素(N=1时)，那么用min()和max)会更加快。

1
2
3
4
5
6
7
>>> min(heap)
2
>>> max(heap)
42
>>> heap
[2, 7, 8, 23, 42, 37, 18, 23]
>>>

如果N和集合本身的大小差不多大，通常更快的方法是先对集合排序，然后做切片操作,使用sorted(items)[：N]或者sorted(items)[-N:])。

实现优先级队列

我们想要实现一个队列，它能够以给定的优先级来对元素排序，且每次pop操作时都会返回优先级最高的那个元素。

heapq模块提供了堆排序算法的实现,heapq有两种方式创建堆，

  • 一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中
  • 一种就是使用heap.heapify(list)转换列表成为堆结构
    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
    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))
            self._index += 1
        def pop(self):
            return heapq.heappop(self._queue)[-1]

    class Item:
        def __init__(self, name):
            self.name = name

        def __repr__(self):
            #!r直接反应对象本体
            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)
    print(q.pop())
    print(q.pop())
    print(q.pop())
    队列以元组(-priority，index，item)的形式组成。把priority取负值是为了让队列能够按元素的优先级从高到低的顺序排列。一般情况下是最小堆。

变量index的作用是为了将具有相同优先级的元素以适当的顺序排列。通过维护一个不断递增的索引，元素将以它们入队列时的顺序来排列。没有哪两个元组会有相同的index值(一旦比较操作的结果可以确定，Python就不会再去比较剩下的元组元素了)

如果想将这个队列用于线程间通信，还需要增加适当的锁和信号机制

在字典中将键映射到多个值上

我们想要一个能将键(key)映射到多个值的字典(即所谓的一键多值字典[multidict])

字典是一种关联容器，每个键都映射到一个单独的值上。如果想让键映射到多个值，需要将这多个值保存到另一个容器如列表或集合中。

为了能方便地创建这样的字典，可以利用collections模块中的defaultdict类。defaultdict的一个特点就是它会自动初始化第一个值，这样只需关注添加元素即可。

1
2
3
4
5
6
7
8
defaultdict(<class 'list'>, {'a': [1, 2], 'b': [4]})
>>> from  collections import defaultdict
>>> d = defaultdict(list)
>>> d['a'].append(1)
>>> d['a'].append(2)
>>> d['b'].append(4)
>>> d
defaultdict(<class 'list'>, {'a': [1, 2], 'b': [4]})
1
2
3
4
5
6
7
>>> d= defaultdict(set)
>>> d['a'].add(1)
>>> d['a'].add(3)
>>> d['a'].add(3)
>>> d
defaultdict(<class 'set'>, {'a': {1, 3}})
>>>

用于分组，有一种java8里面Stream的味道

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

让字典保持有序

要控制字典中元素的顺序，可以使用collections模块中的OrderedDict类。当对字典做迭代时，它会严格按照元素初始添加的顺序进行。例如：

1
2
3
4
5
6
7
8
>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> d['1']=1
>>> d['2']=2
>>> d['3']=3
>>> d
OrderedDict([('1', 1), ('2', 2), ('3', 3)])
>>>

当想构建一个映射结构以便稍后对其做序列化或编码成另一种格式时，OrderedDict就显得特别有用。例如，如果想在进行JSON编码时精确控制各字段的顺序，那么只要首先在OrderedDict中构建数据就可以了。

1
2
3
4
>>> import json
>>> json.dumps(d)
'{"1": 1, "2": 2, "3": 3}'
>>>

OrderedDict 内部维护了一个双向链表，它会根据元素加入的顺序来排列键的位置。第一个新加入的元素被放置在链表的末尾。接下来对已存在的键做重新赋值不会改变键的顺序。

OrderedDict的大小是普通字典的2倍多，这是由于它额外创建的链表所致。因此，如果打算构建一个涉及大量OrderedDict实例的数据结构(例如从CSV文件中读取100000行内容到OrderedDict列表中)，那么需要认真对应用做需求分析，是否可以用内存换便利

与字典有关的计算问题

我们想在字典上对数据执行各式各样的计算(比如求最小值、最大值、排序等)。

通常会利用zip()将字典的键和值反转过来

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> prices={
... 'ACME':45.23,
... 'AAPL':612.78,
... 'IBM1':205.55,
... 'HPQ':37.20,
... 'FB':10.75
... }
>>>
>>> min(zip(prices.values(),prices.keys()))
(10.75, 'FB')
>>> max(zip(prices.values(),prices.keys()))
(612.78, 'AAPL')
>>>

同样，要对数据排序只要使用zip()再配合sorted()就可以了

1
2
3
>>> sorted(zip(prices.values(),prices.keys()))
[(10.75, 'FB'), (37.2, 'HPQ'), (45.23, 'ACME'), (205.55, 'IBM1'), (612.78, 'AAPL')]
>>>

zip()创建了一个迭代器，它的内容只能被消费一次,尝试对字典的值做计算。可以利用字典的values()方法来解决这个问题：但是对于K的获取并不方便。

在计算min()和max()时，如果碰巧value的值相同，则将返回拥有最小或最大key值的那个条目。

在两个字典中寻找相同点(交集)

有两个字典，我们想找出它们中间可能相同的地方(相同的键、相同的值等)。

关于字典的键有一个很少有人知道的特性，那就是它们也支持常见的集合操作，比如求并集、交集和差集。

如果需要对字典的键做常见的集合操作，那么就能直接使用keys-view对象而不必先将它们转化为集合。获取到迭代器，可以直接对字典进行运算交集差集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> a = {
... 'x':1,
... 'y':2,
... 'z':3
... }
>>> b = {
... 'w':10,
... 'x':11,
... 'y':2
... }
>>> a.keys() & b.keys()
{'y', 'x'}
>>> a.keys() - b.keys()
{'z'}

字典的items()方法返回由(key，value)对组成的items-view对象。这个对象支持类似的集合操作，可用来完成找出两个字典间有哪些键值对有相同之处的操作。

1
2
3
>>> a.items() & b.items()
{('y', 2)}
>>>

也可以对字典进行过滤。

1
2
3
>>> {key:a[key] for key in a.keys() - {'z','W'}}
{'y': 2, 'x': 1}
>>>

字典的values()方法并不支持集合操作。部分原因是因为在字典中键和值是不同的，从值的角度来看并不能保证所有的值都是唯一的。

从序列中移除重复项且保持元素间顺序不变

我们想去除序列中出现的重复元素，但仍然保持剩下的元素顺序不变。

如果序列中的值是可哈希(hashable)的，那么这个问题可以通过使用集合和生成器轻松解决。

1
2
3
4
5
6
7
8
9
10
11
12
def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item #生成有序列表
            seen.add(item)


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

如果没办法生成哈希值，如果一个对象是可哈希的，那么在它的生存期内必须是不可变的，它需要有一个hash()方法。

整数、浮点数、字符串、元组都是不可变的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def 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
            seen.add(val)



a=[{'x':1,'y':2},{'x':1,'y':3},{'x':1,'y':2},{'x':2,'y':4}]
#转化为元组
print(list(dedupe(a,key=lambda b:(b['x'],b['y']))))

这里参数key的作用是指定一个函数用来将序列中的元素转换为可哈希的类型，这么做的目的是为了检测重复项。即行为参数化，lambda表达式的使用。

对切片命名

我们的代码已经变得无法阅读，到处都是硬编码的切片索引，我们想将它们清理干净

即通过对切片变量的定义，把可变的部分抽离出来。一般来说，内置的slice()函数会创建一个切片对象，可以用在任何允许进行切片操作的地方。

1
2
3
4
5
6
7
>>> recode='343534534532423435346547543534534534534564634534'
>>> int(recode[12:14]) * float(recode[10:13])
13608.0
>>> a = slice(12,14)
>>> b = slice(10,13)
>>> int(recode[a]) * float(recode[b])
13608.0

查看切片对象属性

1
2
3
4
5
6
>>> a.start
12
>>> a.stop
14
>>> a.step
>>>

通过使用indices(size)方法将切片映射到特定大小的序列上。

1
2
3
4
>>> s = "liruilong"
>>> a.indices(len(s))
(9, 9, 1)
>>>

找出序列中出现次数最多的元素

怎样找出一个序列中出现次数最多的元素呢？

collections.Counter 类就是专门为这类问题而设计的，它甚至有一个有用的most_common()方法直接给了你答案。

出现频率最高的 3 个单词

1
2
3
4
5
6
7
8
9
10
11
12
>>> 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)
>>> word_counts.most_common(3)
[('eyes', 8), ('the', 5), ('look', 4)]
>>> word_counts.most_common(1)
[('eyes', 8)]

作为输入，Counter 对象可以接受任意的hashable序列对象。在底层实现上，一个Counter对象就是一个字典，将元素映射到它出现的次数上

1
2
3
>>> word_counts
Counter({'eyes': 8, 'the': 5, 'look': 4, 'into': 3, 'my': 3, 'around': 2, 'not': 1, "don't": 1, "you're": 1, 'under': 1})
>>>

可以整合其他的容器来统计数据,下面为在原有基础上整合一个列表

1
2
3
4
5
6
7
>>> morewords = ['why','are','you','not','looking','in','my','eyes']
>>> for word in morewords:
...   word_counts[word] += 1
...
>>> word_counts
Counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2, 'around': 2, "don't": 1, "you're": 1, 'under': 1, 'why': 1, 'are': 1, 'you': 1, 'looking': 1, 'in': 1})
>>>

当然，也可以通过update()方法,我们可以看到，update方法并没有替换原来的value，而是进行了累加，和字典的update方法有区别

1
2
3
4
>>> word_counts.update(morewords)
>>> word_counts
Counter({'eyes': 10, 'my': 5, 'the': 5, 'look': 4, 'into': 3, 'not': 3, 'around': 2, 'why': 2, 'are': 2, 'you': 2, 'looking': 2, 'in': 2, "don't": 1, "you're": 1, 'under': 1})
>>>

Counter生成的数据字典可以进行数据运算，只是针对相同Key的Value而言

1
2
3
4
5
6
7
8
9
10
11
>>> morewords = ['why','are','you','not','looking','in','my','eyes']
>>> 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
>>> Counter(words) + Counter(morewords)
Counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2, 'around': 2, "don't": 1, "you're": 1, 'under': 1, 'why': 1, 'are': 1, 'you': 1, 'looking': 1, 'in': 1})
>>>

通过某个关键字排序一个字典列表

你有一个字典列表，你想根据某个或某几个字典字段来排序这个列表。

通过使用 operator 模块的 itemgetter 函数，可以非常容易的排序这样的数据结构。感觉和heapq模块中的函数nlargest()和nsmallest()有些类似

1
2
3
4
5
6
7
8
9
>>> rows = [
... {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
... {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
... {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
... {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
... ]
>>> from operator import itemgetter
>>> sorted(rows, key=itemgetter('fname'))
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}]

rows 被传递给接受一个关键字参数的sorted()内置函数,参数是 callable 类型，从rows中接受一个单一元素，然后返回被用来排序的值,itemgetter() 函数就是负责创建这个 callable 对象的。

1
2
>>> sorted(rows, key=itemgetter('uid'))
[{'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}]

itemgetter() 函数也支持多个 keys，如果你传入多个索引参数给 itemgetter() ，它生成的 callable 对象会返回一个包含所有元素值的元组，并且 sorted() 函数会根据这个元组中元素顺序去排序比如下面的代码

1
2
3
>>> sorted(rows, key=itemgetter('lname','fname'))
[{'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>>

itemgetter() 有时候也可以用 lambda 表达式代替

1
2
3
4
5
>>> sorted(rows, key=lambda r: r['fname'])
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}]
>>> sorted(rows, key=lambda r: (r['lname'],r['fname']))
[{'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>>

使用 itemgetter() 方式会运行的稍微快点。同样适用于 min() 和 max() 等函数

1
2
3
4
5
6
>>> import  heapq
>>> heapq.nsmallest(2,rows,key=itemgetter('fname'))
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>> min(rows,key=itemgetter('fname'))
{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
>>>

排序不支持原生比较的对象

你想排序类型相同的对象，但是他们不支持原生的比较操作

内置的 sorted() 函数有一个关键字参数 key ，可以传入一个 callable 对象给它,这个 callable 对象对每个传入的对象返回一个值，这个值会被 sorted 用来排序

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
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    :   user.py
@Time    :   2022/04/29 19:35:33
@Author  :   Li Ruilong
@Version :   1.0
@Contact :   1224965096@qq.com
@Desc    :   None
"""

# here put the import lib


class User:
    def __init__(self, user_id):
        self.user_id = user_id

    def __repr__(self):
        return 'User({})'.format(self.user_id)


def sort_notcompare():
    users = [User(23), User(3), User(99)]
    print(users)
    print(sorted(users, key=lambda u: u.user_id))

if __name__ == "__main__" : 
    sort_notcompare()
============
[User(23), User(3), User(99)]
[User(3), User(23), User(99)]

另外一种方式是使用 operator.attrgetter() 来代替 lambda 函数：

1
2
from operator import attrgetter
print(sorted(users, key=attrgetter('user_id')))

attrgetter() 函数通常会运行的快点，并且还能同时允许多个字段进行比较

1
sorted(users, key=attrgetter('last_name', 'first_name'))

跟 operator.itemgetter() 函数作用于字典类型很类似 ,同样适用于像 min() 和 max() 之类

通过某个字段将记录分组

你有一个字典或者实例的序列，然后你想根据某个特定的字段比如 date 来分组迭代访问。

itertools.groupby() 函数对于这样的数据分组操作非常实用。为了演示，假设你已经有了下列的字典列表

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
>>> rows = [
... {'address': '5412 N CLARK', 'date': '07/01/2012'},
... {'address': '5148 N CLARK', 'date': '07/04/2012'},
... {'address': '5800 E 58TH', 'date': '07/02/2012'},
... {'address': '2122 N CLARK', 'date': '07/03/2012'},
... {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
... {'address': '1060 W ADDISON', 'date': '07/02/2012'},
... {'address': '4801 N BROADWAY', 'date': '07/01/2012'},
... {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
... ]
>>> from operator import itemgetter
>>> from itertools import groupby
>>> rows.sort(key=itemgetter('date'))
>>> for date, items in groupby(rows, key=itemgetter('date')):
...     print(date)
...     for i in items:
...             print(' ', i)
...
07/01/2012
  {'address': '5412 N CLARK', 'date': '07/01/2012'}
  {'address': '4801 N BROADWAY', 'date': '07/01/2012'}
07/02/2012
  {'address': '5800 E 58TH', 'date': '07/02/2012'}
  {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'}
  {'address': '1060 W ADDISON', 'date': '07/02/2012'}
07/03/2012
  {'address': '2122 N CLARK', 'date': '07/03/2012'}
07/04/2012
  {'address': '5148 N CLARK', 'date': '07/04/2012'}
  {'address': '1039 W GRANVILLE', 'date': '07/04/2012'}
>>>

groupby()函数扫描整个序列并且查找连续相同值(或者根据指定key函数返回值相同)的元素序列。在每次选代的时候,它会返回一个值和一个选代器对象,这个选代器对象可以生成元素值全部等于上面那个值的组中所有对象。

一个非常重要的准备步骤是要根据指定的字段将数据排序 。因为groupby()仅仅检查连续的元素

如果你仅仅只是想根据date字段将数据分组到一个大的数据结构中去,并且允许随机访问,最好使用defaultdict()来构建一个多值字典

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
36
37
38
39
40
>>> from collections import defaultdict
>>> rows_by_date = defaultdict(list)
>>> rows = [
N CLARK', 'date': '07/03/... {'address': '5412 N CLARK', 'date': '07/01/2012'},
... {'address': '5148 N CLARK', 'date': '07/04/2012'},
... {'address': '5800 E 58TH', 'date': '07/02/2012'},
... {'address': '2122 N CLARK', 'date': '07/03/2012'},
... {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
... {'address': '1060 W ADDISON', 'date': '07/02/2012'},
... {'address': '4801 N BROADWAY', 'date': '07/01/2012'},
... {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
... ]
>>> for row in rows:
...     rows_by_date[row['date']].append(row)
...
>>> rows_by_date
defaultdict(<class 'list'>, 
{'07/01/2012': [
        {'address': '5412 N CLARK', 'date': '07/01/2012'
        },
        {'address': '4801 N BROADWAY', 'date': '07/01/2012'
        }
    ], '07/04/2012': [
        {'address': '5148 N CLARK', 'date': '07/04/2012'
        },
        {'address': '1039 W GRANVILLE', 'date': '07/04/2012'
        }
    ], '07/02/2012': [
        {'address': '5800 E 58TH', 'date': '07/02/2012'
        },
        {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'
        },
        {'address': '1060 W ADDISON', 'date': '07/02/2012'
        }
    ], '07/03/2012': [
        {'address': '2122 N CLARK', 'date': '07/03/2012'
        }
    ]
})
>>>

过滤序列元素

你有一个数据序列，想利用一些规则从中提取出需要的值或者是缩短序列

最简单的过滤序列元素的方法就是使用列表推导

1
2
3
4
5
6
>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>> [n for n in mylist if n > 0]
[1, 4, 10, 2, 3]
>>> [n for n in mylist if n < 0]
[-5, -7, -1]
>>>

潜在缺陷就是如果输入非常大的时候会产生一个非常大的结果集，占用大量内存,可以用生成器表达式迭代产生过滤的元素。

1
2
3
4
5
6
7
8
9
10
11
12
>>> pos = (n for n in mylist if n > 0)
>>> pos
<generator object <genexpr> at 0x7f3a14e538e0>
>>> for i in pos:
...     print(i)
...
1
4
10
2
3
>>>

过滤规则比较复杂,将过滤代码放到一个函数中，然后使用内建的filter()函数

1
2
3
4
5
6
7
8
9
10
values = ['1', '2', '-3', '-', '4', 'N/A', '5']
def is_int(val):
    try:
        x = int(val)
        return True
    except ValueError:
        return False
# filter() 函数创建了一个迭代器
ivals = list(filter(is_int, values))
print(ivals)

在过滤的时候转换数据

1
2
3
4
5
>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>> import math
>>> [math.sqrt(n) for n in mylist if n > 0]
[1.0, 2.0, 3.1622776601683795, 1.4142135623730951, 1.7320508075688772]
>>>

过滤操作的一个变种就是将不符合条件的值用新的值代替，

1
2
3
4
5
>>> [n if n > 0 else 0 for n in mylist]
[1, 4, 0, 10, 0, 2, 3, 0]
>>> [n if n < 0 else 0 for n in mylist]
[0, 0, -5, 0, -7, 0, 0, -1]
>>>

itertools.compress(),它以一个 iterable 对象和一个相对应的 Boolean 选择器序列作为输入参数.然后输出 iterable 对象中对应选择器为 True 的元素当你需要用另外一个相关联的序列来过滤某个序列的时候，这个函数是非常有用的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
>>> addresses = [
... '5412 N CLARK',
... '5148 N CLARK',
... '5800 E 58TH',
... '2122 N CLARK'
... '5645 N RAVENSWOOD',
... '1060 W ADDISON',
... '4801 N BROADWAY',
... '1039 W GRANVILLE',
... ]
>>> counts = [ 0, 3, 10, 4, 1, 7, 6, 1]
>>> from itertools import compress
>>> more5 = [n > 5 for n in counts]
>>> more5
[False, False, True, False, False, True, True, False]
>>> list(compress(addresses, more5))
['5800 E 58TH', '4801 N BROADWAY', '1039 W GRANVILLE']
>>>

compress() 也是返回的一个迭代器

从字典中提取子集

你想构造一个字典，它是另外一个字典的子集

是使用字典推导

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> prices = {
... 'ACME': 45.23,
... 'AAPL': 612.78,
... 'IBM': 205.55,
... 'HPQ': 37.20,
... 'FB': 10.75
... }
>>> {key: value for key, value in prices.items() if value > 200}
{'AAPL': 612.78, 'IBM': 205.55}
>>> tech_names = {'AAPL', 'IBM', 'HPQ', 'MSFT'}
>>> {key: value for key, value in prices.items() if key in tech_names}
{'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.2}
>>>

字典推导能做到的，通过创建一个元组序列然后把它传给 dict()也能实现,字典推导方式表意更清晰，并且实际上也会运行的更快些

1
dict((key, value) for key, value in prices.items() if value > 200)

将名称映射到序列的元素中

你有一段通过下标访问列表或者元组中元素的代码，但是这样有时候会使得你的代码难以阅读，于是你想通过名称来访问元素。

collections.namedtuple() 函数通过使用一个普通的元组对象来帮你解决这个问题。

1
2
3
4
5
>>> from collections import namedtuple
>>> Subscriber = namedtuple('Subscriber', ['addr', 'joined'])
>>> sub = Subscriber('jonesy@example.com', '2012-10-19')
>>> sub
Subscriber(addr='jonesy@example.com', joined='2012-10-19')

namedtuple() 返回 Python 中标准元组类型子类的一个工厂方法,传递一个类型名和你需要的字段给它，然后它就会返回一个类,虽然看起来像一个类实例，但是是可交换的。

1
2
3
4
5
6
7
8
>>> sub.addr
'jonesy@example.com'
>>> sub[1]
'2012-10-19'
>>> addr, joined = sub
>>> addr
'jonesy@example.com'
>>>

命名元组的一个主要用途是将你的代码从下标操作中解脱出来,数据查询中返回很大一个元组，通过下标去操作其中的元素有很多可变性，如果使用元组命名则不用考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def compute_cost(records):
    total = 0.0
    for rec in records:
        total += rec[1] * rec[2]
    return total

from collections import namedtuple
Stock = namedtuple('Stock', ['name', 'shares', 'price'])
def compute_cost(records):
    total = 0.0
    for rec in records:
        s = Stock(*rec)
        total += s.shares * s.price
    return total

命名元组另一个用途就是作为字典的替代，字典存储需要更多的内存空间

需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效

是需要注意一个命名元组是不可更改的.如果你真的需要改变后的属性，那么可以使用命名元组实例的replace()方法

1
2
3
4
5
6
7
8
9
10
11
12
>>> sub
Subscriber(addr='jonesy@example.com', joined='2012-10-19')
>>> sub.addr
'jonesy@example.com'
>>> sub.addr = '1@qq.com'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute
>>> sub = sub._replace(addr='1@qq.com')
>>> sub
Subscriber(addr='1@qq.com', joined='2012-10-19')
>>>

它会创建一个全新的命名元组并将对应的字段用新的值取代

_replace() 方法还有一个很有用的特性就是当你的命名元组拥有可选或者缺失字段时候，它是一个非常方便的填充数据的方法。你可以先创建一个包含缺省值的原型元组，然后使用 _replace() 方法创建新的值被更新过的实例,类似于类实例的初始化调用构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
>>> from collections import namedtuple
>>> Stock = namedtuple('Stock', ['name', 'shares', 'price', 'date', 'time'])
>>> stock_prototype = Stock('', 0, 0.0, None, None)
>>> def dict_to_stock(s):
...     return stock_prototype._replace(**s)
...
>>> a = {'name': 'ACME', 'shares': 100, 'price': 123.45}
>>> dict_to_stock(a)
Stock(name='ACME', shares=100, price=123.45, date=None, time=None)
>>> b = {'name': 'ACME', 'shares': 100, 'price': 123.45, 'date': '12/17/2012'}
>>> dict_to_stock(b)
Stock(name='ACME', shares=100, price=123.45, date='12/17/2012', time=None)
>>>

如果你的目标是定义一个需要更新很多实例属性的高效数据结构，那么命名元组并不是你的最佳选择。这时候你应该考虑定义一个包含 slots 方法的类

同时对数据做转换和换算

我们需要调用一个换算(reduction)函数(例如sumO、min)、max))，但首先得对数据做转换或筛选。

1
2
3
4
>>> num = [1,2,3,4,5]
>>> sum(x * x for x in num)
55
>>>

将多个映射合并为单个映射

我们有多个字典或映射，想在逻辑上将它们合并为一个单独的映射结构，以此执行某些特定的操作，比如查找值或检查键是否存在。

一种简单的万法是利用collections模块中的ChainMap类来解决

1
2
3
4
5
6
7
>>> a={'x':1,'z':3}
>>> b={'y':2,'z':4}
>>> from collections import ChainMap
>>> ChainMap(a,b)
ChainMap({'x': 1, 'z': 3}, {'y': 2, 'z': 4})
>>>

ChainMap可接受多个映射然后在逻辑上使它们表现为一个单独的映射结构。但是，这些映射在字面上并不会合并在一起。相反，ChainMap只是简单地维护一个记录底层映射关系的列表，然后重定义常见的字典操作来扫描这个列表。大部分的操作都能正常工作。

1
2
3
4
5
6
7
>>> len(ChainMap(a,b))
3
>>> list(ChainMap(a,b).keys())
['y', 'z', 'x']
>>> list(ChainMap(a,b).values())
[2, 3, 1]
>>>

如果有重复的键，那么这里会采用第一个映射中所对应的值。修改映射的操作总是会作用在列出的第一个映射结构上。

ChainMap与带有作用域的值，比如编程语言中的变量(即全局变量、局部变量等)一起工作时特别有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>>> v = ChainMap()
>>> v['x'] = 1
>>> v = v.new_child()
>>> v['x'] = 2
>>> v = v.new_child()
>>> v['x'] = 3
>>> v
ChainMap({'x': 3}, {'x': 2}, {'x': 1})
>>> v['x']
3
>>> v = v.parents
>>> v['x']...............
2
>>> v = v.parents
>>> v['x']
1
>>> v
ChainMap({'x': 1})
>>>

作为ChainMap的替代方案，我们可能会考虑利用字典的update()方法将多个字典合并在一起。但是破坏了原始的数据结构，而ChainMap使用的就是原始的字典，因此它不会产生这种令人不悦的行为。

1
2
3
4
5
6
7
8
9
>>> a
{'x': 1, 'z': 3}
>>> b
{'y': 2, 'z': 4}
>>>
>>> c= dict(b)
>>> c.update(a)
>>> c
{'y': 2, 'z': 3, 'x': 1}

Python实战之数据结构和算法

https://liruilongs.github.io/2022/04/30/Python/Python实战之数据结构和算法/

发布于

2022-04-30

更新于

2023-06-21

许可协议

# 相关文章
  1.【python小脚本】摄像头rtsp流转hls m3u8 格式web端播放
  2.【python小脚本】监听日志文件异常数据发送告警短信
  3.Python实战之函数的一些奇技淫巧
  4.Python实战之用内置模块来构建REST服务、RPC服务
  5.Python中迭代器&生成器的"奇技淫巧"
  6.Python实战之数字、日期和时间的高级处理
  7.Python实战之字符串和文本处理
  8.Python实战之Linux下脚本编写的"奇技淫巧"
# 推荐文章
  1.《Kubernetes权威指南:从Docker到Kubernetes实践全接触》读书笔记
  2.Git 提交代码 reference broken 问题处理
  3.关于 Git 重写历史的一些笔记
  4.关于Git分支变基操作的一些笔记
  5.关于Git分支基础知识的一些笔记
  6.关于Git分支工作流的一些笔记

喜欢这篇文章？打赏一下作者吧

评论
关注我

链接

最新评论

加载中，最新评论有1分钟缓存...

最新文章

分类

归档

标签

Kubernetes98
Linux65
Ansible25
Ceph22
Python15
Docker9
Git8
JAVA8
华为云8
BPF7
CPU7
Mysql7
test17
Go6
LLM6
OpenShift6
摄影曝光6
程序人生6
DNS5
OKD5
查看全部>>

订阅更新

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×