07.md

七、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()构造函数或{}语法快捷方式创建字典。 实际上，后一种格式几乎总是被使用。 我们可以通过使用冒号将键与值分开，并使用逗号分隔键值对来预填充字典。

例如，在股票申请中，我们通常希望通过股票代码查找价格。 我们可以创建一个字典，使用股票代码作为键，并使用 current，high 和 low 的元组作为值，如下所示：

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)

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

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

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)简单得多，但“我想在一个可迭代的实例中计算特定实例”用例非常普遍，以至于 Python 开发人员为该类创建了一个特定的类。 它。 前面计算字符串中字符数的代码可以很容易地在一行中计算出：

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

Counter对象的行为类似于增强字典，其中键是要计数的项目，值是此类项目的数量。 most_common()方法是最有用的功能之一。 它返回按计数顺序排序的（键，计数）元组的列表。 您可以选择将整数参数传递给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]。 我认为它们看起来像是一张惊讶的脸，不是吗？ 您的计算机可能很惊讶，它可以如此轻松地对数据进行计数。 它的祖先是霍勒里斯（Hollerith）在 1890 年美国人口普查中使用的制表机，一定非常嫉妒！

列表

列表是最少的面向对象的 Python 数据结构。 虽然列表本身就是对象，但 Python 中有很多语法可以使列表的使用尽可能轻松。 与许多其他面向对象的语言不同，Python 中的列表仅可用。 我们不需要导入它们，并且很少需要在它们上调用方法。 我们可以遍历列表而无需显式请求迭代器对象，并且可以使用自定义语法构造一个列表（与字典一样）。 此外，列表理解和生成器表达式将它们变成了名副其实的计算功能的瑞士军刀。

我们不会过多地介绍语法。 您已经在网上的入门教程和本模块的先前示例中看到了它。 如果不学习如何使用列表，就不能花很长时间编写 Python！ 相反，我们将介绍何时应使用列表以及它们作为对象的性质。 如果您不知道如何创建或追加到列表，如何从列表中检索项目，或者“切片符号”是什么，我将指导您直接使用 Python 官方教程。 可以在这个页面在线找到。

在 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属性的任何鸭子类型的对象；如果缺少这些属性，它将失败）。 以下输出说明了有关排序的实际类：

>>> 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方法是最常见且最容易理解的方法。 它使用第二个集合作为参数，并返回一个新集合，该集合包含两个集合中或中的所有元素； 如果元素在两个原始集中都存在，那么它在新集中只会出现一次。 联合就像一个逻辑上的or操作，实际上，如果您不喜欢调用方法，|运算符可以用于两个集合上以执行联合操作。

相反，交集方法接受第二个集合并返回一个新集合，该集合仅包含两个集中的中的元素。 它类似于逻辑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，否则返回False。 但是，在列表中，它将查看容器中的每个对象，直到找到值为止；而在集合中，它只是对值进行哈希处理并检查成员资格。 这意味着无论容器有多大，集合都将在相同的时间内找到该值，但是随着列表包含越来越多的值，列表将花费越来越长的时间来搜索值。

扩展内置

现在，我们将更详细地说明何时需要这样做。

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

如果我们要做的就是使用容器来使用该容器的功能来存储一些对象，那么通常是最好的替代方法。 这样，就很容易将该数据结构传递给其他方法，并且他们将知道如何与之交互。 但是，如果我们想改变容器的实际工作方式，就需要使用继承。 例如，如果我们要确保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 参考也提供了大量有用的信息。 特别要关注collections模块中讨论的抽象基类。

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

通常，需要扩展内置数据类型表明我们使用了错误的数据类型。 并非总是如此，但是如果我们要扩展内置函数，则应仔细考虑是否应该使用其他数据结构。

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

因此，我们将扩展为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__，因为默认实现有效（实际上，只有初始化一个空的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

啊，我们的字典是按排序的，而普通字典不是。 欢呼！

注意

如果要在生产中使用此类，则必须重写其他几种特殊方法，以确保密钥在所有情况下都是最新的。 但是，您不需要这样做； 使用collections模块中的OrderedDict对象，该类提供的功能已在 Python 中提供。 尝试从collections导入类，然后使用help(OrderedDict)进一步了解它。

