[TOC]
到目前为止，在我们的例子中，我们已经看到了许多内置的Python数据结构。你可能已经在介绍性文章或教程中了解了一些数据结构。在本章中，我们将讨论这些数据结构中的面向对象的特性，何时应该使用它们来代替常规类，以及何时不应该使用它们。特别的，我们将了解：
* 元组和命名元组
* 词典
* 列表和集合
* 如何以及为什么扩展内置对象
* 三种类型的队列
## 空对象
让我们从最基本的Python内置类型开始，我们已经见过很多次了，我们创建的每个类都继承自它：对象`object`。技术上，我们可以实例化一个对象，而不需要编写它的子类：
```
>>> o = object()
>>> o.x = 5
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'object' object has no attribute 'x'
```
不幸的是，如你所见，我们不能在直接实例化的对象上设置任何属性。这不是因为Python开发人员想要强制我们写我们自己的类，或者其他任何如此险恶的事情。他们这样做是为了节省内存；很多很多内存。当Python允许对象具有任意属性时，需要一定量的系统内存存储属性名及属性值，用于跟踪每个对象的属性。即使没有存储属性，仍然需要分配内存给*潜在的*新属性。鉴于典型的Python程序存在数十、数百或数千个的对象（每个类都扩展自`object`）；每一笔小的内存开销很快汇成大量的内存消耗。所以，默认情况下，Python会禁用`object`和其他几个内置类型添加任意属性。
> 可以使用`slots`来限制对我们自己类添加任意属性。`slots`超出了本书的范围，你可以使用搜索词查找更多的信息。在正常使用中，使用`slots`没什么好处，但是如果你在写一个将在整个系统中复制数千次的对象，它可以帮助节省内存，就像它对`object`那样。
然而，创建一个我们自己的空对象类是微不足道的；我们在我们的最早的例子中看过这样的空对象类：
```
class MyObject:
pass
```
正如我们已经看到的，我们可以在这样的类上设置属性：
```
>>> m = MyObject()
>>> m.x = "hello"
>>> m.x
'hello'
```
如果我们想将属性组合在一起，我们可以像这样将它们存储在一个空对象中。但是通常我们最好使用其他为存储数据而设计的内置类型。我们在整本书都强调类和对象只应该在我们希望*同时*指定数据和行为的情况下使用。写空类的主要原因就是快速封锁一些东西，我们稍后会回来增加行为。空类很容易修改行为，这比用对象替换数据结构并更改对它的所有引用，要容易得多。因此，从一开始就要判断数据仅仅是数据，还是它是伪装的对象。一旦设计决策完成后，剩下的设计就水到渠成了。
## 元组和命名元组
元组是可以按顺序存储特定数量的其他对象的对象。它们是不可变的，所以我们不能在元组之上添加、删除或替换对象。这似乎就像一个巨大的限制，但事实是，如果你需要修改元组，你多半正在使用错误的数据类型（通常列表更合适）。元组不变性的主要好处是，我们可以把它们作为字典的键，或者对象需要哈希值的其他地方。
</b>
元组用于存储数据；行为不能存储在元组中。如果我们需要操纵元组，我们必须将元组传递给函数（或者其他对象方法）来执行操作。
</b>
元组通常应该存储彼此不同的值。例如，我们不会将三个股票符号放在一个元组中，但是我们可以创建一个包含股票符号、当前价格、当天的高低价格的元组。使用元组的主要目的是将不同的数据片段集合到一个容器中。因此，元组可以是替换“无数据对象”的最简单的工具。
</b>
我们可以通过用逗号分隔值来创建元组。通常，元组是用圆括号括起来，以便于阅读和区分表达式的其他部分，但这并不总是强制性的。以下两种赋值写法是相同的（它们记录一家盈利公司的股票符号、当前价格、高点和低点价格）：
```
>>> stock = "FB", 75.00, 75.03, 74.90
>>> stock2 = ("FB", 75.00, 75.03, 74.90)
```
如果我们在某个其他对象（如函数调用、列表或生成器）内部使用元组，括号是必需的。否则，解释器将无从判断它是元组还是下一个函数参数。例如，以下函数接受元组和日期，并返回一个包含日期和股票高低价平均值的元组：
```
import datetime
def middle(stock, date):
symbol, current, high, low = stock
return (((high + low) / 2), date)
mid_value, date = middle(("FB", 75.00, 75.03, 74.90),
datetime.date(2014, 10, 31))
```
元组是通过将值用逗号分隔开，并将整个元组括在括号中。作为函数参数的元组，用逗号将它与函数的第二个参数分开。
</b>
这个例子还说明了元组解包。函数内部的第一行将`stock`参数拆分为四个不同的变量。元组长度必须与变量的数量完全相同，否则会引发异常。我们还可以在最后一行看到元组解包的示例，函数内部返回了一个元组，该元组被解包成两个值，中间值`mid_value `和日期`date`。当然，有点奇怪的是，我们首先为函数提供了日期，但是这给了我们一个查看解包是如何工作的机会。
</b>
解包是Python中非常有用的特性。我们可以将变量组成元组，让存储和传递它们变得更简单，但是当我们需要访问它们时，我们可以把它们分解成单独的变量。当然，有时候我们只需要访问元组中的一个变量。我们可以使用与其他序列类型(例如列表和字符串)相同的语法来访问单个值：
```
>>> stock = "FB", 75.00, 75.03, 74.90
>>> high = stock[2]
>>> high
75.03
```
我们甚至可以使用切片获取元组的一个片段：
```
>>> stock[1:3]
(75.00, 75.03)
```
这些例子虽然说明了元组是多么灵活，但也展示了一个主要缺点：可读性。一个人阅读这些代码，怎么会知道特定元组的第二个位置代表的是什么呢？从我们赋予它的变量名称，人们可以猜测，它在某种程度上是`high`，但是如果我们在没有分配元组值的情况下访问计算中的元组值，就不会有这样的暗示。人们将不得不在探索元组之前是什么，在代码中寻找声明元组的位置。
</b>
在某些情况下，直接访问元组成员是可以的，但不要成为一种习惯。这种所谓的“神奇数字”（似乎来自代码中没有明显含义的稀薄空气）是许多编码的错误来源并导致几个小时的失败调试。只有当你知道所有的元组值都会立刻有用才使用元组，而且通常在访问时才解包。如果你必须直接访问成员或使用切片并且该值的目的不是显而易见的，至少加一些注释解释它来自哪里。
### 命名元组
那么，当我们想把某些值组合在一起，又知道我们经常需要单独访问它们时，我们该怎么做？我们可以使用一个空对象，就像上一节已经讨论过了的（但是除非我们预期会添加行为），或者我们可以使用字典（如果我们不知道具体有多少特定数据将被存储，这将非常有用），这将在下一节中介绍。
</b>
然而，如果我们不需要向对象添加行为，并且事先知道我们需要存储什么属性，我们可以使用命名元组。命名元组是带有属性的元组。它们是将只读数据进行分组的一个好方法。
</b>
构建一个命名元组比构建一个普通元组多一些工作。首先，我们必须导入`namedtuple`，因为默认情况下它不在命名空间中。然后，我们通过给命名元组命名并概述其属性来描述命名元组。这会返回一个类似类的对象，我们可以随时用我们所需要的值来实例化它们：
```
from collections import namedtuple
Stock = namedtuple("Stock", "symbol current high low")
stock = Stock("FB", 75.00, high=75.03, low=74.90)
```
`namedtuple`构造函数接受两个参数。第一个是命名元组的标识。第二个参数是一串以空格分隔、元组的属性字符串。第一个属性被列出，后跟一个空格（或逗号，看你喜欢），然后是第二个属性，然后是另一个空格，依此类推。结果是一个对象，可以像普通类一样调用来实例化其他对象。这个构造函数必须传入正确数量的参数，作为参数或键参数。和普通对象一样，我们可以创造尽可能多的这个“类”的实例，每个实例都有不同的值。
</b>
然后，可以将生成的`namedtuple`的文件打包、解包，像普通元组那样操作，但是我们也可以像访问对象一样访问它的单个属性：
```
>>> stock.high
75.03
>>> symbol, current, high, low = stock
>>> current
75.00
```
> 请记住，创建命名元组是一个两步过程。首先，使用`collections.namedtuple`创建一个类，然后构造该类的实例。
命名元组对于许多“仅数据”表示来说是完美的，但是它们并不适用于所有情况。像元组和字符串一样，命名元组是不可变的，所以我们不能设置属性后修改它。例如，自从我们开始讨论以来，我公司的股票当前值已经下跌，但是我们不能设置新值:
```
>>> stock.current = 74.98
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: can't set attribute
```
如果我们需要能够改变已经存储的数据，字典可能是我们需要的。
## 字典
字典是非常有用的容器，允许我们直接将对象映射到其他对象上。具有属性的空对象是一种字典；名字属性映射到属性值。这实际上比听起来更接近事实。在内部，对象通常将属性表示为字典，其中值是对象的属性或方法（如果你不相信我，请参见`__dict__`属性）。甚至模块上的属性也存储在内部字典中。
</b>
给定一个特定的键，这个键是映射到某个值的对象，通过字典很容易找到这个值。当你想基于一个对象找到另一个对象的时候，应该一直使用字典。正在被存储的对象称为**值**；用作索引的对象称为**键**。我们已经在前面一些例子中看到了字典语法。
</b>
字典可以使用`dict()`构造函数或`{}`快捷方式创建。实际上，后一种格式几乎总是被使用。我们可以预先填充一个字典，通过使用冒号将键与值分开，然后使用逗号将键值对分开。
</b>
例如，在股票应用程序中，我们通常希望通过股票符号查询价格。我们可以创建一个以股票符号作为键、以当前价格、高价和低价构成的元组作为键值的字典：
```
stocks = {"GOOG": (613.30, 625.86, 610.50),
"MSFT": (30.25, 30.70, 30.19)}
```
正如我们在前面的例子中看到的，我们可以在字典中通过请求方括号内的键来查找值。如果键不在字典里，它会的引发异常：
```
>>> stocks["GOOG"]
(613.3, 625.86, 610.5)
>>> stocks["RIM"]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'RIM'
```
当然，我们可以捕捉`KeyError`并处理它。但是我们还有其他选择。记住，字典是对象，即使它们的主要目的是容纳其他的对象。因此，它们有几种相关的行为。其中这些方法中最有用的是`get`方法；它接受一个键作为第一个参数，和一个如果键不存在时可选的默认值：
```
>>> print(stocks.get("RIM"))
None
>>> stocks.get("RIM", "NOT FOUND")
'NOT FOUND'
```
为了获得更多的控制，我们可以使用`setdefault`方法。如果键在字典里，这个方法的行为就像`get`一样返回该键的值。否则，如果键不在字典中，它不仅会返回我们在方法中提供的默认值（就像`get`做的那样），它也将给这个键设置同样的默认值。另一种思考方式是`setdefault`只在字典中不存在一个键的值时，才会设置该键的值。它返回的值，要么是已经存在的，要么是一个新提供的默认值。
```
>>> stocks.setdefault("GOOG", "INVALID")
(613.3, 625.86, 610.5)
>>> stocks.setdefault("BBRY", (10.50, 10.62, 10.39))
(10.50, 10.62, 10.39)
>>> stocks["BBRY"]
(10.50, 10.62, 10.39)
```
` GOOG`股票已经在字典里了，所以当我们试图使用`setdefault`方法为它设置无效值时，它只会返回字典中已经存在的值。`BBRY`不在字典中，所以`setdefault`返回默认值，并在给我们的字典添加了新的键值对。随后我们可以查看字典里的新股票。
</b>
另外三种非常有用的字典方法是`keys()`、`values()`和`items()`。前两个返回字典中所有键的迭代器和所有值的迭代器。我们可以像使用列表那样使用它们，如果我们想处理所有的键或值，可以在for循环中使用它们。`items()`方法可能是最有用的；它为字典中每个项目配对返回一个元组迭代器`(key，value)`。使用元组解包对for循环中历遍相关的键和值非常有用。下面这个例子打印了字典中每种股票的当前价格：
```
>>> for stock, values in stocks.items():
... print("{} last value is {}".format(stock, values[0]))
...
GOOG last value is 613.3
BBRY last value is 10.50
MSFT last value is 30.25
```
每个键/值元组被解包成两个名为`stock`和`values`的变量（我们可以使用任何我们想要的变量名，但是这两个名字似乎都是合适的），然后打印格式化字符串。
</b>
请注意，股票的显示顺序不同于它们的插入顺序。由于高效的算法（哈希算法）被用来键查找，用以提高查询效率，所以，字典本质上是无序的。
</b>
因此，一旦字典被实例化，就有很多数据被检索的方法；我们可以使用方括号作为索引查询，以及`get`方法、`setdefault`方法，或者`items`方法上的迭代器，等等。
</b>
最后，你可能已经知道，我们可以使用与检索值时使用的索引语法相同的语法给键设置值：
```
>>> stocks["GOOG"] = (597.63, 610.00, 596.28)
>>> stocks['GOOG']
(597.63, 610.0, 596.28)
```
谷歌今天的价格更低，所以我更新了字典中的元组值。我们可以使用此索引语法为任何键设置值，而不用管键是否在字典里。如果键在字典中，旧值将被新值替换；否则，将创建一个新的键/值对。
</b>
到目前为止，我们一直使用字符串作为字典键，但并不局限于字符串键。通常使用字符串作为键，尤其是当我们用字典来存储收集来的数据（而不是使用具有命名属性的对象）。但是我们也可以使用元组、数字，甚至我们自己定义的对象作为字典键。我们甚至可以在一个字典中使用不同类型的键：
```
random_keys = {}
random_keys["astring"] = "somestring"
random_keys[5] = "aninteger"
random_keys[25.2] = "floats work too"
random_keys[("abc", 123)] = "so do tuples"
class AnObject:
def __init__(self, avalue):
self.avalue = avalue
my_object = AnObject(14)
random_keys[my_object] = "We can even store objects"
my_object.avalue = 12
try:
random_keys[[1,2,3]] = "we can't store lists though"
except:
print("unable to store list\n")
for key, value in random_keys.items():
print("{} has value {}".format(key, value))
```
这段代码显示了我们可以提供给字典的几种不同类型的键。它也显示一种无法使用的对象类型。我们已经广泛使用了列表，我们将在下一节看到更多的细节。因为列表可以随时更改（例如，通过添加或删除项目），所以它们不能哈希为特定的值。
</b>
可**哈希**的对象有一个预定义算法，可以将对象转换为唯一的整数值以便快速查找。这个哈希值实际上在字典中被用来查找值。例如，字符串基于字符串中的字符被映射为整数，而元组是元组中项目的哈希值的组合。任何两个在某种程度上被认为相等的对象（就像具有相同字符的字符串或具有相同值的元组）应该具有相同的哈希值，对象的哈希值永远不应该改变。然而，列表可以更改它们的内容，这将改变它们的哈希值（两个列表的哈希值当且仅当它们的内容相同时才会相等）。正因为如此，它们不能用作字典的键。出于同样的原因，字典也不能用作其他字典的键。
</b>
相比之下，可以用作字典键值的对象类型没有这样的限制。例如，我们可以把字符串键映射到列表值上，或者我们可以将嵌套字典作为另一个字典中的值。
### 用户字典
字典的用途非常广泛。有两个主要的使用方法。第一种方法是所有的字典键代表相似对象的不同实例；例如，我们的股票字典。这是一个索引系统。我们使用股票符号作为值的索引。这些值甚至可能是复杂的自定义的对象，用于购买和出售决策，或设定止损，而不是简单的元组。
</b>
第二种设计是字典的每个键代表一个结构的某个方面；在这种情况下，我们最好为每个对象使用单独的字典，他们都有相似（虽然通常不完全相同）的键。这种情况也可以用命名元组来解决。如果使用命名元组，我们得确切地知道数据必须存储哪些属性，并且我们知道我们可以立即提供这些属性数据（当项目被构建时）。但是如果我们需要随着时间的推移创建或更改字典键，或者我们不知道具体会出现什么键，字典可能更合适。
### 使用默认字典
我们已经看到了如果一个键不存在，如何使用`setdefault`来设置默认值，但是如果我们每次查询时都需要设置默认值，这可能会变得有点乏味。例如，如果我们正在计算字母出现在给定的句子中的数量，我们可以这样做：
```
def letter_frequency(sentence):
frequencies = {}
for letter in sentence:
frequency = frequencies.setdefault(letter, 0)
frequencies[letter] = frequency + 1
return frequencies
```
每次我们访问字典，我们都需要检查它是否已经有一个键值，如果没有，将其设置为零。如果每次都需要查询空键的话，我们可以使用另外一种不同版本的字典，称为`defaultdict`：
```
from collections import defaultdict
def letter_frequency(sentence):
frequencies = defaultdict(int)
for letter in sentence:
frequencies[letter] += 1
return frequencies
```
这段代码看起来不可能工作。`defaultdict`在它的构造函数接受一个函数。当访问字典中还没有定义的键时，它调用没有参数的函数为这个键创建默认值。
</b>
在这种情况下，它调用的函数是`int`，它是整数对象的构造函数。通常，只需在代码中输入一个整数就可以创建整数，并且如果我们确实使用`int`构造函数创建了一个整数，我们会将我们想要创建的项传递给它（例如，将数字串转换成整数）。但是如果我们调用不带参数的`int`构造函数（即`int()`），它会返回数字零。在这段代码中，如果字母不存在于`defaultdict`中，当我们访问它时会返回零。然后我们给这个数字加一，表示我们找到了这个字母的一个实例，下一次我们找到一个，这个数字将被返回，我们可以再次增加这个值。
</b>
`defaultdict`对于创建容器字典很有用。如果我们想创建一个过去30天的股票价格字典，我们可以使用股票符号作为键，将价格存储在列表`list`中；我们第一次接触股票价格时，我们希望创建一个空列表。只需将列表`list`传递给`defaultdict`，然后每次访问空键时都会调用它。我们可以用集合或者一个空字典做类似的事情，如果我们想与一个键相关联的话。
</b>
当然，我们也可以编写自己的函数，并将它们传递给`defaultdict`。假设我们想要创建一个`defaultdict`，其中每个新元素包含一个元组，元组内有一个表示当前插入字典的条目数和空列表。没人知道我们为什么要创造这样一个对象，但是让我们看看这个对象长什么样子的：
```
from collections import defaultdict
num_items = 0
def tuple_counter():
global num_items
num_items += 1
return (num_items, [])
d = defaultdict(tuple_counter)
```
当我们运行这段代码时，我们可以在一行代码同时访问空键并插入一个列表：
```
>>> d = defaultdict(tuple_counter)
>>> d['a'][1].append("hello")
>>> d['b'][1].append('world')
>>> d
defaultdict(<function tuple_counter at 0x82f2c6c>,
{'a': (1, ['hello']), 'b': (2, ['world'])})
```
当我们在最后打印`dict`时，我们看到计数器真的在工作。
> 这个例子，虽然简洁地展示了如何为`defaultdict`创建我们自己的函数，实际上不是很好的代码；使用全局变量意味着如果我们创建了四个（译注：为什么是四个？）不同的`defaultdict`代码段，每个代码段都使用`tuple_counter`，它会计数所有字典中的条目数，而不是为每个字典计算不同的条目数。最好创建一个类并将这个类的一个方法传递给`defaultdict`。
#### 计数器
你可能会认为你不能比`defaultdict(int)`做得更简单了，但是“我想以可迭代的方式统计特定实例的数量”是一个已经足够常见的用例，所以Python开发人员为它创建了一个特定的类。之前用于统计字符串字符数量的代码，可以很容易地在一行代码中计算出来：
```
from collections import Counter
def letter_frequency(sentence):
return Counter(sentence)
```
计数器对象的行为就像一个增强的字典，其中键是被计数的项目，值是这些项目的数量。其中最有用的一个函数是`most_common()`方法。它返回一个按照计数排序的`(key，value)`元组列表。你可以选择将整数参数传递到`most_common()`中，以便只查看最常见的元素。例如，你可以写一个简单的投票应用程序，如下所示：
```
from collections import Counter
responses = [
"vanilla",
"chocolate",
"vanilla",
"vanilla",
"caramel",
"strawberry",
"vanilla"
]
print(
"The children voted for {} ice cream".format(
Counter(responses).most_common(1)[0][0]
)
)
```
大概，你会从数据库得到统计数量，或使用复杂的视觉算法计算举手孩子的数量。在这里，我们把它硬编码成这样，以便于我们可以测试`most_common`方法。它返回只有一个元素的列表（因为我们只请求返回一个元素）。此元素存储位置是0、排名第一的名称，因此被调用的函数以双`[0][0]`结束。我觉得它们看起来像一张惊讶的脸，不是吗？你的电脑可能很惊讶它可以如此轻松地计算数据。它的祖先，1890年美国人口普查的霍尔瑞斯制表机，知道后一定很嫉妒！
## 列表
列表是Python数据结构中最不面向对象的。虽然列表本身是对象，Python中有很多语法可以尽可能地轻松使用它们。与许多其他面向对象语言不同，Python中的列表简单易用。我们不需要导入它们，也很少需要在它们身上调用方法。我们可以在列表中历遍，而无需显式请求迭代器对象，我们可以用自定义语法构建一个列表（就像字典一样）。此外，列表解析和生成器表达式使它们成为计算中名副其实的瑞士军刀。
</b>
我们不会深入到语法的太多细节；你可以通过网络的入门教程和本书前面的例子中看到列表。如果你不学习如何使用列表，你不可能编写很好的python代码！我们将学习何时使用列表，以及它们作为对象的性质。如果你不知道如何创建或向列表添加元素，如何从列表中检索项目，或者什么是“切片符号”，你最好尽快查看官方Python教程。你可以在[https://docs.python.org/3/tutorial/](https://docs.python.org/3/tutorial/)找到它们。
</b>
在Python中，当我们想要存储几个具有“相同”类型对象实例时，最常用的就是列表；例如字符串列表或数字列表；最常见的是，我们自定义的对象列表。当我们想要以某种秩序存储项目时，应该始终使用列表。通常，这是它们被插入的顺序，但是它们也可以按照一些标准来排序。
</b>
正如我们在前几章案例研究中看到的，当我们需要修改内容时，列表是非常有用的：插入对象到任意位置或从任意位置删除对象，或者更新列表中的值。
</b>
像字典一样，Python列表使用一个非常有效且经过良好调教的内部数据结构，这样我们就可以只关心我们储存的是什么，而不是考虑如何储存它。许多面向对象语言为队列、堆栈、链表和基于数组的列表提供不同的数据结构（译注：这点特别要留意一下）。Python确实提供了其中一些类的特殊实例，用来优化对大量数据集的访问。然而，通常情况下，列表数据结构可以同时服务于所有这些目的，程序员可以完全控制如何访问它。
</b>
不要使用列表来收集具有单个项目的不同属性。例如，一个特定形式的属性列表，这并不是我们所希望的列表，元组、命名元组、字典和对象都更适合这个目的。在一些语言里，它们可能会创建一个列表，其中每个替换项都有不同的类型；例如，它们可能将字母频率列表写成['a '，1，' b '，3]。它们必须使用一个奇怪的循环，一次访问列表中的两个元素或使用一个模数操作符决定访问哪个位置。
</b>
不要在Python中做这个。我们可以使用字典将相关的项目组合在一起，如我们在上一节中所做的（如果顺序无关紧要），或者使用元组列表。这里有一个相当复杂的例子，展示了我们如何使用列表计算频率的示例。它比字典中的例子复杂得多，而且说明选择正确（或错误）的数据结构将影响我们代码的可读性：
```
import string
CHARACTERS = list(string.ascii_letters) + [" "]
def letter_frequency(sentence):
frequencies = [(c, 0) for c in CHARACTERS]
for letter in sentence:
index = CHARACTERS.index(letter)
frequencies[index] = (letter,frequencies[index][1]+1)
return frequencies
```
这段代码以可能的字符列表开始。`string.ascii_letters`属性按顺序提供所有小写和大写字母的字符串。我们将它转换为列表，然后使用列表串联（加号运算符将两个列表合并成一个）添加一个字符，即空格。这些是我们频率列表中的可用字符（如果我们试图添加不在列表中的字母，会引起程序崩溃，但是异常处理程序可以解决这个问题）。
</b>
函数的第一行使用列表解析将字符列表转换成元组列表。列表解析是Python中一个重要的、非面向对象的的工具；我们将在下一章详细介绍它们。
</b>
然后我们循环遍历句子中的每个字符。我们首先查找字符列表中的字符索引，我们知道我们的频率列表也具有同样的索引，因为我们刚刚从第一个列表创建了第二个列表。然后我们创建一个新元组来更新频率列表的索引，同时丢弃原来的元组。除了垃圾收集和内存浪费之外，它还很难阅读！
</b>
像字典一样，列表也是对象，它们有几种可以调用的方法。以下是一些常见的例子：
* `append(element)`方法在列表末尾添加一个元素
* `insert(index, element)`方法在特定位置插入项目
* `count(element)`方法告诉我们一个元素在列表中出现了多少次
* `index()`方法告诉我们列表中某项的索引，如果找不到，则引发异常
* `find()`方法做同样的事情，但是返回-1而不是引发遗失项目的异常
* `reverse()`方法完全按照它所说的做——反转列表
* `sort()`方法有一些相当复杂的面向对象行为，我们现在将讨论这个问题
### 排序列表
没有任何参数，`sort`通常会做预期的事情。如果它是一个列表字符串，它会按字母顺序排列。这个操作区分大小写，所以所有大写字母将在小写字母之前排序，也就是说，Z在a之前。如果是数字列表，它们将按数字顺序排序。如果提供的是元组列表，列表按每个元组中的第一个元素排序。如果列表含混合的不可排序的项，排序将引发`TypeError`异常。
</b>
如果我们想把我们定义的对象放入到一个列表中，并希望这些对象可排序，我们必须做更多的工作。特殊方法`__lt__`，代表“小于”，以使该类的实例具有可比性。列表中的`sort`方法将在每个对象上访问该方法，以确定该对象在列表中的位置。如果我们的类在某种程度上小于传入参数，`__lt__`方法返回True，否则返回False。这里有一个相当愚蠢的类，可以基于字符串或数字对其排序：
```
class WeirdSortee:
def __init__(self, string, number, sort_num):
self.string = string
self.number = number
self.sort_num = sort_num.
def __lt__(self, object):
if self.sort_num:
return self.number < object.number
return self.string < object.string
def __repr__(self):
return"{}:{}".format(self.string, self.number)
```
`__repr__`方法使我们打印列表时很容易看到这两个值。`__lt__`方法的实现将对象与的另一个同类实例进行比较（或者任何具有`string`, `number`和`sort_num`属性的鸭子类型的对象；如果这些属性缺失，它将失败)。以下输出说明了这个类是如何排序的：
```
>>> a = WeirdSortee('a', 4, True)
>>> b = WeirdSortee('b', 3, True)
>>> c = WeirdSortee('c', 2, True)
>>> d = WeirdSortee('d', 1, True)
>>> l = [a,b,c,d]
>>> print(l)
[a:4, b:3, c:2, d:1]
>>> l.sort()
>>> print(l)
[d:1, c:2, b:3, a:4]
>>> for i in l:
... i.sort_num = False
...
>>> l.sort()
>>> l
[a:4, b:3, c:2, d:1]
```
我们第一次调用`sort`，它是按数字排序的，因为所有正在比较的对象的`sort_num`是TRUE。第二次，它按字母排序。`__lt__`方法是我们实现排序所需要的唯一方法。然而，从技术上讲，如果`__lt__`方法可以实现，那么类通常也能实现类似的`__gt__`，`__eq__`、`__ne__`、`__ge__`、和`__le__`方法，以便所有<、>、==、！=、> =、和< =操作符也能正常工作。你可以先实现`__lt__`和`__eq__`，然后应用`@total_ordering`类装饰器来提供其余的操作符：
```
from functools import total_ordering
@total_ordering
class WeirdSortee:
def __init__(self, string, number, sort_num):
self.string = string
self.number = number
self.sort_num = sort_num
def __lt__(self, object):
if self.sort_num:
return self.number < object.number
return self.string < object.string
def __repr__(self):
return"{}:{}".format(self.string, self.number)
def __eq__(self, object):
return all((
self.string == object.string,
self.number == object.number,
self.sort_num == object.number
))
```
如果我们想在对象上使用操作符，这很有用。然而，假设我们想要做的是定制我们的排序顺序，即使这么做是多余的。对于这种用例，`sort`方法可以采用可选的键参数。这个参数是一个函数，可以将列表中的每个对象翻译成可以进行比较的对象。例如，我们可以使用`str.lower`作为键参数来执行不区分大小写的字符串列表排序：
```
>>> l = ["hello", "HELP", "Helo"]
>>> l.sort()
>>> l
['HELP', 'Helo', 'hello']
>>> l.sort(key=str.lower)
>>> l
['hello', 'Helo', 'HELP']
```
记住，即使`lower`是字符串对象上的方法，它也是一个函数，可以接受唯一的参数，`self`。换句话说，`str.lower(item)`等效于`item.lower()`。当我们将这个函数作为键传递时，它会执行基于小写字母的比较，而不是进行默认的区分大小写的比较。
</b>
有几个排序关键操作如此常见，以至于Python团队提供了它们，这样你就不用自己写了。例如，按照元组列表中第一项之外的内容对元组列表进行排序是很常见的。
`operator.itemgetter`方法可以用作实现此目的的键参数：
```
>>> from operator import itemgetter
>>> l = [('h', 4), ('n', 6), ('o', 5), ('p', 1), ('t', 3), ('y', 2)]
>>> l.sort(key=itemgetter(1))
>>> l
[('p', 1), ('y', 2), ('t', 3), ('h', 4), ('o', 5), ('n', 6)]
```
`itemgetter`函数是最常用的函数(如果对象是字典，也是如此)，但有时你会发现它用于`attrgetter`和`methodcaller`，返回对象的属性和调用对象方法的结果，基于同样的目的。有关更多信息，请参见`operator`模块文档。
## 集合
列表是非常通用的工具，适合大多数容器对象应用程序。但是当我们想要确保列表中的对象是唯一的时，它们就没有用了。例如，歌曲库可能包含同一艺术家的许多歌曲。如果我们想整理歌曲库，列出所有艺术家的名单，在我们再次添加艺术家之前，我们必须核对一下，查看是否已经添加这个艺术家。
</b>
这是使用集合的场景。集合来自数学，它们代表一个无序的(通常)唯一的数字组。我们可以给集合重复加一个数字5次，但它只会在集合中出现一次。
</b>
在Python中，集合可以保存任何可哈希的对象，而不仅仅是数字。哈希对象和可以在字典中用作为键的对象是相同的；所以，列表和字典过时了。像数学集合一样，它们只能存储每个对象的一个副本。所以如果我们想创建一个歌曲艺术家列表，我们可以创建一个字符串名字集合，并简单地将它们添加到集合中。本示例以(歌曲、艺术家)元组列表开始并创建一个艺术家集合：
```
song_library = [("Phantom Of The Opera", "Sarah Brightman"),
("Knocking On Heaven's Door", "Guns N' Roses"),
("Captain Nemo", "Sarah Brightman"),
("Patterns In The Ivy", "Opeth"),
("November Rain", "Guns N' Roses"),
("Beautiful", "Sarah Brightman"),
("Mal's Song", "Vixy and Tony")]
artists = set()
for song, artist in song_library:
artists.add(artist)
print(artists)
```
空集没有内置语法，就像列表和字典一样；我们使用`set()`构造函数创建一个集合。然而，我们可以使用花括号（借用字典语法）创建一个集合，只要该集合包含值。如果我们用冒号来分隔成对的值，它就是一个字典，如`{“key”:
value '，' key2': 'value2'}`。如果我们用逗号分隔值，它就是一个集合，如`{'value '，' value2'}`。项目将通过`add`方法被添加到集合中。如果我们运行这个脚本，我们会看到该集合像广告一样工作：
```
{'Sarah Brightman', "Guns N' Roses", 'Vixy and Tony', 'Opeth'}
```
如果你注意到输出，你会注意到项目没有按照它们被添加到集合中的顺序被打印出来。像字典一样，集合是无序的。两者都使用基于哈希的底层数据结构来提高效率。因为集合是无序的，所以不能按索引查找项目。集合的主要目的就是把世界分成两组：“在集合中的东西”和“不在集合中的东西”。很容易检查一个项目是否在集合中或历遍一个集合，但是如果我们想要对它们进行排序，我们必须将集合转换为列表。下面显示了所有这三项活动：
```
>>> "Opeth" in artists
True
>>> for artist in artists:
... print("{} plays good music".format(artist))
...
Sarah Brightman plays good music
Guns N' Roses plays good music
Vixy and Tony play good music
Opeth plays good music
>>> alphabetical = list(artists)
>>> alphabetical.sort()
>>> alphabetical
["Guns N' Roses", 'Opeth', 'Sarah Brightman', 'Vixy and Tony']
```
虽然集合的主要*特征*是唯一性，但这不是它的主要*目的*。当两个或多个集合合并时，集合最有用。集合类型上的大多数方法可以在其他集合上操作，允许我们有效地合并或比较两个或更多集合中的项目。这些方法有奇怪的名字，因为他们使用与数学中相同的术语。我们将从三种方法开始，三种方法将返回相同的结果，不管哪个是调用集，哪个是被调用集。
</b>
`union`方法是最常见和最容易理解的。它将第二个集合设置为参数并返回一个新的集合，该集合包含两个集合中的任何一个集合的所有元素；如果一个元素同时存在于两个原始集合中，它当然只会在新集合中出现一次。`union`就像一个逻辑or运算，事实上，如果你不喜欢调用方法，`|`运算符可以在两个集合上使用来执行`union`操作。相反，交集方法接受第二个集合并返回一个新集合，该集合仅包含两个集合中都有的那些元素。这就像一个逻辑and运算，也可以使用&运算符代替。
</b>
最后，`symmetric_difference`方法告诉我们还剩下什么；它是一组对象，在一个集合或另一个集合中，但不是两者都有。下面的例子，通过比较我和我姐姐的歌曲库中的艺术家，说明了这些方法：
```
my_artists = {"Sarah Brightman", "Guns N' Roses",
"Opeth", "Vixy and Tony"}
auburns_artists = {"Nickelback", "Guns N' Roses",
"Savage Garden"}
print("All: {}".format(my_artists.union(auburns_artists)))
print("Both: {}".format(auburns_artists.intersection(my_artists)))
print("Either but not both: {}".format(
my_artists.symmetric_difference(auburns_artists)))
```
如果我们运行这段代码，我们会看到这三种方法与打印语句一样，建议这样做：
```
All: {'Sarah Brightman', "Guns N' Roses", 'Vixy and Tony',
'Savage Garden', 'Opeth', 'Nickelback'}
Both: {"Guns N' Roses"}
Either but not both: {'Savage Garden', 'Opeth', 'Nickelback',
'Sarah Brightman', 'Vixy and Tony'}
```
不管哪个集合调用另一个集合，这些方法都返回相同的结果。我们可以说 `my_artists.union(auburns_artists)` 或 `auburns_artists. union(my_artists)`，并获得相同的结果。也有返回不同结果的方法，这取决于谁是调用者和谁是参数。
</b>
这些方法包括`issubset`和`issuperset`，它们是反义词。两者都返回一个`bool`对象。如果调用集中的所有项也在作为参数传入的集合中，`issubset`返回True。如果作为传入参数的集合中的所有项都在调用集中，`issuperset`方法则返回True。因此，`s.issuebset(t)`和`t.ssueperset(s)`是相同的。他们都将返回True，如果t包含s的所有元素。
</b>
最后，`difference`方法返回调用集合中的、但不在作为参数传入的集合中的所有元素；这就像半个`symmetric_difference`方法。`difference`方法也可以用-运算符表示。接下来的代码说明了这些方法的作用:
```
my_artists = {"Sarah Brightman", "Guns N' Roses", "Opeth", "Vixy and Tony"} bands = {"Guns N' Roses", "Opeth"}
print("my_artists is to bands:")
print("issuperset: {}".format(my_artists.issuperset(bands)))
print("issubset: {}".format(my_artists.issubset(bands)))
print("difference: {}".format(my_artists.difference(bands)))
print("*"*20)
print("bands is to my_artists:")
print("issuperset: {}".format(bands.issuperset(my_artists)))
print("issubset: {}".format(bands.issubset(my_artists)))
print("difference: {}".format(bands.difference(my_artists)))
```
当从一个集合调用另外一个集合时，这些代码简单地打印出每个方法的响应。运行它会给出以下输出:
```
my_artists is to bands:
issuperset: True
issubset: False
difference: {'Sarah Brightman', 'Vixy and Tony'}
********************
bands is to my_artists:
issuperset: False
issubset: True
difference: set()
```
在第二种情况下，`difference`方法返回一个空集合，因为`band`中不存在的元素也不存在于`my_artists`。
</b>
`union`、`intersection`、`difference`方法都可以将多个集合视为参数；如我们所料，它们将创建一个对所有参数调用操作之后的集合。
</b>
集合上的方法清楚地表明这个集合可以在其他集合上可以执行的操作，所以它们不仅仅是容器。如果我们有两个不同的数据来源，并需要以某种方式快速合并它们，以确定数据在哪里重叠或不同，我们可以使用集合运算来有效地比较它们。或者如果我们收到的数据可能包含已经处理后的副本，我们可以使用集合来比较两者，并且只处理新数据。
</b>
最后，在使用`in`关键字检查成员资格方面，集合比列表更有效。如果在集合或列表使用 `value in container
`，如果容器存在一个等值元素，则返回True，否则返回False。但是，在列表中，它将查看容器中的每一个对象，而在集合中，它只是哈希这个值，然后检查会员资格。这意味着不管容器有多大，集合会在相同时间内找到值，但是当列表包含越来越多的值，列表就需要越来越长的时间来搜索一个值。
## 扩展内置类型
我们在第3章“当对象相似时”简单地讨论过，内置数据类型如何使用继承来进行扩展的。现在，我们将更详细地讨论何时我们应该这么做。
</b>
当我们有一个要添加功能的内置容器对象时，我们有两种选择。我们可以创建一个新对象，将容器保存为属性（组合），或者我们可以子类化内置对象并添加或修改方法来做我们想要的（继承）。
</b>
如果我们只想使用容器的功能存储一些对象，组合通常是最好的选择。这样，很容易将数据结构传递到其他方法，它们知道如何与之交互。但是如果我们想改变容器的实际工作方式，就需要使用继承。例如，如果我们想确保列表中的每一项都是恰好有5个字符的字符串，我们需要扩展列表并重写`append()`方法来引发无效输入的异常。我们还必须至少重写`__setitem__(self、index、value)`，列表中的一种特殊方法，每当我们使用`x[index] = "value"`语法，都会调用这个方法。`extend()`方法也需要调整。
</b>
是的，列表是对象。所有特殊的、看起来像非面向对象的语法，一直被用在访问列表或字典键，遍历容器上，类似的任务实际上是映射到底层面向对象范式的“语法糖”。我们可能会问Python的设计者为什么这样做。面向对象编程不总是更好吗？这个问题很容易回答。作为一名程序员，在下面的假设例子中，哪一个更容易阅读？哪一个需要更少的打字。
```
c = a + b
c = a.add(b)
l[0] = 5
l.setitem(0, 5)
d[key] = value
d.setitem(key, value)
for x in alist:
#do something with x
it = alist.iterator()
while it.has_next():
x = it.next()
#do something with x
```
高亮部分显示了面向对象的代码可能是什么样子（实际上，这些方法实际上以关联对象的特殊双下划线方法形式存在着)。Python程序员同意非面向对象语法更容易读和写。然而，前面所有的Python语法都映射到“语法糖”背后面向对象的方法。这些方法有特殊的名称（前后加双下划线）来提醒我们有更好的语法糖。然而，它给了我们重写这些行为的方法。例如，我们可以生成一个特殊的整数，当我们将两个整数相加时，该整数总是返回0：
```
class SillyInt(int):
def __add__(self, num):
return 0
```
诚然，这是一件极其奇怪的事情，但它完美地说明了面向对象的原则在起作用：
```
>>> a = SillyInt(1)
>>> b = SillyInt(2)
>>> a + b
0
```
`__add__`方法最棒的一点是，我们可以将它添加到任何我们写的类中，如果我们在该类的实例上使用+运算符，该方法将被调用。例如，字符串、元组和列表连接就是这样工作的。
</b>
所有的特殊方法都是如此。如果我们想在一个自定义对象`myobj`中使用`x`，我们提供 `__contains__`。如果我们想`myobj[i] = value` ，我们提供 `__setitem__` 方法，如果我们想使用`somethine = myobj[i]`，我们提供 `__getitem__` 。
</b>
列表类中有33种特殊方法。我们可以使用`dir`函数来查看所有内容:
```
>>> dir(list)
['__add__', '__class__', '__contains__', '__delattr__','__delitem__',
'__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__
getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__',
'__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__
new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__',
'__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__
subclasshook__', 'append', 'count', 'extend', 'index', 'insert', 'pop',
'remove', 'reverse', 'sort'
```
此外，如果我们需要关于这些方法如何工作的附加信息，我们可以使用`help`函数：
```
>>> help(list.__add__)
Help on wrapper_descriptor:
__add__(self, value, /)
Return self+value.
```
加号运算符将连接两个列表。我们没有空间讨论所有本书中可用的特殊功能，但现在你可以`dir`和`help`探索所有功能。官方在线 Python 参考(https://docs.python.org/3/)也有很多有用的信息。尤其专注`
collections`模块中讨论的抽象基类。
</b>
所以，回到我们何时使用组合或继承的早期观点：如果我们需要改变类中的任何方法——包括特殊的方法——我们当然需要使用继承。如果我们使用组合，我们将写一些方法进行验证或修改，然后调用者使用这些方法，但是没有什么可以阻止他们直接访问属性。他们可以在我们的列表中插入一个没有5个字符的项目，这可能会混淆列表中的其他方法。
</b>
通常，扩展内置数据类型的需求表明我们正在使用错误的数据类型。情况并非总是如此，但如果我们想扩展一个内置类型，我们应该仔细考虑是否有其他更合适的数据结构。
</b>
例如，考虑创建一个能记住键插入顺序的字典。一种方法是保留一个有序键列表，存储在`dict`的一个特殊派生子类中。然后我们可以重写`keys`、`values`、`__iter__`、`iterm`方法，按顺序返回所有内容。当然，我们还得覆盖`__setitem__`和`setdefault`以保持我们的列表是最新的。有可能是需要重写其他方法，以保持`dir(dict)`输出列表和字典一致（记住`clear`和`__delitem__`，以跟踪被移除的项目），但是在这个例子中我们不担心它们。
</b>
所以我们将扩展`dict`并添加一个有序键列表。微不足道，但是我们在哪里创建实际的列表？我们可以将它包含在`__init__`方法中，这很好，但是我们不能保证任何子类都会调用这个初始化方法。还记得我们在第2章“Python中的对象”讨论的`__new__`方法吗？我说它通常只在非常特殊的情况下有用。这就是其中一个特殊情况。我们知道`__new__`将被仅调用一次，我们可以一直在类的新实例上创建一个列表。记住这一点，这里是我们完整的排序词典：
```
from collections import KeysView, ItemsView, ValuesView
class DictSorted(dict):
def __new__(*args, **kwargs):
new_dict = dict.__new__(*args, **kwargs)
new_dict.ordered_keys = []
return new_dict
def __setitem__(self, key, value):
'''self[key] = value syntax'''
if key not in self.ordered_keys:
self.ordered_keys.append(key)
super().__setitem__(key, value)
def setdefault(self, key, value):
if key not in self.ordered_keys:
self.ordered_keys.append(key)
return super().setdefault(key, value)
def keys(self):
return KeysView(self)
def values(self):
return ValuesView(self)
def items(self):
return ItemsView(self)
def __iter__(self):
'''for x in self syntax'''
return self.ordered_keys.__iter__()
```
`__new__`方法创建一个新词典，然后在对象上面放一个空列表。我们不覆盖`__init__`，因为默认实现是有效的（实际上，只有当我们初始化一个空的字典排序对象时，这才是正确的，这是标准的行为。如果我们想`dict`构造函数支持能接受字典或元组列表的其他变体，我们需要修改 `__init__`来更新我们的已排序键列表）。两种设置项目的方法非常相似；它们都更新了键列表，但前提是之前没有添加该项目。我们不想列表存在重复，但是我们不能在这里使用集合；集合是无序的！
</b>
`keys`、`items`、`values`方法都将视图返回到字典中。collections库在字典上提供三个只读视图对象；它们使用 `__iter__`方法循环遍历键，然后使用`__getitem__`（我们不需要重写）来检索值。所以，我们只需要定义我们自定义`__iter__`方法使这三个视图工作。你可能想超类会使用多态正确地创建这些视图，但是如果我们不重写这三种方法，它们将不返回正确排序的视图。
</b>
最后，`__iter__`方法是真正特殊的方法；它确保如果我们循环字典的键（用`for ... in`语法），按正确的顺序返回键值。它通过返回ordered _ keys列表的`__iter__`来实现这一点，该列表返回一个迭代器对象，它和我们在列表上使用`for ... in `是一样的。因为`ordered _ keys`是所有可用键的列表（由于我们覆盖了其他方法），这也是字典的正确迭代器对象。
</b>
让我们来看看这些方法中的一些，并与普通字典进行比较:
```
>>> ds = DictSorted()
>>> d = {}
>>> ds['a'] = 1
>>> ds['b'] = 2
>>> ds.setdefault('c', 3)
3
>>> d['a'] = 1
>>> d['b'] = 2
>>> d.setdefault('c', 3)
3
>>> for k,v in ds.items():
... print(k,v)
...
a 1
b 2
c 3
>>> for k,v in d.items():
... print(k,v)
...
a 1
c 3
b 2
```
啊，我们的字典分类了，而普通的字典没有。开心！
> 如果你想在生产中使用这个类，你必须重写其他几种特殊的方法使得键在所有的实例中是最新的。但是，你不需要这样做；这个类的功能已在Python中提供，使用`collections`模块中的`OrderedDict`对象。尝试从`collections`中导入类，并使用`help(OrderedDict)`了解更多信息。
## 队列
队列是特殊的数据结构，因为像集合一样，它们的功能可以完全用列表来处理。然而，尽管列表是用途极其广泛的通用工具，对于容器操作，它们有时不是最有效的数据结构。如果你的程序使用的是小数据集（多达数百甚至更多
当今处理器上的数千个元素），那么列表可能会覆盖你的用例。但是，如果你需要将数据扩展到数百万，您可能需要一个更有效的容器来满足你的特定用例。因此，Python提供了三个队列数据结构的类型，取决于你正在寻找的访问类型。三者都使用相同的API，但是行为和数据结构都不同。
</b>
然而，在我们开始使用队列之前，先考虑列表数据结构。Python列表是许多用例中是最有利的数据结构：
* 它们支持对列表中任何元素的高效随机访问
* 它们有严格的元素排序
* 它们高效地支持追加操作
但是，如果你要在任何地方插入元素，而不是在列表尾部（尤其是如果在列表开头插入），列表会变慢。正如我们在上一节集合中讨论的那样，它们检查列表中是否存在某元素的速度也很慢，还有搜索也是一样。按照排序的顺序存储数据或对数据重新排序也是很低效率的。
</b>
让我们看看Python队列模块提供的三种类型的容器。
### FIFO队列
FIFO代表先进先出，代表“队列”定义最普遍的理解。想象一行人在银行或收银机排队。第一个进入队伍的人首先得到服务，第二个进入队伍的人接着得到服务，如果一个新人想要获得服务，他们得加入排队等候轮到他们。
</b>
Python`Queue`类就是这样。它通常被用作一种通信媒介，当一个或多个对象产生数据而一个或多个其他对象以某种方式消耗这些数据，可能速度不同。想想一个消息应用，它从网络接收消息，但每次只能给用户显示一条消息。其他消息可以按接收顺序缓冲在队列中。FIFO队列在这种并发应用中被大量使用。（我们将在第12章“测试面向对象的程序”中详细讨论并发性。)
</b>
当你不需要访问任何数据结构的任何数据时，除下要访问下一个要消费的对象之外，`Queue`类是一个很好的选择。为此使用列表是效率较低的，因为如果在列表的开头插入数据（或移除数据），需要历遍列表中的每一个元素。
</b>
队列有一个非常简单的API。`Queue`可以有“无限”（直到计算机内存不足）的容量，但是它通常被限制在某个最大值。主要方法是`put()`和`get()`，它们将元素添加到的后面，就像排队，然后从前面依次把它们拿回来。这两种方法接受可选参数来控制如果操作没有完成会发生什么，因为队列要么是空的（无法获取），要么就是满的（无法加入）。默认值行为是阻塞或无所事事地等待，直到队列对象有可用的数据或空间来继续进行。你也可以抛出异常，代替传递`block=False`参数。或者你可以在引发异常之前让它等一段时间，通过传递一个超时`timeout`参数。
</b>
该类还具有检查队列是满`full()` 或空`empty()`的方法，并且有几个额外的方法来处理并发访问，我们不会在这里讨论。以下是演示这些原则的互动会议：
```
>>> from queue import Queue
>>> lineup = Queue(maxsize=3)
>>> lineup.get(block=False)
Traceback (most recent call last):
File "<ipython-input-5-a1c8d8492c59>", line 1, in <module>
lineup.get(block=False)
File "/usr/lib64/python3.3/queue.py", line 164, in get
raise Empty
queue.Empty
>>> lineup.put("one")
>>> lineup.put("two")
>>> lineup.put("three")
>>> lineup.put("four", timeout=1)
Traceback (most recent call last):
File "<ipython-input-9-4b9db399883d>", line 1, in <module>
lineup.put("four", timeout=1)
File "/usr/lib64/python3.3/queue.py", line 144, in put
raise Full
queue.Full
>>> lineup.full()
True
>>> lineup.get()
'one'
>>> lineup.get()
'two'
>>> lineup.get()
'three'
>>> lineup.empty()
True
```
在语法糖之下，Python使用`collections.deque`数据结构实现队列。Deques是高级数据结构，允许有效访问集合的两端。它提供了比Queue更灵活的接口。如果你想用它做更多的实验，请参考Python文档。
### LIFO队列
LIFO后进先出队列更常被称为**堆栈**。想象一堆纸，你只能访问最上面的纸。你可以在最上面再放一张纸，使它成为新的最上面的纸，或者你可以把最上面的纸拿开，露出下面的那张。
</b>
传统上，栈上的操作被命名为推送和弹出，但是Python队列模块使用与FIFO队列完全相同的应用编程接口：`put()`和`get()`。然而，在LIFO队列中，这些方法在堆栈的“顶部”操作，而不是在队列的前面和后面。这是多态性的一个很好的例子。如果你看看Python标准库中的队列源代码，你会发现有一个超类包含FIFO和LIFO队列的子类，两个子类在少数关键操作非常不同的（LIFO在堆栈顶部操作，FIFO在deque实例的前面和后面操作）。
</b>
下面是LIFO队列的一个例子：
```
>>> from queue import LifoQueue
>>> stack = LifoQueue(maxsize=3)
>>> stack.put("one")
>>> stack.put("two")
>>> stack.put("three")
>>> stack.put("four", block=False)
Traceback (most recent call last):
File "<ipython-input-21-5473b359e5a8>", line 1, in <module>
stack.put("four", block=False)
File "/usr/lib64/python3.3/queue.py", line 133, in put
raise Full
queue.Full
>>> stack.get()
'three'
>>> stack.get()
'two'
>>> stack.get()
'one'
>>> stack.empty()
True
>>> stack.get(timeout=1)
Traceback (most recent call last):
File "<ipython-input-26-28e084a84a10>", line 1, in <module>
stack.get(timeout=1)
File "/usr/lib64/python3.3/queue.py", line 175, in get
raise Empty
queue.Empty
```
你可能想知道为什么不能标准列表使用`append()`和`pop() `。坦白地说，那可能是我会做的。我很少有机会在生产代码中使用`LifoQueue`类。处理列表的末尾是一个有效操作；事实上，列表如此有效，以至于`LifoQueue`队列是建在列表之上的！
</b>
你可能更希望使用`LifoQueue`而不是列表。最重要的一点是`LifoQueue`支持干净的来自多个线程并发访问。如果在并发设置中你需要类似堆栈的行为，你应该把列表留在家里。其次，`LifoQueue`强制实施堆栈接口。你不会无意中将值插入`LifoQueue`队列中的错误位置，例如（尽管，作为一个练习，你可以完全有意识地想出如何做到这一点）。
### 优先级队列
优先级队列实施了与之前队列非常不同的排序方式。同样，它们遵循完全相同的`get()`和`put()`API，但是不是依赖物品到达的顺序来决定它们应该在什么时候返回，而是返回最“重要”的项目。按照惯例，最重要的是，或者最高优先级项目是使用小于运算符排序的最低项目。
</b>
一个常见的约定是在优先级队列中存储元组，其中元组中第一个元素是该元素的优先级，第二个元素是数据。另一个常见的范例是实现`__lt__`方法，正如我们在这章前面讨论的那样。在队列中具有相同优先级的多个元素是完全可以接受的，尽管不能保证哪一个会先返回。
</b>
例如，搜索引擎在爬取最不可能被搜索到的网站之前，可以使用优先级队列来确保它获得最流行网页的最新内容。产品推荐工具可以使用它来显示信息关于排名最高的产品，同时仍然加载排名较低的数据。
</b>
请注意，优先级队列将始终返回当前队列最重要的元素。如果队列为空，`get()`方法将阻塞（默认情况下)，但如果队列中有元素，它将不会阻塞并等待更高优先级的元素被添加。队列对没有被添加的元素一无所知（或者甚至是先前已经被提取的元素），而仅根据队列的当前内容做出决定。
</b>
下面交互式会话显示了正在运行的优先级队列，使用元组作为权重确定处理项目的顺序：
```
>>> heap.put((3, "three"))
>>> heap.put((4, "four"))
>>> heap.put((1, "one") )
>>> heap.put((2, "two"))
>>> heap.put((5, "five"), block=False)
Traceback (most recent call last):
File "<ipython-input-23-d4209db364ed>", line 1, in <module>
heap.put((5, "five"), block=False)
File "/usr/lib64/python3.3/queue.py", line 133, in put
raise Full
Full
>>> while not heap.empty():
print(heap.get())
(1, 'one')
(2, 'two')
(3, 'three')
(4, 'four')
```
优先级队列几乎普遍使用堆数据结构来实现。Python的实现利用`heapq`模块有效地在普通列表内部存储堆。你可以看有关堆的算法和数据结构的教科书，以获得更多的信息，我们将不再这里提及其他迷人的结构了。不管数据结构是什么，都可以使用面向对象的原则包装相关的算法（行为），例如`heapq`模块中提供的算法，围绕着它们在计算机内存中构建的数据，就像`queue`模块已经代表我们在标准库中完成了的工作。`
## 个案研究
为了将所有东西联系在一起，我们将编写一个简单的链接收集器，它将访问一个网站，并收集它在该网站中存在的每个页面上的每个链接。在我们开始之前，不过，我们需要一些测试数据来处理。只需编写一些超文本标记语言文件要使用彼此之间以及到互联网上其他站点容器链接，像这样:
```
<html>
<body>
<a href="contact.html">Contact us</a>
<a href="blog.html">Blog</a>
<a href="esme.html">My Dog</a>
<a href="/hobbies.html">Some hobbies</a>
<a href="/contact.html">Contact AGAIN</a>
<a href="http://www.archlinux.org/">Favorite OS</a>
</body>
</html>
```
说出index.html文件中的一个，这样当页面被提供时它会首先出现。
确保其他文件存在，并保持事情的复杂性，以便有很多
他们之间的联系。本章的例子包括一个名为
case_study_serve(现存最烂的个人网站之一！)如果你
我宁愿不自己设计。
现在，通过输入包含所有这些内容的目录来启动一个简单的网络服务器
文件并运行以下命令:
```
python3 -m http.server
```
这将启动在端口8000上运行的服务器；你可以看到你制作的页面
请访问您的web浏览器中的http://localhost:8000/。
> 我怀疑任何人都可以用更少的工作建立并运行一个网站！
永远不要让别人说，“你不能用蟒蛇轻易做到这一点。”
目标是向我们的收集器传递该站点的基本网址(在这种情况下:http://
localhost:8000/)，并让它创建一个包含站点上每个唯一链接的列表。
我们需要考虑三种类型的网址(链接到外部网站
以http://开头，绝对内部链接，以/字符开头，和
相对联系，对于其他一切)。我们还需要注意页面可能链接到
彼此循环；我们需要确保我们不会多次处理同一个页面
时代，否则它可能永远不会结束。随着所有这些独特性的继续，听起来我们
需要一些器械包。
在开始之前，让我们先从基础开始。我们需要连接什么代码
并解析该页面中的所有链接？
```
from urllib.request import urlopen
from urllib.parse import urlparse
import re
import sys
LINK_REGEX = re.compile(
"<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>")
class LinkCollector:
def __init__(self, url):
self.url = "" + urlparse(url).netloc
def collect_links(self, path="/"):
full_url = self.url + path
page = str(urlopen(full_url).read())
links = LINK_REGEX.findall(page)
print(links)
if __name__ == "__main__":
LinkCollector(sys.argv[1]).collect_links()
```
考虑到它在做什么，这是一小段代码。它连接到中的服务器
命令行上传递的参数下载页面，并提取所有
页面上的链接。__init__方法使用urlparse函数仅提取
网址中的主机名；所以即使我们传入http://localhost:8000/some/page。
html，它仍将运行在主机的顶层http://localhost:8000/。这
有道理，因为我们想收集网站上的所有链接，尽管它假设
每一页都通过一些链接序列连接到索引。
collect_links方法连接到指定页面并从其下载
服务器，并使用正则表达式查找页面中的所有链接。常规
表达式是一个非常强大的字符串处理工具。不幸的是，他们
学习曲线陡峭；如果你以前没有用过，我强烈推荐
研究关于这个主题的所有书籍或网站。如果你不认为他们
值得知道的是，尝试在没有它们的情况下编写前面的代码，你将会改变
你的思想。
该示例还在collect_links方法的中间停止打印值
链接。这是我们编写程序时测试程序的一种常见方式:停止并输出
确保它是我们期望的价值。以下是它为我们的示例输出的内容:
```
['contact.html', 'blog.html', 'esme.html', '/hobbies.html',
'/contact.html', 'http://www.archlinux.org/']
```
现在我们在第一页收集了所有的链接。我们能做什么
是吗？我们不能只将链接放入一个集合中来删除重复项，因为链接可能
相对的或绝对的。例如，contact.html和/contact.html指向
同一页。所以我们应该做的第一件事是将所有链接规范化到它们的完整网址，
包括主机名和相对路径。我们可以通过添加一个规范化的网址来做到这一点
方法到我们的对象:
```
def normalize_url(self, path, link):
if link.startswith("http://"):
return link
elif link.startswith("/"):
return self.url + link
else:
return self.url + path.rpartition(
'/')[0] + '/' + link
```
此方法将每个网址转换为一个完整的地址，其中包括协议和
主机名。现在，两个联系人页面具有相同的值，我们可以存储它们
一套。我们必须修改__init__来创建集合，并收集_链接来放置
所有的链接。
然后，我们将不得不访问所有非外部链接并收集它们。但是等等
分钟；如果我们这样做，当我们遇到
同一页两次？看起来我们实际上需要两套:一套收集的
链接和一组访问过的链接。这表明我们明智地选择了一套
代表我们的数据；我们知道当我们操作的时候布景是最有用的
不止一个。让我们设置这些:
```
class LinkCollector:
def __init__(self, url):
self.url = "http://+" + urlparse(url).netloc
self.collected_links = set()
self.visited_links = set()
def collect_links(self, path="/"):
full_url = self.url + path
self.visited_links.add(full_url)
page = str(urlopen(full_url).read())
links = LINK_REGEX.findall(page)
links = {self.normalize_url(path, link
) for link in links}
self.collected_links = links.union(
self.collected_links)
unvisited_links = links.difference(
self.visited_links)
print(links, self.visited_links,
self.collected_links, unvisited_links)
```
创建规范化链接列表的行使用集合理解，否
不同于列表理解，除了结果是一组值。我们会的
下一章将详细介绍这些内容。该方法再次停止打印
当前的值，所以我们可以验证我们没有混淆我们的集合，并且
不同的是我们想要调用的收集未访问链接的方法。
然后我们可以添加几行代码，循环遍历所有未访问的链接，并添加
他们也来收藏:
```
for link in unvisited_links:
if link.startswith(self.url):
self.collect_links(urlparse(link).path)
```
if声明确保我们只从一个网站收集链接；我们
我不想离开并收集互联网上所有页面的所有链接(除非
我们是谷歌或互联网档案馆！)。如果我们修改
程序输出收集到的链接，我们可以看到它似乎已经收集了所有链接:
```
if __name__ == "__main__":
collector = LinkCollector(sys.argv[1])
collector.collect_links()
for link in collector.collected_links:
print(link)
```
它显示我们收集到的所有链接，而且只显示一次，尽管
我的示例中的页面相互链接了多次:
```
$ python3 link_collector.py http://localhost:8000
http://localhost:8000/
http://en.wikipedia.org/wiki/Cavalier_King_Charles_Spaniel
http://beluminousyoga.com
http://archlinux.me/dusty/
http://localhost:8000/blog.html
http://ccphillips.net/
http://localhost:8000/contact.html
http://localhost:8000/taichi.html
http://www.archlinux.org/
http://localhost:8000/esme.html
http://localhost:8000/hobbies.html
```
即使它收集到外部页面的链接，它也不会从任何页面收集链接
我们链接的外部页面。如果我们想收集，这是一个很棒的小程序
网站中的所有链接。但是它并没有给我构建一个
站点地图；它会告诉我我有哪些页面，但不会告诉我哪些页面链接到其他页面
页数。如果我们想这样做，我们就必须做一些修改。
我们应该做的第一件事是查看我们的数据结构。收集的链接集
已经不起作用了；我们想知道哪些链接与哪些链接相关联
页数。那么，我们能做的第一件事就是把这个集合变成一个集合字典
我们浏览的每一页。字典键将代表完全相同的数据
目前在片场。这些值将是该页面上所有链接的集合。这是
变化:
```
from urllib.request import urlopen
from urllib.parse import urlparse
import re
import sys
LINK_REGEX = re.compile(
"<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>")
class LinkCollector:
def __init__(self, url):
self.url = "http://%s" % urlparse(url).netloc
self.collected_links = {}
self.visited_links = set()
def collect_links(self, path="/"):
full_url = self.url + path
self.visited_links.add(full_url)
page = str(urlopen(full_url).read())
links = LINK_REGEX.findall(page)
links = {self.normalize_url(path, link
) for link in links}
self.collected_links[full_url] = links
for link in links:
self.collected_links.setdefault(link, set())
unvisited_links = links.difference(
self.visited_links)
for link in unvisited_links:
if link.startswith(self.url):
self.collect_links(urlparse(link).path)
def normalize_url(self, path, link):
if link.startswith("http://"):
return link
elif link.startswith("/"):
return self.url + link
else:
return self.url + path.rpartition('/'
)[0] + '/' + link
if __name__ == "__main__":
collector = LinkCollector(sys.argv[1])
collector.collect_links()
for link, item in collector.collected_links.items():
print("{}: {}".format(link, item))
```
这是一个惊人的小变化；最初创建两组并集的线具有
替换为更新字典的三行。第一个简单地告诉我们
字典为那一页收集的链接是什么。第二个创建一个空的
为字典中尚未添加到字典中的任何项目设置，
使用setdefault。结果是一个包含所有链接作为关键字的字典，
映射到所有内部链接的链接集，以及外部链接的空集。
最后，我们可以使用队列来存储，而不是递归调用collect_links
尚未处理的链接。这个实现不支持它，
但是这将是创建多线程版本的良好的第一步
并行处理多个请求以节省时间。
```
from urllib.request import urlopen
from urllib.parse import urlparse
import re
import sys
from queue import Queue
LINK_REGEX = re.compile("<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>")
class LinkCollector:
def __init__(self, url):
self.url = "http://%s" % urlparse(url).netloc
self.collected_links = {}
self.visited_links = set()
def collect_links(self):
queue = Queue()
queue.put(self.url)
while not queue.empty():
url = queue.get().rstrip('/')
self.visited_links.add(url)
page = str(urlopen(url).read())
links = LINK_REGEX.findall(page)
links = {
self.normalize_url(urlparse(url).path, link)
for link in links
}
self.collected_links[url] = links
for link in links:
self.collected_links.setdefault(link, set())
unvisited_links = links.difference(self.visited_links)
for link in unvisited_links:
if link.startswith(self.url):
queue.put(link)
def normalize_url(self, path, link):
if link.startswith("http://"):
return link.rstrip('/')
elif link.startswith("/"):
return self.url + link.rstrip('/')
else:
return self.url + path.rpartition('/')[0] + '/' + link.
rstrip('/')
if __name__ == "__main__":
collector = LinkCollector(sys.argv[1])
collector.collect_links()
for link, item in collector.collected_links.items():
print("%s: %s" % (link, item))
```
我不得不手动删除normalize_url方法中的任何尾随斜杠
删除此版本代码中的重复项。
因为最终结果是一个未排序的字典，所以对顺序没有限制
链接应该在中处理。因此，我们可以很容易地使用
这里是一个后进先出队列，而不是队列。优先级队列可能不会
很有意义，因为在这种情况下，没有明显的优先级赋予链接。
## 摘要
我们已经讨论了几个内置的数据结构，并试图理解如何
为特定应用选择一个。有时候，我们能做的最好的事情就是创建一个
新的对象类，但通常，其中一个内置对象正好提供了我们需要的东西。
如果没有，我们总是可以使用继承或组合来使它们适应我们的
用例。我们甚至可以覆盖特殊方法来完全改变行为
内置语法。
在下一章中，我们将讨论如何集成Python的面向对象和非面向对象方面。一路上，我们会发现它更面向对象
比第一眼看到的还多！
