Skip to content

Latest commit

 

History

History
1195 lines (869 loc) · 74.6 KB

06.md

File metadata and controls

1195 lines (869 loc) · 74.6 KB
Raw

六、Python 数据结构

到目前为止，在我们的示例中，我们已经看到许多内置 Python 数据结构正在运行。您可能也在介绍性书籍或教程中介绍了其中的许多内容。在本章中，我们将讨论这些数据结构的面向对象特性，何时应该使用它们来代替常规类，何时不应该使用它们。我们将特别介绍：

  • 元组和命名元组
  • 辞典
  • 列表和集合
  • 如何以及为什么扩展内置对象
  • 三种类型的队列

空对象

让我们从最基本的内置 Python 开始，我们已经见过很多次了，我们在创建的每个类中都扩展了它：object。从技术上讲，我们可以实例化一个object而无需编写子类：

>>> o = object()
>>> o.x = 5
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
AttributeError: 'object' object has no attribute 'x'

不幸的是，正如您所看到的，无法在直接实例化的object上设置任何属性。这并不是因为 Python 开发人员想强迫我们编写自己的类，或者任何如此险恶的东西。他们这样做是为了节省内存；很多记忆。当 Python 允许对象具有任意属性时，它需要一定数量的系统内存来跟踪每个对象具有哪些属性，以存储属性名称及其值。即使没有存储任何属性，也会为潜在新属性分配内存。给定典型 Python 程序中的几十个、数百个或数千个对象（每个类都扩展对象）；这少量内存将很快变成大量内存。因此，Python 在默认情况下禁用了object和其他几个内置的任意属性。

注

可以使用插槽在我们自己的类上限制任意属性。插槽超出了本书的范围，但如果您要查找更多信息，您现在有了一个搜索词。在正常使用中，使用插槽没有多大好处，但如果您正在编写一个对象，该对象将在整个系统中被复制数千次，它们可以帮助节省内存，就像它们在object中所做的一样。

然而，创建我们自己的空对象类是微不足道的；我们在最早的例子中看到：

class MyObject:
    pass

而且，正如我们已经看到的，可以在这些类上设置属性：

>>> m = MyObject()
>>> m.x = "hello"
>>> m.x
'hello'

如果我们想将属性分组在一起，我们可以将它们存储在这样一个空对象中。但我们通常最好使用其他设计用于存储数据的内置组件。本书始终强调，类和对象只能在您希望同时指定数据和行为时使用。编写一个空类的主要原因是为了快速阻止某些内容，因为我们知道稍后会回来添加行为。使行为适应类比用对象替换数据结构并更改对它的所有引用要容易得多。因此，重要的是从一开始就确定数据是否只是数据，还是伪装的对象。一旦做出了设计决策，设计的其余部分自然就会到位。

元组和命名元组

元组是对象，可以按顺序存储特定数量的其他对象。它们是不可变的，因此我们不能动态添加、删除或替换对象。这似乎是一个巨大的限制，但事实是，如果需要修改元组，则使用了错误的数据类型（通常列表更合适）。元组不变性的主要好处是，我们可以将它们用作字典中的键，以及对象需要哈希值的其他位置中的键。

元组用于存储数据；行为不能存储在元组中。如果我们需要行为来操作元组，我们必须将元组传递给执行该操作的函数（或另一个对象上的方法）。

元组通常应该存储彼此不同的值。例如，我们不会将三个股票符号放在一个元组中，但我们可能会创建一个股票符号、当前价格、当天的高点和低点的元组。元组的主要用途是将不同的数据片段聚合到一个容器中。因此，元组可以是替换“没有数据的对象”习惯用法的最简单工具。

我们可以通过用逗号分隔值来创建元组。通常，元组被包装在括号中，以便于阅读，并将它们与表达式的其他部分分开，但这并不总是强制性的。以下两项任务是相同的（它们记录了一家相当盈利的公司的股票、当前价格、高点和低点）：

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

元组直接在函数调用内部创建，方法是使用逗号分隔值并将整个元组括在括号中。然后，这个元组后面跟一个逗号，将其与第二个参数分开。

此示例还演示了元组解包。函数中的第一行将stock参数解压为四个不同的变量。元组的长度必须与变量的数量完全相同，否则将引发异常。我们还可以在最后一行看到一个元组解包的示例，其中函数中返回的元组被解包为两个值，mid_value和date。当然，这是一件奇怪的事情，因为我们首先提供了函数的日期，但它给了我们一个在工作中看到解包的机会。

解包是 Python 中非常有用的特性。我们可以将变量组合在一起，使存储和传递变得更简单，但是当我们需要访问所有变量时，我们可以将它们解压成单独的变量。当然，有时我们只需要访问元组中的一个变量。我们可以使用与其他序列类型（例如列表和字符串）相同的语法来访问单个值：

