Python3 CookBook学习笔记 -- 数据结构与算法

2018-02-17 本文已影响20人 faris_shi

1. 迭代对象解压赋值

解压赋值操作可以应用到任何迭代对象上，如：列表、元组、字符串、文件对象、迭代器、生成器。

唯一的要求：

变量的数量必须跟序列元素的数量是一样的。

>>> p=(1,2,3,4)
>>> a,b,c,d=p
>>> a
1
>>> b
2
>>> c
3
>>> d
4

>>> datas=['apple', 'cherry', 1, (1,2,3,4)]
>>> a,b,c,d=datas
>>> a
'apple'
>>> b
'cherry'
>>> c
1
>>> d
(1, 2, 3, 4)

>>> s='faris'
>>> a,b,c,d,e=s
>>> a
'f'
>>> b
'a'
>>> c
'r'
>>> d
'i'
>>> e
's'

2. 扩展迭代对象解压赋值

如果遇到不确定个数或任意个数元素的可迭代对象时，则需要使用星号表达式可以用来解决这个问题。

假设你现在有一些用户的记录列表，每条记录包含一个名字、邮件，接着就是不确定数量的电话号码。

>>> record = ('Dave', 'dave@example.com', '773-555-1212', '847-555-1212')
>>> name, email, *phone_numbers = record
>>> name
'Dave'
>>> email
'dave@example.com'
>>> phone_numbers
['773-555-1212', '847-555-1212']
>>>

如果你想解压一些元素后丢弃它们，你不能简单就使用 * ，但是你可以使用一个普通的废弃名称，比如 _ 或者 ign （ignore）。

>>> record = ('ACME', 50, 123.45, (12, 18, 2012))
>>> name, *_, (*_, year) = record
>>> 
>>> 
>>> 
>>> name
'ACME'
>>> _
[12, 18]
>>> 
>>> 
>>> year
2012

3. 查找最大或最小的 N 个元素

heapq 模块有两个函数：nlargest() 和 nsmallest() 可以完美解决这个问题。

输出最大和最小的三个值：

>>> import heapq
>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> print(heapq.nlargest(3, nums)) 
[42, 37, 23]
>>> print(heapq.nsmallest(3, nums))
[-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}
... ]
>>> cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
>>> expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
>>> 
>>> cheap
[{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}]
>>> 
>>> expensive
[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'IBM', 'shares': 100, 'price': 91.1}]

注意点

当要查找的元素个数相对比较小的时候，函数 nlargest() 和 nsmallest() 是很合适的。
如果你仅仅想查找唯一的最小或最大（N=1）的元素的话，那么使用 min() 和 max() 函数会更快些。
如果 N 的大小和集合大小接近的时候，通常先排序这个集合然后再使用切片操作会更快点（ sorted(items)[:N] 或者是 sorted(items)[-N:] ）。

4. 实现一个优先级队列

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):
     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()
q.pop()
q.pop()
q.pop()

在上面代码中，队列包含了一个 (-priority, index, item) 的元组。优先级为负数的目的是使得元素按照优先级从高到低排序。这个跟普通的按优先级从低到高排序的堆排序恰巧相反。

对于Item对象是不支持相互比较的：

>>> a=Item('foo')
>>> b=Item('boo')
>>> a > b
Traceback (most recent call last):
  File "test.py", line 26, in <module>
    a > b
TypeError: '>' not supported between instances of 'Item' and 'Item'

但是使用元组，则可以进行比较：

>>> class Item:
...     def __init__(self, name):
...             self.name = name
...     def __repr__(self):
...      return 'Item({!r})'.format(self.name)
... 
>>> 
>>> a=(1, Item('foo'))
>>> b=(2, Item('boo'))
>>> print (a > b)
False

5. 字典中的键映射多个值 `multidict`

一个字典就是一个键对应一个单值的映射。如果你想要一个键映射多个值，那么你就需要将这多个值放到另外的容器中，比如列表或者集合里面。

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

使用 collections 模块中的 defaultdict 来构造一键多值的字典：

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

defaultdict 会自动为将要访问的键（就算目前字典中并不存在这样的键）创建映射实体。

>>> d = defaultdict(set)
>>> 
>>> 
>>> d['d']
set()
>>> d
defaultdict(<class 'set'>, {'d': set()})

