Python-数据结构和算法之20问答

数据结构和算法

python 提供了大量的内置数据结构，包括列表，集合以及字典。大多数情况下使用这些数据结构是很简单的。 但是，我们也会经常碰到到诸如查询，排序和过滤等等这些普遍存在的问题。 因此，这一章的目的就是讨论这些比较常见的问题和算法。 另外，我们也会给出在集合模块 collections 当中操作这些数据结构的方法。

1.1 解压序列赋值给多个变量

问题

现在有一个包含 n 个元素的元组或者是序列，怎样将它里面的值解压后同时赋值给 n 个变量？

解决方案

任何的序列（或者是可迭代对象）可以通过一个简单的赋值语句解压并赋值给多个变量。 唯一的前提就是变量的数量必须跟序列元素的数量是一样的。

代码示例：

>>> p = (4, 5)
>>> x, y = p
>>> x
4
>>> y
5
>>>
>>> data = [ 'acme', 50, 91.1, (2012, 12, 21) ]
>>> name, shares, price, date = data
>>> name
'acme'
>>> date
(2012, 12, 21)
>>> name, shares, price, (year, mon, day) = data
>>> name
'acme'
>>> year
2012
>>> mon
12
>>> day
21
>>>

如果变量个数和序列元素的个数不匹配，会产生一个异常。

代码示例：

>>> p = (4, 5)
>>> x, y, z = p
traceback (most recent call last):
file "<stdin>", line 1, in <module>
valueerror: need more than 2 values to unpack
>>>

讨论

实际上，这种解压赋值可以用在任何可迭代对象上面，而不仅仅是列表或者元组。 包括字符串，文件对象，迭代器和生成器。

代码示例：

>>> s = 'hello'
>>> a, b, c, d, e = s
>>> a
'h'
>>> b
'e'
>>> e
'o'
>>>

有时候，你可能只想解压一部分，丢弃其他的值。对于这种情况 python 并没有提供特殊的语法。 但是你可以使用任意变量名去占位，到时候丢掉这些变量就行了。

代码示例：

>>> data = [ 'acme', 50, 91.1, (2012, 12, 21) ]
>>> _, shares, price, _ = data
>>> shares
50
>>> price
91.1
>>>

你必须保证你选用的那些占位变量名在其他地方没被使用到。

1.2 解压可迭代对象赋值给多个变量

问题

如果一个可迭代对象的元素个数超过变量个数时，会抛出一个 valueerror 。 那么怎样才能从这个可迭代对象中解压出 n 个元素出来？

解决方案

python 的星号表达式可以用来解决这个问题。比如，你在学习一门课程，在学期末的时候， 你想统计下家庭作业的平均成绩，但是排除掉第一个和最后一个分数。如果只有四个分数，你可能就直接去简单的手动赋值， 但如果有 24 个呢？这时候星号表达式就派上用场了：

def drop_first_last(grades):
    first, *middle, last = grades
    return avg(middle)

另外一种情况，假设你现在有一些用户的记录列表，每条记录包含一个名字、邮件，接着就是不确定数量的电话号码。 你可以像下面这样分解这些记录：

>>> record = ('dave', '[e-mail]', '773-555-1212', '847-555-1212')
>>> name, email, *phone_numbers = record
>>> name
'dave'
>>> email
'[e-mail]'
>>> phone_numbers
['773-555-1212', '847-555-1212']
>>>

值得注意的是上面解压出的 phone_numbers 变量永远都是列表类型，不管解压的电话号码数量是多少（包括 0 个）。 所以，任何使用到 phone_numbers 变量的代码就不需要做多余的类型检查去确认它是否是列表类型了。

星号表达式也能用在列表的开始部分。比如，你有一个公司前 8 个月销售数据的序列， 但是你想看下最近一个月数据和前面 7 个月的平均值的对比。你可以这样做：

*trailing_qtrs, current_qtr = sales_record
trailing_avg = sum(trailing_qtrs) / len(trailing_qtrs)
return avg_comparison(trailing_avg, current_qtr)

下面是在 python 解释器中执行的结果：