>>> stock = "FB", 75.00, 75.03, 74.90
>>> high = stock[2]
>>> high
75.03

我们甚至可以使用切片表示法提取较大的元组片段：

>>> stock[1:3]
(75.00, 75.03)

这些示例说明了元组的灵活性，同时也说明了它们的一个主要缺点：可读性。阅读此代码的人如何知道特定元组的第二个位置是什么？他们可以根据我们分配给它的变量的名称猜测它是某种类型的high，但是如果我们在计算中刚刚访问了元组值而没有分配它，就不会有这样的指示。在发现元组的作用之前，他们必须仔细检查代码以找到元组声明的位置。

在某些情况下，直接访问元组成员是可以的，但不要养成习惯。这种所谓的“神奇数字”（似乎是凭空而来的数字，在代码中没有明显的意义）是许多编码错误的根源，并导致数小时的调试失败。只有当您知道所有的值都将同时有用并且通常在访问时会被解包时，才尝试使用元组。如果您必须直接或使用切片访问某个成员，并且该值的用途不是很明显，那么至少要包含一条注释，解释该值的来源。

命名元组

那么，当我们想要将值分组在一起，但知道我们经常需要单独访问它们时，我们该怎么做？好的，我们可以使用一个空对象，如前一节所讨论的（但除非我们预期以后会添加行为，否则这很少有用），或者我们可以使用字典（如果我们不知道将存储多少或哪些特定数据，那么最有用），我们将在下一节中介绍。

但是，如果我们不需要向对象添加行为，并且我们事先知道需要存储哪些属性，那么我们可以使用命名元组。命名元组是带有态度的元组。它们是将只读数据分组在一起的好方法。

构造命名元组比构造普通元组需要更多的工作。首先，我们必须导入namedtuple，因为默认情况下它不在名称空间中。然后，我们通过给命名元组命名并概述其属性来描述它。这将返回一个类似类的对象，我们可以使用所需的值多次实例化该对象：

from collections import namedtuple
Stock = namedtuple("Stock", "symbol current high low")
stock = Stock("FB", 75.00, high=75.03, low=74.90)

namedtuple构造函数接受两个参数。第一个是命名元组的标识符。第二个是命名元组可以具有的一组空格分隔属性。应该列出第一个属性，后跟一个空格（或逗号，如果您愿意），然后是第二个属性，然后是另一个空格，依此类推。结果是一个对象，可以像普通类一样调用它来实例化其他对象。构造函数必须具有正确数量的参数，这些参数可以作为参数或关键字参数传入。与普通对象一样，我们可以创建任意多个该“类”的实例，每个实例都有不同的值。

由此产生的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__属性）。甚至模块上的属性也在内部存储在字典中。

给定映射到某个值的特定键对象，字典在查找该值时非常有效。当您希望基于其他对象查找一个对象时，应始终使用它们。正在存储的对象称为值；用作索引的对象称为键。我们已经在前面的一些示例中看到了字典语法。

可以使用dict()构造函数或{}语法快捷方式创建字典。实际上，几乎总是使用后一种格式。我们可以通过使用冒号分隔键和值，并使用逗号分隔键值对来预填充字典。

例如，在股票应用程序中，我们通常希望通过股票符号查找价格。我们可以创建一个字典，使用股票符号作为键，使用当前、高和低的元组作为值，如下所示：

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返回默认值并在字典中为我们设置新值。然后我们检查新股票是否确实在字典中。

另外三种非常有用的字典方法是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（我们可以使用我们想要的任何变量名称，但这两个名称似乎都合适），然后以格式化字符串的形式打印出来。

请注意，股票的显示顺序与插入股票的顺序不同。字典，由于高效的算法（称为散列），用于使密钥查找如此快速，本质上是未排序的。

因此，一旦字典被实例化，就有很多方法可以从字典中检索数据；我们可以使用方括号作为索引语法，get方法、setdefault方法或迭代items方法等。

最后，您可能已经知道，我们可以使用检索值时使用的相同索引语法在字典中设置值：

>>> stocks["GOOG"] = (597.63, 610.00, 596.28)
>>> stocks['GOOG']
(597.63, 610.0, 596.28)

今天谷歌的价格更低，所以我更新了字典中的元组值。我们可以使用此索引语法为任何键设置一个值，而不管该键是否在字典中。如果在字典中，旧值将替换为新值；否则，将创建一个新的键/值对。

到目前为止，我们一直使用字符串作为字典键，但并不局限于字符串键。使用字符串作为键是很常见的，尤其是当我们将数据存储在字典中以将其聚集在一起时（而不是使用具有命名属性的对象）。但我们也可以使用元组、数字，甚至是我们定义为字典键的对象。我们甚至可以在一本字典中使用不同类型的键：

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