队列

队列是特有的数据结构，因为像集一样，它们的功能可以完全使用列表来处理。 但是，尽管列表是用途极为广泛的通用工具，但它们有时并不是容器操作的最有效数据结构。 如果您的程序使用的是小型数据集（在当今的处理器上多达数百甚至数千个元素），则列表可能会涵盖您的所有用例。 但是，如果您需要将数据规模扩展到数百万，则可能需要针对特定​​用例的更高效容器。 因此，Python 提供了三种类型的队列数据结构，具体取决于您要寻找的访问类型。 这三个都使用相同的 API，但是行为和数据结构都不同。

但是，在开始队列之前，请考虑信任列表数据结构。 对于许多用例，Python 列表是最有利的数据结构：

• 它们支持有效地随机访问列表中的任何元素
• 它们具有严格的元素顺序
• 他们有效地支持附加操作

但是，如果在列表末尾以外的任何地方插入元素，它们往往会使变慢（特别是在列表的开头时）。 正如我们在集合一节中讨论的那样，它们对于检查列表中是否存在某个元素以及通过扩展进行搜索也很慢。 按排序顺序存储数据或对数据重新排序也可能效率不高。

让我们看一下 Python queue模块提供的三种容器。

FIFO 队列

FIFO 代表为先进先出**，代表最普遍理解的单词“队列”定义。 想象有一群人在银行或收银机旁排队。 进入队伍的第一个人首先得到服务，队伍中的第二个人获得第二服务，如果有新人想要服务，他们会加入队伍的末端并等待轮到他们。**

Python Queue类就是这样。 当一个或多个对象正在生成数据而一个或多个其他对象以某种方式（可能以不同的速率）使用数据时，通常将其用作一种通信介质。 考虑一种正在从网络接收消息，但一次只能向用户显示一条消息的消息传递应用。 可以按照其他消息的接收顺序将它们缓存在队列中。 在此类并发应用中，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数据结构之上实现了队列。 双端队列是高级数据结构，可以有效访问集合的两端。 它提供的接口比Queue公开的接口更灵活。 如果您想尝试更多 Python 文档，请参考。

LIFO queues

LIFO（后进先出）队列更多，经常被称为堆栈。 考虑一堆纸，您只能访问最上面的纸。 您可以将另一张纸放在纸叠的顶部，使其成为新的最上面的纸，或者可以拿走最上面的纸以露出下面的纸。

传统上，堆栈上的操作称为 push 和 pop，但是 Python queue模块使用与 FIFO 队列完全相同的 API：put()和get()。 但是，在 LIFO 队列中，这些方法在堆栈的“顶部”操作，而不是在行的前面和后面。 这是多态性的一个很好的例子。 如果查看 Python 标准库中的Queue源代码，您实际上会看到一个超类，该超类具有 FIFO 和 LIFO 队列的子类，这些子类实现了一些操作（在堆栈的顶部而不是前面和后面）进行操作。 deque实例的返回）在两者之间存在重大差异。

这是运行中的 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都在引擎盖下使用了标准清单！

有几个原因可能需要使用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 上运行的服务器。 您可以在网络浏览器中访问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方法连接到服务器并从服务器下载指定的页面，并使用正则表达式查找页面中的所有链接。 正则表达式是一个非常强大的字符串处理工具。 不幸的是，他们的学习曲线陡峭。 如果您以前从未使用过它们，我强烈建议您学习有关该主题的所有书籍或网站。 如果您认为不值得了解它们，请尝试在没有它们的情况下编写前面的代码，您会改变主意。

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

['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语句确保我们仅从一个网站收集链接； 我们不想离开并收集 Internet 上所有页面的所有链接（除非我们是 Google 或 Internet 存档！）。 如果我们修改程序底部的主要代码以输出收集的链接，我们可以看到似乎已经收集了所有链接：

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。 优先级队列可能没有多大意义，因为在这种情况下，没有明显的优先级附加到链接。