可以通过一个普通的字典上使用 setdefault() 去除这个情况：

>>> d = {}
>>> d.setdefault('a', []).append(1)
>>> d.setdefault('a', []).append(2)
>>> d.setdefault('b', []).append(4)
>>> 
>>> d
{'a': [1, 2], 'b': [4]}
>>> d['c']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'c'
>>> 
>>> d['a']
[1, 2]

这种写法是让人非常别扭的，因为需要多些一次[]。

也可以自己实现：

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

但是从Python提倡的简洁上来说，没有defaultdict简洁：

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

6. 字典按顺序输出

为了能控制一个字典中元素的顺序，你可以使用 collections 模块中的 OrderedDict 类

>>> from collections import OrderedDict
>>> 
>>> d = OrderedDict()
>>> d['foo'] = 1
>>> d['bar'] = 2
>>> d['spam'] = 3
>>> d['grok'] = 4
>>> 
>>> d
OrderedDict([('foo', 1), ('bar', 2), ('spam', 3), ('grok', 4)])
>>> 
>>> for key in d:
...     print(key, d[key])
... 
foo 1
bar 2
spam 3
grok 4

OrderedDict 内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候，它会被放到链表的尾部。

一个 OrderedDict 的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。大量数据时，需要权衡效率。

7. 字典运算

如何在数据字典中执行求最小值、最大值、排序？

上面我们学习的方法为：

使用heapq 中的 nlargest、nsmallest、heapify完成堆排序。
使用 sorted函数。
使用 min函数和 max函数

参考股票名和价格映射字典：

prices = {
    'ACME': 45.23,
    'AAPL': 612.78,
    'IBM': 205.55,
    'HPQ': 37.20,
    'FB': 10.75
}

7.1 heapq

显然无法实现字典排序，无论是根据key排序，还是根据value排序。

>>> heapq.nlargest(1, prices)
['IBM']
>>> heapq.nsmallest(1, prices)
['AAPL']
>>> heapq.heapify(prices)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: heap argument must be a list

7.2 sorted

显然 sorted无法实现对value的排序，只能对key进行排序并返回排好序的key列表，且还需要再次遍历这个列表才能获取value。

>>> sorted(prices)
['AAPL', 'ACME', 'FB', 'HPQ', 'IBM']

7.2 min max

显然和sorted是相同的问题，只能对key进行排序。

>>> min(prices)
'AAPL'
>>> 
>>> 
>>> max(prices)
'IBM'

方案1 zip：

我们为了对值进行操作时，需要使用zip() 函数对key与value进行翻转。

>>> list(zip(prices.values(), prices.keys()))
[(45.23, 'ACME'), (612.78, 'AAPL'), (205.55, 'IBM'), (37.2, 'HPQ'), (10.75, 'FB')]
>>> 
>>> 
>>> min(zip(prices.values(), prices.keys()))
(10.75, 'FB')
>>> 
>>> 
>>> max(zip(prices.values(), prices.keys()))
(612.78, 'AAPL')
>>> 
>>> 
>>> sorted(zip(prices.values(), prices.keys()))
[(10.75, 'FB'), (37.2, 'HPQ'), (45.23, 'ACME'), (205.55, 'IBM'), (612.78, 'AAPL')]

需要注意的是 zip() 函数创建的是一个只能访问一次的迭代器。

>>> prices_and_names = zip(prices.values(), prices.keys())
>>> print(min(prices_and_names)) # OK
(10.75, 'FB')
>>> print(max(prices_and_names))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: max() arg is an empty sequence

方案2 min + values max + values

直接输出最大或者最小`values`

>>> min(prices.values()) # Returns 10.75
10.75
>>> max(prices.values()) # Returns 612.78
612.78

输出最大或者最小的`value`对应的`key`

>>> min(prices, key=lambda k: prices[k]) 
'FB'
>>> max(prices, key=lambda k: prices[k]) 
'AAPL'

8. 查找两字典的相同点

怎样在两个字典中寻寻找相同点（比如相同的键、相同的值等等）？

a = {
    'x' : 1,
    'y' : 2,
    'z' : 3
}

b = {
    'w' : 10,
    'x' : 11,
    'y' : 2
}