这段代码显示了我们可以提供给字典的几种不同类型的键。它还显示了一种无法使用的对象类型。我们已经广泛使用了列表，我们将在下一节中看到更多关于它们的详细信息。因为列表可以随时更改（例如，通过添加或删除项），所以它们不能散列为特定值。

可散列的对象基本上有一个已定义的算法，可以将对象转换为唯一的整数值，以便快速查找。这个散列实际上是用来在字典中查找值的。例如，字符串根据字符串中的字符映射为整数，而元组组合元组中项目的哈希。任何被认为相等的两个对象（如具有相同字符的字符串或具有相同值的元组）都应该具有相同的哈希值，并且对象的哈希值永远不会更改。但是，列表可以更改其内容，这将更改其哈希值（只有当两个列表的内容相同时，两个列表才应该相等）。因此，它们不能用作字典键。出于同样的原因，字典不能用作其他字典的键。

相反，可以用作字典值的对象类型没有限制。例如，我们可以使用映射到列表值的字符串键，或者我们可以将嵌套的字典作为另一个字典中的值。

字典用例

词典用途广泛，用途广泛。使用词典有两种主要方式。第一种是字典，其中所有键表示相似对象的不同实例；例如，我们的股票字典。这是一个索引系统。我们使用股票符号作为价值的索引。这些值甚至可以是复杂的自定义对象，用于做出买卖决策或设置止损，而不是我们的简单元组。

第二种设计是字典，其中每个键代表单个结构的某些方面；在这种情况下，我们可能会为每个对象使用一个单独的字典，它们都有相似（尽管通常不完全相同）的键集。后一种情况通常也可以用命名元组解决。当我们确切地知道数据必须存储哪些属性，并且我们知道必须一次提供所有数据片段（当构建项时）时，通常应该使用这些属性。但是如果我们需要随着时间的推移创建或更改字典键，或者我们不知道这些键可能是什么，那么字典更合适。

使用 defaultdict

我们已经了解了如何在键不存在时使用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接受其构造函数中的函数。每当访问字典中不存在的键时，它都会调用该函数（不带参数）以创建默认值。

在本例中，它调用的函数是int，它是整数对象的构造函数。通常，只需在代码中键入一个整数即可创建整数，如果我们确实使用int构造函数创建了一个整数，我们会将要创建的项传递给它（例如，将一串数字转换为整数）。但是如果我们不带任何参数调用int，它会很方便地返回数字零。在此代码中，如果该字母在defaultdict中不存在，则在访问该字母时返回数字零。然后我们在这个数字上加上一个，表示我们已经找到了这个字母的一个实例，下次我们找到一个实例时，这个数字将被返回，我们可以再次增加这个值。

defaultdict用于创建容器的字典。如果我们想创建过去 30 天的股价字典，我们可以使用股票符号作为键，并将价格存储在list中；第一次访问股票价格时，我们希望它创建一个空列表。只需将list传入defaultdict，每次访问空密钥时都会调用它。如果我们想将一个字典与一个键相关联，我们可以对集合甚至空字典执行类似的操作。

当然，我们也可以编写自己的函数并将它们传递到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)简单得多，但“我想在一个 iterable 中计算特定实例”用例非常常见，Python 开发人员为此创建了一个特定的类。前面计算字符串中字符数的代码可以在一行中轻松计算：

from collections import Counter
def letter_frequency(sentence):
    return Counter(sentence)

Counter对象的行为类似于一个增强的字典，其中键是要计数的项目，值是这些项目的数量。最有用的函数之一是most_common()方法。它返回按计数排序的（key，count）元组列表。您可以选择将整数参数传递到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 中的列表是简单可用的。我们不需要导入它们，也很少需要对它们调用方法。我们可以在列表上循环，而无需显式地请求迭代器对象，并且可以使用自定义语法构造列表（就像使用字典一样）。此外，列表理解和生成器表达式将它们转化为名副其实的瑞士军刀计算功能。

我们不会对语法进行太多的详细介绍；您已经在网上的入门教程和本书前面的示例中看到了它。如果不学习如何使用列表，就无法编写很长时间的 Python 代码！相反，我们将讨论何时应该使用列表，以及它们作为对象的性质。如果您不知道如何创建或附加到列表，如何从列表中检索项目，或者“切片表示法”是什么，我将指导您阅读官方 Python 教程 post haste。可在网上找到 http://docs.python.org/3/tutorial/ 。

在 Python 中，当我们想要存储“相同”类型对象的多个实例时，通常应该使用列表；字符串列表或数字列表；大多数情况下，我们自己定义的对象列表。当我们想要以某种顺序存储项目时，应该始终使用列表。通常，这是插入它们的顺序，但它们也可以按某些标准排序。