>>> *trailing, current = [10, 8, 7, 1, 9, 5, 10, 3]
>>> trailing
[10, 8, 7, 1, 9, 5, 10]
>>> current
3

讨论

扩展的迭代解压语法是专门为解压不确定个数或任意个数元素的可迭代对象而设计的。 通常，这些可迭代对象的元素结构有确定的规则（比如第 1 个元素后面都是电话号码）， 星号表达式让开发人员可以很容易的利用这些规则来解压出元素来。 而不是通过一些比较复杂的手段去获取这些关联的元素值。

值得注意的是，星号表达式在迭代元素为可变长元组的序列时是很有用的。 比如，下面是一个带有标签的元组序列：

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)

星号解压语法在字符串操作的时候也会很有用，比如字符串的分割。

代码示例：

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

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

代码示例：

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

在很多函数式语言中，星号解压语法跟列表处理有许多相似之处。比如，如果你有一个列表， 你可以很容易的将它分割成前后两部分：

>>> items = [1, 10, 7, 4, 5, 9]
>>> head, *tail = items
>>> head
1
>>> tail
[10, 7, 4, 5, 9]
>>>

如果你够聪明的话，还能用这种分割语法去巧妙的实现递归算法。比如：

>>> def sum(items):
...     head, *tail = items
...     return head + sum(tail) if tail else head
...
>>> sum(items)
36
>>>

然后，由于语言层面的限制，递归并不是 python 擅长的。 因此，最后那个递归演示仅仅是个好奇的探索罢了，对这个不要太认真了。

1.3 保留最后 n 个元素

问题

在迭代操作或者其他操作的时候，怎样只保留最后有限几个元素的历史记录？

解决方案

保留有限历史记录正是 collections.deque 大显身手的时候。比如，下面的代码在多行上面做简单的文本匹配， 并返回匹配所在行的最后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(r'../../cookbook/somefile.txt') as f:
        for line, prevlines in search(f, 'python', 5):
            for pline in prevlines:
                print(pline, end='')
            print(line, end='')
            print('-' * 20)

讨论

我们在写查询元素的代码时，通常会使用包含 yield 表达式的生成器函数，也就是我们上面示例代码中的那样。 这样可以将搜索过程代码和使用搜索结果代码解耦。如果你还不清楚什么是生成器，请参看 4.3 节。

使用 deque(maxlen=n) 构造函数会新建一个固定大小的队列。当新的元素加入并且这个队列已满的时候， 最老的元素会自动被移除掉。

代码示例：

>>> q = deque(maxlen=3)
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3], maxlen=3)
>>> q.append(4)
>>> q
deque([2, 3, 4], maxlen=3)
>>> q.append(5)
>>> q
deque([3, 4, 5], maxlen=3)

尽管你也可以手动在一个列表上实现这一的操作（比如增加、删除等等）。但是这里的队列方案会更加优雅并且运行得更快些。

更一般的， deque 类可以被用在任何你只需要一个简单队列数据结构的场合。 如果你不设置最大队列大小，那么就会得到一个无限大小队列，你可以在队列的两端执行添加和弹出元素的操作。

代码示例：

>>> q = deque()
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3])
>>> q.appendleft(4)
>>> q
deque([4, 1, 2, 3])
>>> q.pop()
3
>>> q
deque([4, 1, 2])
>>> q.popleft()
4

在队列两端插入或删除元素时间复杂度都是 o(1) ，区别于列表，在列表的开头插入或删除元素的时间复杂度为 o(n) 。

1.4 查找最大或最小的 n 个元素

问题

怎样从一个集合中获得最大或者最小的 n 个元素列表？

解决方案

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

import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # prints [-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'])

译者注：上面代码在对每个元素进行对比的时候，会以 price 的值进行比较。

讨论

如果你想在一个集合中查找最小或最大的 n 个元素，并且 n 小于集合元素数量，那么这些函数提供了很好的性能。 因为在底层实现里面，首先会先将集合数据进行堆排序后放入一个列表中：

>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> import heapq
>>> heap = list(nums)
>>> heapq.heapify(heap)
>>> heap
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
>>>