最直接的想法便是遍历a，然后检查b。

python其实更加简单方便

相同的key

>>> a.keys() & b.keys()
{'y', 'x'}

a中有，b中没有的key

>>> a.keys() - b.keys()
{'z'}

相同的元素

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

两个字典的合集

>>> a.items() | b.items()
{('x', 11), ('z', 3), ('y', 2), ('w', 10), ('x', 1)}

我们可以使用以上的操作，来完成修改或者过滤字典元素。

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

一个字典就是一个键集合与值集合的映射关系。字典的 keys() 方法返回一个展现键集合的键视图对象。键视图的一个很少被了解的特性就是它们也支持集合操作，比如集合并、交、差运算。所以，如果你想对集合的键执行一些普通的集合操作，可以直接使用键视图对象而不用先将它们转换成一个 set。

>>> type(a.keys())
<class 'dict_keys'>
>>> 
>>> 
>>> type(a.keys() & b.keys())
<class 'set'>

字典的 items() 方法返回一个包含 (键，值) 对的元素视图对象。这个对象同样也支持集合操作，并且可以被用来查找两个字典有哪些相同的键值对。

>>> type(a.items())
<class 'dict_items'>
>>> 
>>> 
>>> type(a.items() & b.items())
<class 'set'>

尽管字典的 values() 方法也是类似，但是它并不支持这里介绍的集合操作。某种程度上是因为值视图不能保证所有的值互不相同，这样会导致某些集合操作会出现问题。不过，如果你硬要在值上面执行这些集合操作的话，你可以先将值集合转换成 set，然后再执行集合运算就行了。

>>> 
>>> type(a.values())
<class 'dict_values'>
>>> 
>>> 
>>> a.values() & b.values()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for &: 'dict_values' and 'dict_values'
>>> 
>>> 
>>> set(a.values()) & set(b.values())
{2}

9. 删除序列相同元素并保持顺序

怎样在一个序列上面保持元素顺序的同时消除重复的值？

如果序列上的值都是 hashable类型，那么可以很简单的利用集合或者生成器来解决这个问题。

什么是 hashable类型？

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). Hashable objects which compare equal must have the same hash value. Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

如果一个对象在其生命周期内有一个固定不变的哈希值 (这需要__hash__() 方法) ，且可以与其他对象进行比较操作 (这需要__eq__() 方法) ，那么这个对象就是可哈希对象 ( hashable ) 。可哈希对象必须有相同的哈希值才算作相等。由于字典 ( dict ) 的键 ( key ) 和集合 ( set ) 内部使用到了哈希值，所以只有可哈希 ( hashable ) 对象才能被用作字典的键和集合的元素。所有 python 内置的不可变对象都是可哈希的，同时，可变容器 (比如：列表 ( list ) 或者字典 ( dict ) ) 都是不可哈希的。用户自定义的类的实例默认情况下都是可哈希的；它们跟其它对象都不相等 (除了它们自己) ，它们的哈希值来自 id() 方法。

>>> 
>>> def dedupe(items):
...     seen = set()
...     for item in items:
...         if item not in seen:
...             yield item
...             seen.add(item)
...     return items
... 
>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> 
>>> list(dedupe(a))
[1, 5, 2, 9, 10]

这个方法仅仅在序列中元素为 hashable 的时候才管用。如果你想消除元素不可哈希（比如 dict 类型）的序列中重复元素的话，你需要将上述代码稍微改变一下，就像这样：

>>> 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)
...     return items
... 
>>> 
>>> 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}]

如果你仅仅就是想消除重复元素而不用维持顺序的话，通常可以简单的构造一个集合

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

如果我们想读取文件并排除掉重复行，也可以使用上面的方法

with open(somefile,'r') as f:
for line in dedupe(f):
    ...

10. 命名切片

假定你有一段代码要从一个记录字符串中几个固定位置提取出特定的数据字段（比如文件或类似格式）：

>>> record = '....................100 .......513.25 ..........'
>>> cost = int(record[20:23]) * float(record[31:37])
>>> cost
51325.0

我们需要命名切片 slice

slice 有三个属性，start, stop, step。在创建构造函数时，可以适时忽略。

创建切片

>>> a=slice(10)   #stop为10, step默认为1的分片
>>> a
slice(None, 10, None)