正如我们在上一章的案例研究中所看到的，当我们需要修改内容时，列表也非常有用：在列表的任意位置插入或删除，或者更新列表中的值。

与字典一样，Python 列表使用了非常高效且经过良好调整的内部数据结构，因此我们可以担心存储的内容，而不是如何存储。许多面向对象的语言为队列、堆栈、链表和基于数组的列表提供了不同的数据结构。如果需要优化对大型数据集的访问，Python 确实提供了其中一些类的特殊实例。然而，通常情况下，列表数据结构可以同时满足所有这些目的，并且编码者可以完全控制他们如何访问它。

不要使用列表收集单个项目的不同属性。例如，我们不需要特定形状的属性列表。元组、命名元组、字典和对象都更适合于此目的。在某些语言中，他们可能会创建一个列表，其中每个备用项都是不同的类型；例如，他们可能会为我们的信件频率列表写['a', 1, 'b', 3]。他们必须使用一个奇怪的循环来同时访问列表中的两个元素，或者使用一个模数运算符来确定访问的位置。

不要在 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属性按顺序提供所有字母（小写和大写）的字符串。我们将其转换为一个列表，然后使用列表连接（加号运算符使两个列表合并为一个）添加一个字符，即空格。这些是频率列表中可用的字符（如果我们尝试添加列表中不存在的字母，代码将中断，但异常处理程序可以解决此问题）。

函数中的第一行使用列表理解将CHARACTERS列表转换为元组列表。列表理解是 Python 中一个重要的、非面向对象的工具；我们将在下一章详细介绍它们。

然后我们在句子中的每个字符上循环和。我们首先在CHARACTERS列表中查找角色的索引，我们知道它在频率列表中具有相同的索引，因为我们刚刚从第一个列表创建了第二个列表。然后，我们通过创建一个新元组来更新频率列表中的索引，丢弃原始元组。除了垃圾收集和内存浪费的问题，这是相当困难的阅读！

和字典一样，列表也是对象，它们有几个方法可以调用。以下是一些常见的问题：

  • append(element)方法在列表末尾添加一个元素
  • insert(index, element)方法在特定位置插入项目
  • count(element)方法告诉我们一个元素在列表中出现了多少次
  • index()方法告诉我们列表中某个项目的索引，如果找不到，则引发异常
  • find()方法做同样的事情，但是返回-1而不是引发缺失项的异常
  • reverse()方法完全按照它所说的做，将列表翻转过来
  • sort()方法具有一些相当复杂的面向对象行为，我们现在将介绍这些行为

排序表

如果没有任何参数，sort通常会做预期的事情。如果是字符串列表，它将按字母顺序排列。此操作区分大小写，因此所有大写字母都将排序在小写字母之前，即Z在a之前。如果是数字列表，它们将按数字顺序排序。如果提供了元组列表，则该列表将按每个元组中的第一个元素排序。如果提供了包含不可分拣物品的混合物，分拣将引发TypeError异常。

如果我们想把我们自己定义的对象放到一个列表中，并使这些对象可排序，我们必须做更多的工作。应在类上定义表示“小于”的特殊方法__lt__，以使该类的实例具有可比性。列表中的sort方法将在每个对象上访问此方法，以确定它在列表中的位置。如果我们的类在某种程度上小于传递的参数，则此方法应返回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属性的任何 duck 类型的对象进行比较；如果缺少这些属性，该方法将失败）。以下输出说明了该类在排序方面的作用：

>>> 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]
>>> l
[a:4, b:3, c:2, d:1]
>>> l.sort()
>>> 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__方法是我们实现排序所需的唯一方法。但是，从技术上讲，如果实现了，该类通常还应该实现类似的__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方法可以采用可选的key参数。此参数是一个函数，可以将列表中的每个对象转换为可以进行比较的对象。例如，我们可以使用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()。当我们将此函数作为键传递时，它将对小写值执行比较，而不是执行默认的区分大小写的比较。

有一些排序键操作非常常见，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模块文档。

套

列表是非常通用的工具，适合大多数容器对象应用程序。但当我们想要确保列表中的对象是唯一的时，它们就没有用处了。例如，歌曲库可能包含同一艺术家的许多歌曲。如果我们想对库进行排序并创建一个所有艺术家的列表，我们必须在再次添加他们之前检查列表以查看是否已经添加了艺术家。

这就是布景的用武之地。集合来自数学，它们代表一组无序的（通常）唯一数字。我们可以将一个数字添加到一个集合中五次，但它只会在集合中显示一次。

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