堆数据结构最重要的特征是 heap[0] 永远是最小的元素。并且剩余的元素可以很容易的通过调用 heapq.heappop() 方法得到， 该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素（这种操作时间复杂度仅仅是 o(log n)，n 是堆大小）。 比如，如果想要查找最小的 3 个元素，你可以这样做：

>>> heapq.heappop(heap)
-4
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2

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

尽管你没有必要一定使用这里的方法，但是堆数据结构的实现是一个很有趣并且值得你深入学习的东西。 基本上只要是数据结构和算法书籍里面都会有提及到。 heapq 模块的官方文档里面也详细的介绍了堆数据结构底层的实现细节。

1.5 实现一个优先级队列

问题

怎样实现一个按优先级排序的队列？ 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素

解决方案

下面的类利用 heapq 模块实现了一个简单的优先级队列：

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()
item('bar')
>>> q.pop()
item('spam')
>>> q.pop()
item('foo')
>>> q.pop()
item('grok')
>>>

仔细观察可以发现，第一个 pop() 操作返回优先级最高的元素。 另外注意到如果两个有着相同优先级的元素（ foo 和 grok ），pop 操作按照它们被插入到队列的顺序返回的。

讨论

这一小节我们主要关注 heapq 模块的使用。 函数 heapq.heappush() 和 heapq.heappop() 分别在队列 _queue 上插入和删除第一个元素， 并且队列 _queue 保证第一个元素拥有最高优先级（ 1.4 节已经讨论过这个问题）。 heappop() 函数总是返回”最小的”的元素，这就是保证队列pop操作返回正确元素的关键。 另外，由于 push 和 pop 操作时间复杂度为 o(log n)，其中 n 是堆的大小，因此就算是 n 很大的时候它们运行速度也依旧很快。

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

index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量，可以确保元素按照它们插入的顺序排序。 而且， index 变量也在相同优先级元素比较的时候起到重要作用。

为了阐明这些，先假定 item 实例是不支持排序的：

>>> a = item('foo')
>>> b = item('bar')
>>> a < b
traceback (most recent call last):
file "<stdin>", line 1, in <module>
typeerror: unorderable types: item() < item()
>>>

如果你使用元组 (priority, item) ，只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话，那么比较操作就会跟之前一样出错：

>>> a = (1, item('foo'))
>>> b = (5, item('bar'))
>>> a < b
true
>>> c = (1, item('grok'))
>>> a < c
traceback (most recent call last):
file "<stdin>", line 1, in <module>
typeerror: unorderable types: item() < item()
>>>

通过引入另外的 index 变量组成三元组 (priority, index, item) ，就能很好的避免上面的错误， 因为不可能有两个元素有相同的 index 值。python 在做元组比较时候，如果前面的比较已经可以确定结果了， 后面的比较操作就不会发生了：

>>> a = (1, 0, item('foo'))
>>> b = (5, 1, item('bar'))
>>> c = (1, 2, item('grok'))
>>> a < b
true
>>> a < c
true
>>>

如果你想在多个线程中使用同一个队列，那么你需要增加适当的锁和信号量机制。 可以查看 12.3 小节的例子演示是怎样做的。

heapq 模块的官方文档有更详细的例子程序以及对于堆理论及其实现的详细说明。

1.6 字典中的键映射多个值

问题

怎样实现一个键对应多个值的字典（也叫 multidict）？

解决方案

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

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

选择使用列表还是集合取决于你的实际需求。如果你想保持元素的插入顺序就应该使用列表， 如果想去掉重复元素就使用集合（并且不关心元素的顺序问题）。

你可以很方便的使用 collections 模块中的 defaultdict 来构造这样的字典。 defaultdict 的一个特征是它会自动初始化每个 key 刚开始对应的值，所以你只需要关注添加元素操作了。比如：

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)

需要注意的是， defaultdict 会自动为将要访问的键（就算目前字典中并不存在这样的键）创建映射实体。 如果你并不需要这样的特性，你可以在一个普通的字典上使用 setdefault() 方法来代替。比如：