>>> a=slice(0, 10) # start为1， stop为10, step默认为1的分片
>>> a
slice(0, 10, None)

>>> a=slice(0, 10, 2) # start为1， stop为10, step为2的分片
>>> a
slice(0, 10, 2)

示例：

>>> SHARES = slice(20, 23)
>>> PRICE = slice(31, 37)
>>> cost = int(record[SHARES]) * float(record[PRICE])
>>> cost
51325.0

这样你避免了大量无法理解的硬编码下标，使得你的代码更加清晰可读了。

内置的 slice() 函数创建了一个切片对象，可以被用在任何切片允许使用的地方。

>>> items = [0, 1, 2, 3, 4, 5, 6]
>>> a = slice(2, 4)
>>> items[a]
[2, 3]
>>> items[a] = [10,11]
>>> items[a]
[10, 11]
>>> items
[0, 1, 10, 11, 4, 5, 6]

如果你有一个切片对象 a，你可以分别调用它的 a.start , a.stop , a.step 属性来获取更多的信息。比如：

>>> a = slice(5, 50, 2)
>>> a.start
5
>>> a.stop
50
>>> a.step
2
>>>

我们也可以调用切片的 indices(size) 方法将它映射到一个确定大小的序列上，这个方法返回一个三元组 ( start, stop, step ) ，所有值都会被合适的缩小以满足边界限制，从而使用的时候避免出现 IndexError 异常

>>> items = [0, 1, 2, 3, 4, 5, 6]
>>> a=slice(0,0)
>>> type(a)
<class 'slice'>
>>> b=a.indices(len(items))
>>> b
(0, 0, 1)
>>> type(b)
<class 'tuple'>

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

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

我们可能需要collections.Counter ， Counter 对象可以接受任意的由可哈希（hashable）元素构成的序列对象。在底层实现上，一个 Counter 对象就是一个字典，将元素映射到它出现的次数上。

from collections import Counter

>>> 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'
... ]
>>> word_counts = Counter(words)
>>> 
>>> 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})
>>> 
>>> type(word_counts)
<class 'collections.Counter'>
>>> 
>>> 
>>> dir(word_counts)
['__add__', '__and__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__iand__', '__init__', '__init_subclass__', '__ior__', '__isub__', '__iter__', '__le__', '__len__', '__lt__', '__missing__', '__module__', '__ne__', '__neg__', '__new__', '__or__', '__pos__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__weakref__', '_keep_positive', 'clear', 'copy', 'elements', 'fromkeys', 'get', 'items', 'keys', 'most_common', 'pop', 'popitem', 'setdefault', 'subtract', 'update', 'values']
>>> 
>>> word_counts['not']
1
>>> word_counts['eyes']
8
>>>

我们也可以手动添加：

>>> morewords = ['why','are','you','not','looking','in','my','eyes']
>>> for word in morewords:
...     word_counts[word] += 1
... 
>>> word_counts['eyes']
>>> 9

只不过 Counter的内部提供了 update的方法：

>>> word_counts.update(morewords)
>>> word_counts['eyes']
>>> 10

由于Counter实现了 hashable，因此可以用于运算操作。

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

因此，Counter这个特性会在很多场合使用，比如合并统计数据，制表等等场合。

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

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

使用 operator 模块的 itemgetter 函数。

>>> from operator import itemgetter
>>>  
>>> 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}
... ]
>>> 
>>> 
>>> rows_by_fname = sorted(rows, key=itemgetter('fname'))
>>> rows_by_uid = sorted(rows, key=itemgetter('uid'))
>>> rows_by_all = sorted(rows, key=itemgetter('fname', 'uid'))
>>> 
>>> rows_by_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_by_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}]
>>> 
>>> rows_by_all
[{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}]

同样，itemgetter() 有时候也可以用 lambda 表达式代替，但是没有itemgetter() 效率高。比如：

>>> rows_by_fname = sorted(rows, key=lambda r: r['fname'])
>>> rows_by_lfname = sorted(rows, key=lambda r: (r['lname'],r['fname']))
>>> 
>>> 
>>> 
>>> rows_by_lfname
[{'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}, {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}]
>>> rows_by_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}]

最后，不要忘了这节中展示的技术也同样适用于 min() 和 max() 等函数