虽然集合的主要特征是唯一性，但这不是其主要目的。当组合使用两个或多个集合时，集合最有用。集合类型上的大多数方法都在其他集合上操作，使我们能够有效地组合或比较两个或多个集合中的项。这些方法的名称很奇怪，因为它们使用的术语与数学中使用的术语相同。我们将从三个返回相同结果的方法开始，不管哪个是调用集，哪个是被调用集。

union方法是最常见、最容易理解的方法。它将第二个集合作为参数，并返回一个新集合，该集合包含两个集合中或中的所有元素；如果一个元素在两个原始集合中，那么它在新集合中只显示一次。Union 就像一个逻辑的or操作，事实上，如果您不喜欢调用方法，可以在两个集合上使用|操作符来执行 Union 操作。

相反，交集方法接受第二个集合并返回一个新集合，该集合只包含两个集合中的元素。它类似于逻辑的and操作，也可以使用&操作符进行引用。

最后，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)))

如果我们运行这段代码，我们会看到这三种方法执行 print 语句所建议的操作：

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)并得到相同的结果。还有一些方法根据调用方和参数返回不同的结果。

这些方法包括issubset和issuperset，它们是彼此相反的。两者都返回一个bool。如果调用集中的所有项也在作为参数传递的集合中，issubset方法返回True。如果参数中的所有项也在调用集中，issuperset方法返回True。因此s.issubset(t)和t.issuperset(s)是相同的。如果t包含s中的所有元素，它们都将返回True。

最后，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方法返回一个空集，因为bands中没有不在my_artists中的项目。

union、intersection和difference方法都可以将多个集合作为参数；正如我们所料，它们将返回在对所有参数调用操作时创建的集合。

因此，集合上的方法清楚地表明集合是用来操作其他集合的，它们不仅仅是容器。如果我们有来自两个不同来源的数据，并且需要以某种方式快速组合它们，以确定数据重叠或不同的位置，我们可以使用集合操作来有效地比较它们。或者，如果传入的数据可能包含已处理的重复数据，则可以使用集合来比较这两个数据，并仅处理新数据。

最后，当使用in关键字检查成员资格时，知道集合比列表更有效是有价值的。如果在集合或列表上使用语法value in container，如果container中的一个元素等于value，否则返回True。但是，在列表中，它将查看容器中的每个对象，直到找到值为止，而在集合中，它只是对值进行散列并检查成员资格。这意味着，无论容器有多大，集合都会在相同的时间内找到值，但列表搜索值的时间会越来越长，因为列表包含越来越多的值。

扩展内置程序

我们在第 3 章中简要讨论了当对象相似时，如何使用继承扩展内置数据类型。现在，我们将更详细地讨论我们希望在什么时候这样做。

当我们有一个内置的容器对象要添加功能时，我们有两个选项。我们可以创建一个新对象，将该容器作为属性（组合）保存，也可以对内置对象进行子类化，并在其上添加或调整方法以执行我们想要的操作（继承）。

如果我们只想使用容器来存储一些使用容器特性的对象，那么合成通常是最好的选择。这样，就可以很容易地将该数据结构传递到其他方法中，并且它们将知道如何与之交互。但是如果我们想改变容器实际工作的方式，我们需要使用继承。例如，如果我们想确保list中的每个项目都是一个正好包含五个字符的字符串，我们需要扩展list并重写append()方法，以针对无效输入引发异常。我们还至少需要重写__setitem__(self, index, value)（列表上的一个特殊方法，每当我们使用x[index] = "value"语法时都会调用该方法）和extend()方法。

是的，列表是对象。我们一直在寻找的访问列表或字典键、循环容器和类似任务的所有特殊的非面向对象语法实际上是映射到下面的面向对象范例的“语法糖”。我们可能会问 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__方法的可怕之处在于，我们可以将它添加到我们编写的任何类中，如果我们在该类的实例上使用+操作符，它将被调用。例如，这就是字符串、元组和列表串联的工作方式。

所有的特殊方法都是如此。如果我们想对自定义对象使用x in myobj语法，我们可以实现__contains__。如果我们想使用myobj[i] = value语法，我们提供__setitem__方法，如果我们想使用something = myobj[i]，我们实现__getitem__。

在list类中有中的 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模块中讨论的抽象基类。

那么，回到前面关于何时使用组合与继承的观点：如果我们需要以某种方式更改类上的任何方法，包括特殊方法，我们肯定需要使用继承。如果我们使用 composition，我们可以编写执行验证或更改的方法，并要求调用方使用这些方法，但是没有什么可以阻止它们直接访问属性。他们可能会在我们的列表中插入一个没有五个字符的项目，这可能会混淆列表中的其他方法。