d = {} # 一个普通的字典
d.setdefault('a', []).append(1)
d.setdefault('a', []).append(2)
d.setdefault('b', []).append(4)

但是很多程序员觉得 setdefault() 用起来有点别扭。因为每次调用都得创建一个新的初始值的实例（例子程序中的空列表 [] ）。

讨论

一般来讲，创建一个多值映射字典是很简单的。但是，如果你选择自己实现的话，那么对于值的初始化可能会有点麻烦， 你可能会像下面这样来实现：

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

如果使用 defaultdict 的话代码就更加简洁了：

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

这一小节所讨论的问题跟数据处理中的记录归类问题有大的关联。可以参考 1.15 小节的例子。

1.7 字典排序

问题

你想创建一个字典，并且在迭代或序列化这个字典的时候能够控制元素的顺序。

解决方案

为了能控制一个字典中元素的顺序，你可以使用 collections 模块中的 ordereddict 类。 在迭代操作的时候它会保持元素被插入时的顺序，示例如下：

from collections import ordereddict

d = ordereddict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grok'] = 4
# outputs "foo 1", "bar 2", "spam 3", "grok 4"
for key in d:
    print(key, d[key])

当你想要构建一个将来需要序列化或编码成其他格式的映射的时候， ordereddict 是非常有用的。 比如，你想精确控制以 json 编码后字段的顺序，你可以先使用 ordereddict 来构建这样的数据：

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

讨论

ordereddict 内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候， 它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。

需要注意的是，一个 ordereddict 的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。 所以如果你要构建一个需要大量 ordereddict 实例的数据结构的时候（比如读取 100,000 行 csv 数据到一个 ordereddict 列表中去）， 那么你就得仔细权衡一下是否使用 ordereddict 带来的好处要大过额外内存消耗的影响。

1.8 字典的运算

问题

怎样在数据字典中执行一些计算操作（比如求最小值、最大值、排序等等）？

解决方案

考虑下面的股票名和价格映射字典：

prices = {
    'acme': 45.23,
    'aapl': 612.78,
    'ibm': 205.55,
    'hpq': 37.20,
    'fb': 10.75
}

为了对字典值执行计算操作，通常需要使用 zip() 函数先将键和值反转过来。 比如，下面是查找最小和最大股票价格和股票值的代码：

min_price = min(zip(prices.values(), prices.keys()))
# min_price is (10.75, 'fb')
max_price = max(zip(prices.values(), prices.keys()))
# max_price is (612.78, 'aapl')

类似的，可以使用 zip() 和 sorted() 函数来排列字典数据：

prices_sorted = sorted(zip(prices.values(), prices.keys()))
# prices_sorted is [(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
print(max(prices_and_names)) # valueerror: max() arg is an empty sequence

讨论

如果你在一个字典上执行普通的数学运算，你会发现它们仅仅作用于键，而不是值。比如：

min(prices) # returns 'aapl'
max(prices) # returns 'ibm'

这个结果并不是你想要的，因为你想要在字典的值集合上执行这些计算。 或许你会尝试着使用字典的 values() 方法来解决这个问题：

min(prices.values()) # returns 10.75
max(prices.values()) # returns 612.78

不幸的是，通常这个结果同样也不是你想要的。 你可能还想要知道对应的键的信息（比如那种股票价格是最低的？）。

你可以在 min() 和 max() 函数中提供 key 函数参数来获取最小值或最大值对应的键的信息。比如：

min(prices, key=lambda k: prices[k]) # returns 'fb'
max(prices, key=lambda k: prices[k]) # returns 'aapl'

但是，如果还想要得到最小值，你又得执行一次查找操作。比如：

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

前面的 zip() 函数方案通过将字典”反转”为 (值，键) 元组序列来解决了上述问题。 当比较两个元组的时候，值会先进行比较，然后才是键。 这样的话你就能通过一条简单的语句就能很轻松的实现在字典上的求最值和排序操作了。

需要注意的是在计算操作中使用到了 (值，键) 对。当多个实体拥有相同的值的时候，键会决定返回结果。 比如，在执行 min() 和 max() 操作的时候，如果恰巧最小或最大值有重复的，那么拥有最小或最大键的实体会返回：