>>> min(rows, key=itemgetter('uid'))
{'fname': 'John', 'lname': 'Cleese', 'uid': 1001}
>>> max(rows, key=itemgetter('uid'))
{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
>>>

同样需要注意的是，由于 dict 不是 hashable。所以不能使用 min 、max、sorted。但是tuple、set是hasable，所以我们可以通过 lambda 和 itemgetter来完成对两者的排序。

>>> 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}
... ]
>>> 
>>> min(rows)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'
>>> 
>>> max(rows)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '>' not supported between instances of 'dict' and 'dict'
>>> 
>>> sorted(rows)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'
>>> 
>>> min(rows, key=lambda r:(r['fname']))
{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
>>> 
>>> max(rows, key=lambda r:(r['fname']))
{'fname': 'John', 'lname': 'Cleese', 'uid': 1001}
>>> 
>>> 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}]
>>>

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

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

上一节我们知道sorted、min、max、heapq.nsmallest、heapq.nlargest函数有一个关键字参数 key，可以传入一个callable 对象给它。

这个 callable 对象对每个传入的对象返回一个值，这个值会被用来排序这些对象。而这个callable对象可以是我们使用lambda自定义对象，或者使用from operator import attrgetter或者from operator import itemgetter。

本章第3节、第4节、第7节、第12节都在讲如何排序。

13.1 `hashable` 排序

当装有hashable类型的list、tuple、set 我们可以使用任意的排序方式进行排序。

list排序

>>> letters=['a', 'b', 'c', 'd', 'z', 'g']
>>> sorted(letters)
['a', 'b', 'c', 'd', 'g', 'z']
>>> 
>>> min(letters)
'a'
>>> max(letters)
'z'
>>> 
>>> import heapq
>>> 
>>> heapq.nsmallest(1, letters)
['a']
>>> heapq.nlargest(1, letters)
['z']
>>> sorted(letters)[0]
'a'
>>> sorted(letters)[len(letters) -1]
'z'

tuple排序

>>> letters=('a', 'b', 'c', 'd', 'z', 'g')
>>> sorted(letters)
['a', 'b', 'c', 'd', 'g', 'z']
>>> type(sorted(letters))
<class 'list'>
>>> min(letters)
'a'
>>> max(letters)
'z'
>>> import heapq
>>> 
>>> heapq.nsmallest(1, letters)
['a']
>>> heapq.nlargest(1, letters)
['z']
>>> sorted(letters)[0]
'a'
>>> sorted(letters)[len(letters) -1]
'z'

set排序

>>> letters=('a', 'b', 'c', 'd', 'z', 'g')
>>> letters=set(letters)
>>> sorted(letters)
['a', 'b', 'c', 'd', 'g', 'z']
>>> type(sorted(letters))
<class 'list'>
>>> min(letters)
'a'
>>> max(letters)
'z'
>>> import heapq
>>> 
>>> heapq.nsmallest(1,  letters)
['a']
>>> heapq.nlargest(1,  letters)
['z']
>>> sorted(letters)[0]
'a'
>>> sorted(letters)[len(letters) -1]
'z'

13.2 非hashable 排序

我们知道dict 、自定义对象是非hashable的。

装有dict元素的列表