通常，扩展内置数据类型的需要表明我们使用了错误的数据类型。情况并不总是这样，但是如果我们想扩展一个内置的，我们应该仔细考虑不同的数据结构是否更适合。

例如，考虑创建一个记住键插入顺序的字典所需的内容。一种方法是保存一个有序的密钥列表，该列表存储在一个特殊派生的子类dict中。然后我们可以覆盖方法keys、values、__iter__和items来按顺序返回所有内容。当然，我们还必须覆盖__setitem__和setdefault以使我们的列表保持最新。dir(dict)的输出中可能还有一些其他方法需要重写，以保持列表和字典的一致性（clear和__delitem__记住，以跟踪项目何时被删除），但在本例中，我们不担心它们。

所以我们将扩展dict并添加一个有序密钥列表。虽然很琐碎，但是我们在哪里创建实际的列表呢？我们可以将它包含在__init__方法中，这将很好地工作，但我们不能保证任何子类都会调用该初始值设定项。还记得我们在第 2 章中讨论的__new__方法吗？Python 中的对象？我说它通常只在非常特殊的情况下有用。这是一种特殊情况。我们知道__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__，因为默认实现是有效的（实际上，只有当我们初始化一个空的DictSorted对象时，这才是正确的，这是标准行为。如果我们想支持dict构造函数的其他变体，它接受字典或元组列表，我们需要修复__init__来更新ordered_keys列表）。设置项目的两种方法非常相似；它们都会更新键列表，但前提是之前未添加该项。我们不希望列表中出现重复项，但不能在此处使用集合；这是无序的！

keys、items和values方法都将视图返回到字典中。集合库在字典上提供三个只读的View对象；他们使用__iter__方法循环键，然后使用__getitem__（我们不需要覆盖）检索值。因此，我们只需要定义我们的定制__iter__方法，就可以使这三个视图正常工作。您可能认为超类可以使用多态性正确地创建这些视图，但是如果我们不重写这三个方法，它们就不会返回正确排序的视图。

最后，__iter__方法是真正特殊的方法；它确保如果我们循环字典的键（使用for…in语法），它将以正确的顺序返回值。它通过返回ordered_keys列表的__iter__来实现这一点，该列表返回的迭代器对象与我们使用for时使用的迭代器对象相同。。。in在列表中。由于ordered_keys是所有可用键的列表（由于我们重写其他方法的方式），因此这也是字典的正确迭代器对象。

与普通字典相比，让我们看看这些方法中的一些：

>>> 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，但在行为和数据结构上有所不同。

然而，在我们开始排队之前，请考虑可信列表数据结构。Python 列表是许多用例中最有利的数据结构：

  • 它们支持对列表中任何元素的有效随机访问
  • 它们对元素有严格的排序
  • 它们有效地支持追加操作

但是，如果您在列表末尾以外的任何位置插入元素（尤其是在列表开头的位置），则它们的速度往往较慢。正如我们在集合一节中所讨论的，它们在检查列表中是否存在元素以及扩展搜索时也很慢。按排序顺序存储数据或对数据重新排序也可能效率低下。

让我们看看 Pythonqueue模块提供的三种类型的容器。

先进先出队列

FIFO 代表先进先出的，而代表“队列”一词最常见的定义。想象一下，一排人在银行或收银机前排队。第一个排队的人首先得到服务，第二个排队的人第二次得到服务，如果一个新的人想要得到服务，他们加入队伍的末端，等待轮到他们。

PythonQueue类就是这样。当一个或多个对象正在生成数据，而一个或多个其他对象正在以某种方式（可能以不同的速率）消耗数据时，它通常用作一种通信介质。设想一个消息传递应用程序正在从网络接收消息，但一次只能向用户显示一条消息。其他消息可以按照接收顺序在队列中缓冲。FIFO 队列在此类并发应用程序中被大量使用。（我们将在第 12 章、测试面向对象程序中进一步讨论并发性。）

当您不需要访问数据结构中的任何数据时，Queue类是一个不错的选择，下一个要使用的对象除外。使用列表进行此操作效率较低，因为在后台，在列表开头插入（或删除）数据可能需要移动列表中的其他元素。

队列有一个非常简单的 API。一个Queue可以有“无限”（直到计算机内存耗尽）的容量，但它通常被限制在某个最大大小。主要的方法是put()和get()，它们将一个元素添加到行的后面，并按顺序从前面检索它们。这两种方法都接受可选参数，以控制由于队列为空（无法获取）或已满（无法放置）而导致操作无法成功完成时发生的情况。默认行为是阻塞或空闲等待，直到Queue对象有数据或空间来完成操作。您可以通过传递block=False参数让它引发异常。或者，您可以让它在通过传递timeout参数引发异常之前等待定义的时间量。