>>> prices = { 'aaa' : 45.23, 'zzz': 45.23 }
>>> min(zip(prices.values(), prices.keys()))
(45.23, 'aaa')
>>> max(zip(prices.values(), prices.keys()))
(45.23, 'zzz')
>>>

1.9 查找两字典的相同点

问题

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

解决方案

考虑下面两个字典：

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

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

为了寻找两个字典的相同点，可以简单的在两字典的 keys() 或者 items() 方法返回结果上执行集合操作。比如：

# find keys in common
a.keys() & b.keys() # { 'x', 'y' }
# find keys in a that are not in b
a.keys() - b.keys() # { 'z' }
# find (key,value) pairs in common
a.items() & b.items() # { ('y', 2) }

这些操作也可以用于修改或者过滤字典元素。 比如，假如你想以现有字典构造一个排除几个指定键的新字典。 下面利用字典推导来实现这样的需求：

# make a new dictionary with certain keys removed
c = {key:a[key] for key in a.keys() - {'z', 'w'}}
# c is {'x': 1, 'y': 2}

讨论

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

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

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

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

问题

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

解决方案

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

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

这里的key参数指定了一个函数，将序列元素转换成 hashable 类型。下面是它的用法示例：

>>> 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]
>>> set(a)
{1, 2, 10, 5, 9}
>>>

然而，这种方法不能维护元素的顺序，生成的结果中的元素位置被打乱。而上面的方法可以避免这种情况。

在本节中我们使用了生成器函数让我们的函数更加通用，不仅仅是局限于列表处理。 比如，如果如果你想读取一个文件，消除重复行，你可以很容易像这样做：

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

上述key函数参数模仿了 sorted() , min() 和 max() 等内置函数的相似功能。 可以参考 1.8 和 1.13 小节了解更多。

1.11 命名切片

问题

如果你的程序包含了大量无法直视的硬编码切片，并且你想清理一下代码。

解决方案

假定你要从一个记录（比如文件或其他类似格式）中的某些固定位置提取字段：

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

与其那样写，为什么不想这样命名切片呢：

shares = slice(20, 23)
price = slice(31, 37)
cost = int(record[shares]) * float(record[price])

在这个版本中，你避免了使用大量难以理解的硬编码下标。这使得你的代码更加清晰可读。

讨论

一般来讲，代码中如果出现大量的硬编码下标会使得代码的可读性和可维护性大大降低。 比如，如果你回过来看看一年前你写的代码，你会摸着脑袋想那时候自己到底想干嘛啊。 这是一个很简单的解决方案，它让你更加清晰的表达代码的目的。

内置的 slice() 函数创建了一个切片对象。所有使用切片的地方都可以使用切片对象。比如：

>>> items = [0, 1, 2, 3, 4, 5, 6]
>>> a = slice(2, 4)
>>> items[2:4]
[2, 3]
>>> items[a]
[2, 3]
>>> items[a] = [10,11]
>>> items
[0, 1, 10, 11, 4, 5, 6]
>>> del items[a]
>>> items
[0, 1, 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 异常。比如：

>>> s = 'helloworld'
>>> a.indices(len(s))
(5, 10, 2)
>>> for i in range(*a.indices(len(s))):
...     print(s[i])
...
w
r
d
>>>

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

问题

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

解决方案

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

为了演示，先假设你有一个单词列表并且想找出哪个单词出现频率最高。你可以这样做：

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)
# 出现频率最高的3个单词
top_three = word_counts.most_common(3)
print(top_three)
# outputs [('eyes', 8), ('the', 5), ('look', 4)]

讨论

作为输入， counter 对象可以接受任意的由可哈希（hashable）元素构成的序列对象。 在底层实现上，一个 counter 对象就是一个字典，将元素映射到它出现的次数上。比如：

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

或者你可以使用 update() 方法：

>>> word_counts.update(morewords)
>>>

counter 实例一个鲜为人知的特性是它们可以很容易的跟数学运算操作相结合。比如：