>>> import heapq
>>> 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}
... ]
>>> heapq.nsmallest(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}]
>>> 
>>> heapq.nlargest(3, portfolio, key=lambda s: s['price'])
[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'IBM', 'shares': 100, 'price': 91.1}]
>>> 
>>> sorted(portfolio, key=lambda n: (n['name']))
[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}, {'name': 'IBM', 'shares': 100, 'price': 91.1}, {'name': 'YHOO', 'shares': 45, 'price': 16.35}]
>>>
>>> sorted(portfolio, key=lambda n: (n['shares'], n['price']))
[{'name': 'HPQ', 'shares': 35, 'price': 31.75}, {'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'IBM', 'shares': 100, 'price': 91.1}, {'name': 'FB', 'shares': 200, 'price': 21.09}]
>>> 
>>> min(portfolio, key=lambda n: (n['name']))
{'name': 'AAPL', 'shares': 50, 'price': 543.22}
>>> 
>>> max(portfolio, key=lambda n: (n['name']))
{'name': 'YHOO', 'shares': 45, 'price': 16.35}
>>>
 >>> from operator import itemgetter
>>>
>>> min(portfolio, key=itemgetter('name'))
{'name': 'AAPL', 'shares': 50, 'price': 543.22}
>>> 
>>> max(portfolio, key=itemgetter('name'))
{'name': 'YHOO', 'shares': 45, 'price': 16.35}
>>>  
>>> sorted(portfolio, key=itemgetter('name'))
[{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}, {'name': 'IBM', 'shares': 100, 'price': 91.1}, {'name': 'YHOO', 'shares': 45, 'price': 16.35}]

dict

>>> prices = {
...     'ACME': 45.23,
...     'AAPL': 612.78,
...     'IBM': 205.55,
...     'HPQ': 37.20,
...     'FB': 10.75
... }
>>> sorted(prices)
['AAPL', 'ACME', 'FB', 'HPQ', 'IBM']
>>> 
>>> min(prices)
'AAPL'
>>> 
>>> max(prices)
'IBM'
>>> sorted(prices, key=lambda n : prices[n])
['FB', 'HPQ', 'ACME', 'IBM', 'AAPL']
>>> 
>>> min(prices, key=lambda n : prices[n])
'FB'
>>> max(prices, key=lambda n : prices[n])
'AAPL'
>>> heapq.nsmallest(1, prices)
['AAPL']
>>> 
>>> heapq.nlargest(1, prices)
['IBM']
>>> 
>>> min(zip(prices.values(), prices.keys()))
(10.75, 'FB')
>>> 
>>> max(zip(prices.values(), prices.keys()))
(612.78, 'AAPL')
>>> sorted(zip(prices.values(), prices.keys()))
[(10.75, 'FB'), (37.2, 'HPQ'), (45.23, 'ACME'), (205.55, 'IBM'), (612.78, 'AAPL')]
>>> 
>>> min(prices.values())
10.75
>>> 
>>> max(prices.values())
612.78
>>> sorted(prices.values())
[10.75, 37.2, 45.23, 205.55, 612.78]

自定义对象

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

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

>>> users = [User(23), User(3), User(99)]
>>>
>>> sorted(users, key=lambda n: (n.user_id))
[User(3), User(23), User(99)]
>>> min(users, key=lambda n: (n.user_id))
User(3)
>>> max(users, key=lambda n: (n.user_id))
User(99)
>>>
>>> from operator import attrgetter
>>>
>>> sorted(users, key=attrgetter('user_id'))
[User(3), User(23), User(99)]
>>> min(users, key=attrgetter('user_id'))
User(3)
>>> max(users, key=attrgetter('user_id'))
User(99)

14. 通过某个字段将记录分组

我们可以使用 itertools.groupby() 对字典或者序列进行分组。

groupby() 仅仅检查连续的元素，如果事先并没有排序完成的话，分组函数将得不到想要的结果。

>>> 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'},
... ]
>>> 
>>> # Sort by the desired field first
... rows.sort(key=itemgetter('date'))
>>> # Iterate in groups
... 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'}

如果不想进行排序，仅仅是想根据date对数据进行分组，且随机访问，那么欢迎使用defaultdict()

>>> from collections import defaultdict
>>> rows_by_date = defaultdict(list)
>>> for row in rows:
...     rows_by_date[row['date']].append(row)
>>>
>>> rows_by_date['07/04/2012']
[{'address': '5148 N CLARK', 'date': '07/04/2012'}, {'address': '1039 W GRANVILLE', 'date': '07/04/2012'}]

15. 过滤序列元素

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

使用列表推导

>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
 >>> [n for n in mylist if n > 0]
[1, 4, 10, 2, 3]
>>>  t=[n for n in mylist if n < 0]
>>> 
>>> t
[-5, -7, -1]
>>> 
>>> type(t)
<class 'list'>

列表推导的一个潜在缺陷就是如果要过滤的列表过大产生一个非常大的结果集，占用大量内存。所以建议使用生成器表达式迭代

生成器表达式迭代

>>> pos = (n for n in mylist if n > 0)
>>> 
>>> type(pos)
<class 'generator'>
>>> for x in pos:
...     print(x)
... 
1
4
10
2
3

如果过滤条件过于复杂，那么可以把过滤条件放到一个函数中，并使用filter()

>>> values = ['1', '2', '-3', '-', '4', 'N/A', '5']
>>> def is_int(val):
...     try:
...             x = int(val)
...             return True
...     except ValueError:
...             return False
... 
>>> n=filter(is_int, values)
>>> type(n)
<class 'filter'>
>>> ivals = list(n)
>>> 
>>> ivals
['1', '2', '-3', '4', '5']

filter类是一个迭代器，因此如果我们需要变成一个列表时可以使用list()。如果我们需要遍历时，请直接使用：

>>> n=filter(is_int, values)
>>> for x in n:
...     print(x)

过滤的同时修改数据

生成器表达式迭代和列表推导能够干很多很多有意思的事情，比如在过滤的同时完成对数据的进一步改造：

将mylist的中的数字全部平方，然后过滤丢弃。

>>> 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]