这个类还有一些方法来检查Queue是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数据结构的顶部实现队列。DEQUE 是高级数据结构，允许高效访问集合的两端。它提供了比Queue公开的更灵活的接口。如果您想对 Python 文档进行更多的实验，请参阅它。

后进先出队列

后进先出（后进先出队列更为频繁地被称为栈。想象一下，在一堆文件中，您只能访问最上面的文件。您可以将另一张纸放在纸堆顶部，使其成为新的最上面的纸，也可以将最上面的纸拿走，露出其下面的纸。

传统上，堆栈上的操作被命名为 push 和 pop，但是 Pythonqueue模块使用与 FIFO 队列完全相同的 API：put()和get()。然而，在后进先出队列中，这些方法在堆栈的“顶部”操作，而不是在行的前后。这是多态性的一个很好的例子。如果您查看 Python 标准库中的Queue源代码，您会发现实际上有一个超类，其中包含 FIFO 和 LIFO 队列的子类，这些子类实现了少数操作（在堆栈顶部操作，而不是在deque实例的前面和后面操作），这两种操作之间存在着极大的差异。

以下是后进先出队列运行的一个示例：

>>> 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在引擎盖下使用了一个标准列表！

有几个原因可以让您使用LifoQueue而不是列表。最重要的是LifoQueue支持多线程的干净并发访问。如果在并发设置中需要类似堆栈的行为，则应将列表留在家中。第二，LifoQueue强制堆栈接口。例如，您不能在无意中将值插入到LifoQueue中的错误位置（不过，作为练习，您可以完全有意识地解决如何执行此操作）。

优先级队列

优先级队列实施了与以前队列实现截然不同的排序方式。同样，它们遵循完全相同的get()和put()API，但不是依赖项目到达的顺序来确定何时应该返回，而是返回最“重要”的项目。按照惯例，最重要或优先级最高的项是使用小于运算符对最低项进行排序的项。

一种常见的约定是将元组存储在优先级队列中，其中元组中的第一个元素是该元素的优先级，第二个元素是数据。另一个常见的范例是实现__lt__方法，正如我们在本章前面讨论的那样。队列中有多个具有相同优先级的元素是完全可以接受的，尽管不能保证首先返回哪个元素。

例如，搜索引擎可能会使用优先级队列来确保它在对不太可能被搜索的站点进行爬网之前刷新最流行网页的内容。产品推荐工具可能会使用它来显示排名最高的产品的信息，同时仍会加载排名较低的产品的数据。

请注意，优先级队列将始终返回队列中当前最重要的元素。如果队列为空，get()方法将阻塞（默认情况下），但如果队列中已经有内容，则不会阻塞并等待添加更高优先级的元素。队列对尚未添加的元素（甚至对以前提取的元素）一无所知，只根据队列的当前内容做出决策。

此交互式会话显示了一个优先级队列，使用元组作为权重来确定处理的顺序项：

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

优先级队列几乎普遍使用heap数据结构实现。Python 的实现利用heapq模块将堆有效地存储在普通列表中。关于堆的更多信息，请参阅算法和数据结构的教科书，更不用说我们在这里没有介绍的许多其他有趣的结构了。无论数据结构是什么，您都可以使用面向对象的原则将相关算法（行为），如heapq模块中提供的算法（行为），围绕它们在计算机内存中构建的数据进行包装，就像queue模块在标准库中代表我们所做的那样。

案例研究

为了将所有内容联系在一起，我们将编写一个简单的链接收集器，它将访问一个网站，并收集它在该网站中找到的每个页面上的每个链接。不过，在开始之前，我们需要一些测试数据。只需编写一些 HTML 文件即可使用，这些文件包含相互之间以及到 Internet 上其他站点的链接，如下所示：

<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（现存最蹩脚的个人网站之一！）的目录，如果您不想自己设置它们的话。

现在，通过输入包含所有这些文件的目录来启动一个简单的 web 服务器，并运行以下命令：

python3 -m http.server

这将启动在端口 8000 上运行的服务器；您可以在 web 浏览器中查看通过访问http://localhost:8000/创建的页面。

注

我怀疑任何人都能用更少的工作建立和运行一个网站！千万不要说，“用 Python 做这件事不容易。”

我们的目标是向收集器传递站点的基本 URL（在本例中为：http://localhost:8000/），并让收集器创建一个包含站点上每个唯一链接的列表。我们需要考虑三种类型的 URL（指向外部站点的链接，以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函数从 URL 中提取主机名；所以即使我们传入了http://localhost:8000/some/page.html，它仍然会在主机http://localhost:8000/的顶层运行。这是有意义的，因为我们希望收集站点上的所有链接，尽管它假定每个页面都通过一些链接序列连接到索引。