>>> a = counter(words)
>>> b = counter(morewords)
>>> a
counter({'eyes': 8, 'the': 5, 'look': 4, 'into': 3, 'my': 3, 'around': 2,
"you're": 1, "don't": 1, 'under': 1, 'not': 1})
>>> b
counter({'eyes': 1, 'looking': 1, 'are': 1, 'in': 1, 'not': 1, 'you': 1,
'my': 1, 'why': 1})
>>> # combine counts
>>> c = a + b
>>> c
counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2,
'around': 2, "you're": 1, "don't": 1, 'in': 1, 'why': 1,
'looking': 1, 'are': 1, 'under': 1, 'you': 1})
>>> # subtract counts
>>> d = a - b
>>> d
counter({'eyes': 7, 'the': 5, 'look': 4, 'into': 3, 'my': 2, 'around': 2,
"you're": 1, "don't": 1, 'under': 1})
>>>

毫无疑问， counter 对象在几乎所有需要制表或者计数数据的场合是非常有用的工具。 在解决这类问题的时候你应该优先选择它，而不是手动的利用字典去实现。

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

问题

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

解决方案

通过使用 operator 模块的 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}
]

根据任意的字典字段来排序输入结果行是很容易实现的，代码示例：

from operator import itemgetter
rows_by_fname = sorted(rows, key=itemgetter('fname'))
rows_by_uid = sorted(rows, key=itemgetter('uid'))
print(rows_by_fname)
print(rows_by_uid)

代码的输出如下：

[{'fname': 'big', 'uid': 1004, 'lname': 'jones'},
{'fname': 'brian', 'uid': 1003, 'lname': 'jones'},
{'fname': 'david', 'uid': 1002, 'lname': 'beazley'},
{'fname': 'john', 'uid': 1001, 'lname': 'cleese'}]
[{'fname': 'john', 'uid': 1001, 'lname': 'cleese'},
{'fname': 'david', 'uid': 1002, 'lname': 'beazley'},
{'fname': 'brian', 'uid': 1003, 'lname': 'jones'},
{'fname': 'big', 'uid': 1004, 'lname': 'jones'}]

itemgetter() 函数也支持多个 keys，比如下面的代码

rows_by_lfname = sorted(rows, key=itemgetter('lname','fname'))
print(rows_by_lfname)

会产生如下的输出：

[{'fname': 'david', 'uid': 1002, 'lname': 'beazley'},
{'fname': 'john', 'uid': 1001, 'lname': 'cleese'},
{'fname': 'big', 'uid': 1004, 'lname': 'jones'},
{'fname': 'brian', 'uid': 1003, 'lname': 'jones'}]

讨论

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

operator.itemgetter() 函数有一个被 rows 中的记录用来查找值的索引参数。可以是一个字典键名称， 一个整形值或者任何能够传入一个对象的 __getitem__() 方法的值。 如果你传入多个索引参数给 itemgetter() ，它生成的 callable 对象会返回一个包含所有元素值的元组， 并且 sorted() 函数会根据这个元组中元素顺序去排序。 但你想要同时在几个字段上面进行排序（比如通过姓和名来排序，也就是例子中的那样）的时候这种方法是很有用的。

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

rows_by_fname = sorted(rows, key=lambda r: r['fname'])
rows_by_lfname = sorted(rows, key=lambda r: (r['lname'],r['fname']))

这种方案也不错。但是，使用 itemgetter() 方式会运行的稍微快点。因此，如果你对性能要求比较高的话就使用 itemgetter() 方式。

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

>>> min(rows, key=itemgetter('uid'))
{'fname': 'john', 'lname': 'cleese', 'uid': 1001}
>>> max(rows, key=itemgetter('uid'))
{'fname': 'big', 'lname': 'jones', 'uid': 1004}
>>>

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

问题

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

解决方案

内置的 sorted() 函数有一个关键字参数 key ，可以传入一个 callable 对象给它， 这个 callable 对象对每个传入的对象返回一个值，这个值会被 sorted 用来排序这些对象。 比如，如果你在应用程序里面有一个 user 实例序列，并且你希望通过他们的 user_id 属性进行排序， 你可以提供一个以 user 实例作为输入并输出对应 user_id 值的 callable 对象。比如：

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

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