将小于0的数用0代替，而不是丢弃掉。

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

itertools.compress()

itertools.compress()以一个 iterable 对象和一个相对应的 Boolean 选择器序列作为输入参数。然后输出 iterable 对象中对应选择器为 True 的元素。

>>> 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]  #`Boolean` 选择器序列
>>> more5
[False, False, True, False, False, True, True, False]
>>> 
>>> compress=compress(addresses, more5)
>>> compress
<itertools.compress object at 0x1022b49b0>
>>> 
>>> list(compress)
['5800 E 58TH', '1060 W ADDISON', '4801 N BROADWAY']
>>>

需要我们先创建Boolean 选择器序列，然后才能使用。

16. 从字典中提取子集

字典推导

字典推导能够完成绝大多数的需求，并且速度更快。

>>> prices = {
...     'ACME': 45.23,
...     'AAPL': 612.78,
...     'IBM': 205.55,
...     'HPQ': 37.20,
...     'FB': 10.75
... }
... p1 = {key: value for key, value in prices.items() if value > 200}
... tech_names = {'AAPL', 'IBM', 'HPQ', 'MSFT'}
>>> p2 = {key: value for key, value in prices.items() if key in tech_names}
>>> p1
{'AAPL': 612.78, 'IBM': 205.55}
>>> 
>>> p2
{'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.2}

dict() + 元组

>>> p1 = dict((key, value) for key, value in prices.items() if value > 200)
>>> 
>>> p1
{'AAPL': 612.78, 'IBM': 205.55}

17. 映射名称到序列元素

当我们从数据库中读出一行数据时，返回的是一个元组，我们需要通过下标来查找我们想要的字段，这样的代码是不可读的。

collections.namedtuple()

collections.namedtuple()，可以称为命名元组，可以通过一个存放对应key的元组，来解决映射的问题。

>>> 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')
>>> 
>>> sub.addr
'jonesy@example.com'
>>> 
>>> sub.joined
'2012-10-19'
>>> type(sub)
<class '__main__.Subscriber'>

namedtuple 看起来想一个简单对象，但是它却支持所有的普通元组操作。

>>> list(sub)
['jonesy@example.com', '2012-10-19']
>>> 
>>> len(sub)
2
>>> sub[1]
'2012-10-19'
>>> 
>>> addr, joined = sub
>>> addr
'jonesy@example.com'
>>> joined
'2012-10-19'

命名元组不可修改

>>> sub.addr='11@qq.com'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute

如果非要进行修改，那么请使用 _replace() 方法，但是它会创建一个全新的命名元组。

>>> newSub=sub._replace(addr='11@qq.com')
>>> newSub
Subscriber(addr='11@qq.com', joined='2012-10-19')

另外需要注意的是，命名元组的另一个用途就是替代只读字典的，因为字典存储需要更多的内存空间。如果你需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效。

_replace()

_replace() 可以完成根据你的原始序列，来填充命名元组。

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

18. 转换并同时计算数据

你需要在数据序列上执行聚集函数（比如 sum() , min() , max() ）之前，需要转换或者过滤数据。

优雅的办法就是 生成器表达式，也是我们必须第一个想到的。

>>> nums = [1, 2, 3, 4, 5]
>>> s = sum(x * x for x in nums)
>>> s
55
>>> s=sum(x for x in nums if x > 3)
>>> s
9

>>> import os
>>> files = os.listdir('/Users/faris/Desktop')
>>> if any(name.endswith('.py') for name in files):
...     print('There be python!')
... else:
...     print('Sorry, no python.')
There be python!

19. 合并多个字典或映射

如果我们有两个字典a、b。我们需要查找一个值，如果a中没有，然后再去b中找。

collections. ChainMap 会将多个字典逻辑顺序合并。

>>> a = {'x': 1, 'z': 3 }
>>> b = {'y': 2, 'z': 4 }
>>> 
>>> from collections import ChainMap
>>> c = ChainMap(a,b)
>>> print(c['x'])  
1
>>> print(c['y']) 
2
>>> print(c['z'])   打印的是a中的值，而不是b中的值
3

如果出现重复键，那么第一次出现的映射值会被返回。因此，例子程序中的 c['z'] 总是会返回字典 a 中对应的值，而不是 b 中对应的值。

>>> len(c)
3
>>> c.keys()
KeysView(ChainMap({'x': 1, 'z': 3}, {'y': 2, 'z': 4}))
>>> 
>>> c.values()
ValuesView(ChainMap({'x': 1, 'z': 3}, {'y': 2, 'z': 4}))
>>>  
>>> list(c.keys())
['z', 'x', 'y']
>>> 
>>> list(c.values())
[3, 1, 2]

对于字典的更新或删除操作总是影响的是列表中第一个字典。

>>> c['z'] = 10
>>> c['w'] = 40
>>> del c['x']
>>> a
{'w': 40, 'z': 10}
>>> del c['y']
Traceback (most recent call last):
...
KeyError: "Key not found in the first mapping: 'y'"
>>>

如果你想物理合并，那么请使用dict.update()，但是它会重新创建一个新的字典，并且对新字典的更新不会反应在旧字典，对旧字典的更新也不会反应在新字典上。

>>> a = {'x': 1, 'z': 3 }
>>> b = {'y': 2, 'z': 4 } 
>>> 
>>> merged = dict(b)
>>> 
>>> merged
{'y': 2, 'z': 4}
>>> merged.update(a)
>>> 
>>> merged
{'y': 2, 'z': 3, 'x': 1}
>>> 
>>> a
{'x': 1, 'z': 3}
>>> 
>>> b
{'y': 2, 'z': 4}

Python3 CookBook学习笔记 -- 数据结构与算法

1. 迭代对象解压赋值

2. 扩展迭代对象解压赋值

3. 查找最大或最小的 N 个元素

4. 实现一个优先级队列

5. 字典中的键映射多个值 `multidict`

6. 字典按顺序输出

7. 字典运算

7.1 heapq

7.2 sorted

7.2 min max

方案1 zip：

方案2 min + values max + values

直接输出最大或者最小`values`

输出最大或者最小的`value`对应的`key`

8. 查找两字典的相同点

9. 删除序列相同元素并保持顺序

10. 命名切片

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

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

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

13.1 `hashable` 排序

13.2 非hashable 排序

14. 通过某个字段将记录分组

15. 过滤序列元素

16. 从字典中提取子集

17. 映射名称到序列元素

18. 转换并同时计算数据

19. 合并多个字典或映射

猜你喜欢

热点阅读

Python3 CookBook学习笔记 -- 数据结构与算法

1. 迭代对象解压赋值

2. 扩展迭代对象解压赋值

3. 查找最大或最小的 N 个元素

4. 实现一个优先级队列

5. 字典中的键映射多个值 multidict

6. 字典按顺序输出

7. 字典运算

7.1 heapq

7.2 sorted

7.2 min max

方案1 zip：

方案2 min + values max + values

直接输出最大或者最小values

输出最大或者最小的value对应的key

8. 查找两字典的相同点

9. 删除序列相同元素并保持顺序

10. 命名切片

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

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

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

13.1 hashable 排序

13.2 非hashable 排序

14. 通过某个字段将记录分组

15. 过滤序列元素

16. 从字典中提取子集

17. 映射名称到序列元素

18. 转换并同时计算数据

19. 合并多个字典或映射

猜你喜欢

热点阅读

5. 字典中的键映射多个值 `multidict`

直接输出最大或者最小`values`

输出最大或者最小的`value`对应的`key`

13.1 `hashable` 排序