collect_links方法连接到服务器并从服务器下载指定的页面，并使用正则表达式查找页面中的所有链接。正则表达式是一种非常强大的字符串处理工具。不幸的是，他们有一个陡峭的学习曲线；如果你以前没有使用过它们，我强烈建议你学习关于这个主题的所有书籍或网站。如果您认为它们不值得知道，那么尝试在没有它们的情况下编写前面的代码，您将改变主意。

该示例也在 PosiT0Ay 方法的中间停止，以打印链接的值。这是在编写程序时测试程序的常用方法：停止并输出值，以确保它是我们期望的值。下面是它为我们的示例输出的内容：

['contact.html', 'blog.html', 'esme.html', '/hobbies.html',
'/contact.html', 'http://www.archlinux.org/']

现在我们有了第一页中所有链接的集合。我们能用它做什么？我们不能只是将链接弹出到一个集合中来删除重复项，因为链接可能是相对的，也可能是绝对的。例如，contact.html和/contact.html指向同一页。因此，我们应该做的第一件事是规范化所有指向完整 URL 的链接，包括主机名和相对路径。我们可以通过向对象添加一个normalize_url方法来实现这一点：

    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

此方法将每个 URL 转换为包含协议和主机名的完整地址。现在，两个联系人页面具有相同的值，我们可以将它们存储在一个集合中。我们必须修改__init__来创建集合，collect_links将所有链接放入集合。

然后，我们必须访问所有非外部链接并收集它们。但是等一下；如果我们这样做，当我们两次遇到同一个页面时，如何避免重新访问链接？看起来我们实际上需要两组链接：一组收集的链接和一组访问的链接。这表明我们明智地选择了一组数据来表示我们的数据；我们知道，当我们操作多个集合时，集合是最有用的。让我们设置这些：

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)

创建规范化链接列表的行使用set理解，与列表理解没有区别，只是结果是一组值。我们将在下一章详细介绍这些。再一次，该方法停止打印当前值，这样我们就可以验证我们的集合没有被混淆，并且difference确实是我们想要调用以收集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方法中的任何前斜杠，以删除此版本代码中的重复项。

因为最终结果是一个未排序的字典，所以对链接的处理顺序没有限制。因此，我们可以很容易地在这里使用LifoQueue而不是Queue。优先级队列可能没有多大意义，因为在这种情况下，链接没有明显的优先级。

练习

学习如何选择正确的数据结构的最佳方法是多次出错。获取一些您最近编写的代码，或者编写一些使用列表的新代码。尝试使用一些不同的数据结构重写它。哪些更有意义？哪些没有？哪些代码最优雅？

尝试使用几对不同的数据结构。您可以查看在前一章练习中所做的示例。是否存在可以使用namedtuple或dict方法的对象？尝试两种方法并查看。是否存在可能因为您没有真正访问值而设置的字典？你们有检查重复项的清单吗？一套就够了吗？或者几套？其中一个队列实现会更高效吗？将 API 限制在堆栈顶部而不是允许随机访问列表是否有用？

如果您想使用一些特定的示例，请尝试调整链接收集器以同时保存用于每个链接的标题。也许您可以用 HTML 生成一个站点地图，列出站点上的所有页面，并包含指向其他页面的链接列表，这些页面以相同的链接标题命名。

您最近是否编写过任何容器对象，可以通过继承内置方法并重写某些“特殊”双下划线方法来改进这些对象？您可能需要做一些研究（使用dir和help，或者 Python 库参考）来找出哪些方法需要重写。您确定继承是应用的正确工具吗；基于组合的解决方案是否更有效？在你做出决定之前，两种方法都试一下（如果可能的话）。试着找出每种方法优于另一种的不同情况。

如果您在开始本章之前熟悉各种 Python 数据结构及其用法，您可能会感到厌烦。但是如果是这样的话，你很有可能过度使用数据结构！查看一些旧代码，并重写它以使用更多自制对象。仔细考虑备选方案并全部试用；哪一个是最具可读性和可维护性的系统？

始终严格评估您的代码和设计决策。养成回顾旧代码的习惯，并注意您对“良好设计”的理解是否在编写后发生了变化。软件设计有很大的美学成分，就像艺术家在画布上画油画一样，我们都必须找到最适合我们的风格。

总结

我们已经介绍了几种内置数据结构，并试图了解如何为特定应用程序选择一种。有时，我们能做的最好的事情就是创建一个新的对象类，但通常，其中一个内置项正好提供了我们所需要的。如果没有，我们总是可以使用继承或组合来适应我们的用例。我们甚至可以重写特殊方法来完全改变内置语法的行为。

在下一章中，我们将讨论如何集成 Python 的面向对象和非面向对象方面。一路上，我们会发现它比乍一看更面向对象！