>>> from operator import attrgetter
>>> sorted(users, key=attrgetter('user_id'))
[user(3), user(23), user(99)]
>>>

讨论

选择使用 lambda 函数或者是 attrgetter() 可能取决于个人喜好。 但是， attrgetter() 函数通常会运行的快点，并且还能同时允许多个字段进行比较。 这个跟 operator.itemgetter() 函数作用于字典类型很类似（参考1.13小节）。 例如，如果 user 实例还有一个 first_name 和 last_name 属性，那么可以向下面这样排序：

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

同样需要注意的是，这一小节用到的技术同样适用于像 min() 和 max() 之类的函数。比如：

>>> min(users, key=attrgetter('user_id'))
user(3)
>>> max(users, key=attrgetter('user_id'))
user(99)
>>>

1.15 通过某个字段将记录分组

问题

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

解决方案

itertools.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'},
]

现在假设你想在按 date 分组后的数据块上进行迭代。为了这样做，你首先需要按照指定的字段(这里就是 date )排序， 然后调用 itertools.groupby() 函数：

from operator import itemgetter
from itertools import groupby

# 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
  {'date': '07/01/2012', 'address': '5412 n clark'}
  {'date': '07/01/2012', 'address': '4801 n broadway'}
07/02/2012
  {'date': '07/02/2012', 'address': '5800 e 58th'}
  {'date': '07/02/2012', 'address': '5645 n ravenswood'}
  {'date': '07/02/2012', 'address': '1060 w addison'}
07/03/2012
  {'date': '07/03/2012', 'address': '2122 n clark'}
07/04/2012
  {'date': '07/04/2012', 'address': '5148 n clark'}
  {'date': '07/04/2012', 'address': '1039 w granville'}

讨论

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

一个非常重要的准备步骤是要根据指定的字段将数据排序。 因为 groupby() 仅仅检查连续的元素，如果事先并没有排序完成的话，分组函数将得不到想要的结果。

如果你仅仅只是想根据 date 字段将数据分组到一个大的数据结构中去，并且允许随机访问， 那么你最好使用 defaultdict() 来构建一个多值字典，关于多值字典已经在 1.6 小节有过详细的介绍。比如：

from collections import defaultdict
rows_by_date = defaultdict(list)
for row in rows:
    rows_by_date[row['date']].append(row)

这样的话你可以很轻松的就能对每个指定日期访问对应的记录：

>>> for r in rows_by_date['07/01/2012']:
... print(r)
...
{'date': '07/01/2012', 'address': '5412 n clark'}
{'date': '07/01/2012', 'address': '4801 n broadway'}
>>>

在上面这个例子中，我们没有必要先将记录排序。因此，如果对内存占用不是很关心， 这种方式会比先排序然后再通过 groupby() 函数迭代的方式运行得快一些。

1.16 过滤序列元素

赞 (0)

打赏 微信扫一扫

相关文章:

• 

  Django 系列博客（十二）

  Django 系列博客（十二） 前言 本篇博客继续介绍 Django 中的查询，分别为聚合查询和分组查询，以及 F 和 Q 查询。 聚合查询 语法：... [阅读全文]
• 

  python编程规范系列--建议01～07

  本系列来自《编写高质量代码 改善python程序的91个建议》的读书笔记整理。 ... [阅读全文]
• 

  Spring Boot 学习目录

  之前一直做.net 的开发，后来发现C# 在生态方面和Java还是差了好多，而且目前有很多.net 方面的技术也是借鉴了Java相关的开发，所以最近... [阅读全文]
• 

  铁路查询系统

  本实例综合运用了列表、字典、元祖以及for循环、while循环和if-else语句，是入门同学比较经典的事例之一。 ... [阅读全文]
• 

  ZooKeeper伪集群的搭建（Windows）

  首先下载 zookeeper 地址：https://www.apache.org/dyn/closer.cgi/zookeeper/ 1、下载完成解... [阅读全文]

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 [e-mail] 举报，一经查实将立刻删除。

发表评论

验证码：