Python 数据结构和算法实用指南（一）（3）

Python 数据结构和算法实用指南（一）（2）https://developer.aliyun.com/article/1507523

对字典进行排序

如果我们想对字典的键或值进行简单的排序，我们可以这样做：

>>> d = {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6} 
>>> sorted(list(d)) 
['five', 'four', 'one', 'six', 'three', 'two']  
>>> sorted(list(d.values())) 
[1, 2, 3, 4, 5, 6] 

请注意，前面代码中的第一行按字母顺序对键进行排序，第二行按整数值的顺序对值进行排序。

sorted()方法有两个感兴趣的可选参数：key和reverse。key参数与字典键无关，而是一种传递函数给排序算法以确定排序顺序的方法。例如，在下面的代码中，我们使用__getitem__特殊方法根据字典的值对字典键进行排序：

基本上，前面的代码对d中的每个键使用相应的值进行排序。我们也可以根据字典键的排序顺序对值进行排序。然而，由于字典没有一种方法可以通过其值返回一个键，就像列表的list.index方法一样，使用可选的key参数来做到这一点有点棘手。另一种方法是使用列表推导式，就像下面的例子演示的那样：

sorted()方法还有一个可选的reverse参数，毫不奇怪，它确实做到了它所说的—反转排序列表的顺序，就像下面的例子一样：

现在，假设我们有以下字典，其中英语单词作为键，法语单词作为值。我们的任务是将字符串值放在正确的数字顺序中：

d2={'one':'uno','two':'deux','three':'trois','four':'quatre','five':'cinq','six':'six'}

当然，当我们打印这个字典时，它可能不会按正确的顺序打印。因为所有的键和值都是字符串，我们没有数字顺序的上下文。为了将这些项目放在正确的顺序中，我们需要使用我们创建的第一个字典，将单词映射到数字作为对英语到法语字典进行排序的一种方式：

请注意，我们正在使用第一个字典d的值来对第二个字典d2的键进行排序。由于我们两个字典中的键是相同的，我们可以使用列表推导式来对法语到英语字典的值进行排序：

当然，我们可以定义自己的自定义方法，然后将其用作排序方法的关键参数。例如，在这里，我们定义一个简单地返回字符串的最后一个字母的函数：

def corder(string): 
    return (string[len(string)-1])

然后，我们可以将其用作排序函数的关键，按其最后一个字母对每个元素进行排序：

文本分析的字典

字典的常见用途是计算序列中相似项的出现次数；一个典型的例子是计算文本中单词的出现次数。以下代码创建了一个字典，其中文本中的每个单词都用作键，出现次数作为其值。这使用了一个非常常见的嵌套循环习语。在这里，我们使用它来遍历文件中的行的外部循环和字典的键的内部循环：

def wordcount(fname):  
   try: 
        fhand=open(fname) 
   except:
        print('File can not be opened') 
        exit() 
   count=dict() 
   for line in fhand: 
        words=line.split() 
        for word in words: 
            if word not in count: 
                count[word]=1  
            else: 
                count[word]+=1 
   return(count)

这将返回一个字典，其中每个唯一单词在文本文件中都有一个元素。一个常见的任务是将这些项目过滤成我们感兴趣的子集。您需要在运行代码的同一目录中保存一个文本文件。在这里，我们使用了alice.txt，这是《爱丽丝梦游仙境》的一个简短摘录。要获得相同的结果，您可以从davejulian.net/bo5630下载alice.txt，或者使用您自己的文本文件。在下面的代码中，我们创建了另一个字典filtered，其中包含来自count的子集：

count=wordcount('alice.txt') 
filtered={key:value for key, value in count.items() if value <20 and value>16 }

当我们打印过滤字典时，我们得到以下结果：

{'once': 18, 'eyes': 18, 'There': 19, 'this,': 17, 'before': 19, 'take': 18, 'tried': 18, 'even': 17, 'things': 19, 'sort': 17, 'her,': 18, '`And': 17, 'sat': 17, '`But': 19, "it,'": 18, 'cried': 18, '`Oh,': 19, 'and,': 19, "`I'm": 19, 'voice': 17, 'being': 19, 'till': 19, 'Mouse': 17, '`but': 19, 'Queen,': 17}

请注意使用字典推导来构建过滤字典。字典推导的工作方式与我们在第一章中看到的列表推导相同，即Python 对象、类型和表达式。

集合

集合是无序的唯一项集合。集合本身是可变的——我们可以向其中添加和删除项目；但是，项目本身必须是不可变的。集合的一个重要区别是它们不能包含重复的项目。集合通常用于执行诸如交集、并集、差集和补集等数学运算。

与序列类型不同，集合类型不提供任何索引或切片操作。Python 中有两种类型的集合对象，可变的set对象和不可变的frozenset对象。使用花括号内的逗号分隔的值创建集合。顺便说一句，我们不能使用a={}创建一个空集，因为这将创建一个字典。要创建一个空集，我们要么写a=set()，要么写a=frozenset()。

集合的方法和操作描述在下表中：

在上表中，参数t可以是任何支持迭代的 Python 对象，所有方法都适用于set和frozenset对象。重要的是要意识到这些方法的操作符版本要求它们的参数是集合，而方法本身可以接受任何可迭代类型。例如，对于任何集合s，s-[1,2,3]将生成不支持的操作数类型。使用等效的s.difference([1,2,3])将返回一个结果。

可变的set对象具有其他方法，如下表所述：

在这里，考虑一个简单的示例，显示了添加、删除、丢弃和清除操作：

>>> s1 = set()
>>> s1.add(1)
>>> s1.add(2)
>>> s1.add(3)
>>> s1.add(4)
>>> s1
{1, 2, 3, 4}
>>> s1.remove(4)
>>> s1
{1, 2, 3}
>>> s1.discard(3)
>>> s1
{1, 2}
>>>s1.clear()
>>>s1
set()

以下示例演示了一些简单的集合操作及其结果：

请注意，set对象不在乎其成员不全是相同类型，只要它们都是不可变的。如果您尝试在集合中使用可变对象，例如列表或字典，您将收到一个不可哈希类型错误。可哈希类型都有一个哈希值，在实例的整个生命周期中不会改变。所有内置的不可变类型都是可哈希的。所有内置的可变类型都不可哈希，因此不能用作集合的元素或字典的键。

还要注意在前面的代码中，当我们打印出s1和s2的并集时，只有一个值为'ab'的元素。这是集合的一个自然属性，它们不包括重复项。

除了这些内置方法之外，我们还可以对集合执行许多其他操作。例如，要测试集合的成员资格，请使用以下方法：

我们可以使用以下方法循环遍历集合中的元素：

不可变集合

Python 有一个名为frozenset的不可变集合类型。它的工作方式几乎与set完全相同，除了不允许更改值的方法或操作，例如add()或clear()方法。这种不可变性有几种有用之处。

例如，由于普通集合是可变的，因此不可哈希，它们不能用作其他集合的成员。另一方面，frozenset是不可变的，因此可以用作集合的成员：

此外，frozenset的不可变属性意味着我们可以将其用作字典的键，如下例所示：

数据结构和算法的模块

除了内置类型之外，还有几个 Python 模块可以用来扩展内置类型和函数。在许多情况下，这些 Python 模块可能提供效率和编程优势，使我们能够简化我们的代码。

到目前为止，我们已经查看了字符串、列表、集合和字典的内置数据类型，以及十进制和分数模块。它们通常被术语抽象数据类型（ADT）描述。 ADT 可以被认为是可以在数据上执行的操作集的数学规范。它们由其行为而不是其实现来定义。除了我们已经查看的 ADT 之外，还有几个 Python 库提供了对内置数据类型的扩展。这将在下一节中讨论。

集合

collections模块提供了更专门的、高性能的替代品，用于内置数据类型，以及一个实用函数来创建命名元组。以下表列出了collections模块的数据类型和操作及其描述：

双端队列

双端队列，通常发音为decks，是类似列表的对象，支持线程安全、内存高效的追加。双端队列是可变的，并支持列表的一些操作，如索引。双端队列可以通过索引分配，例如，dq[1] = z；但是，我们不能直接切片双端队列。例如，dq[1:2]会导致TypeError（我们将看一种从双端队列返回切片作为列表的方法）。

双端队列比列表的主要优势在于，在双端队列的开头插入项目要比在列表的开头插入项目快得多，尽管在双端队列的末尾插入项目的速度比列表上的等效操作略慢一些。双端队列是线程安全的，并且可以使用pickle模块进行序列化。

一个有用的思考双端队列的方式是填充和消耗项目。双端队列中的项目通常是从两端顺序填充和消耗的：

我们可以使用pop()和popleft()方法来消耗双端队列中的项目，如下例所示：

我们还可以使用rotate(n)方法将所有项目向右移动和旋转n步，对于n整数的正值或n步的负值向左移动，使用正整数作为参数，如下例所示：

请注意，我们可以使用rotate和pop方法来删除选定的元素。还值得知道的是，返回双端队列切片的简单方法，可以按以下方式完成：

itertools.islice()方法的工作方式与列表上的切片相同，只是它不是以列表作为参数，而是以可迭代对象作为参数，并返回所选值，按起始和停止索引，作为列表。

双端队列的一个有用特性是它们支持一个maxlen可选参数，用于限制双端队列的大小。这使得它非常适合一种称为循环缓冲区的数据结构。这是一种固定大小的结构，实际上是端对端连接的，它们通常用于缓冲数据流。以下是一个基本示例：

dq2=deque([],maxlen=3) 
for i in range(6):
    dq2.append(i) 
    print(dq2)

这将打印出以下内容：

在这个例子中，我们从右侧填充并从左侧消耗。请注意，一旦缓冲区已满，最旧的值将首先被消耗，然后从右侧替换值。在第四章中，当实现循环列表时，我们将再次看循环缓冲区。

ChainMap 对象

collections.chainmap类是在 Python 3.2 中添加的，它提供了一种将多个字典或其他映射链接在一起，以便它们可以被视为一个对象的方法。此外，还有一个maps属性，一个new_child()方法和一个parents属性。ChainMap对象的基础映射存储在列表中，并且可以使用maps[i]属性来检索第i个字典。请注意，尽管字典本身是无序的，ChainMap对象是有序的字典列表。

ChainMap在使用包含相关数据的多个字典的应用程序中非常有用。消费应用程序期望按优先级获取数据，如果两个字典中的相同键出现在基础列表的开头，则该键将优先考虑。ChainMap通常用于模拟嵌套上下文，例如当我们有多个覆盖配置设置时。以下示例演示了ChainMap的可能用例：

>>> import collections
>>> dict1= {'a':1, 'b':2, 'c':3}
>>> dict2 = {'d':4, 'e':5}
>>> chainmap = collections.ChainMap(dict1, dict2)  # linking two dictionaries
>>> chainmap
ChainMap({'a': 1, 'b': 2, 'c': 3}, {'d': 4, 'e': 5})
>>> chainmap.maps
[{'a': 1, 'b': 2, 'c': 3}, {'d': 4, 'e': 5}]
>>> chainmap.values
<bound method Mapping.values of ChainMap({'a': 1, 'b': 2, 'c': 3}, {'d': 4, 'e': 5})
>>>> chainmap['b']   #accessing values 
2
>>> chainmap['e']
5

使用ChainMap对象而不仅仅是字典的优势在于我们保留了先前设置的值。添加子上下文会覆盖相同键的值，但不会从数据结构中删除它。当我们需要保留更改记录以便可以轻松回滚到先前的设置时，这可能很有用。

我们可以通过为map()方法提供适当的索引来检索和更改任何字典中的任何值。此索引表示ChainMap中的一个字典。此外，我们可以使用parents()方法检索父设置，即默认设置：

>>> from collections import ChainMap
>>> defaults= {'theme':'Default','language':'eng','showIndex':True, 'showFooter':True}
>>> cm= ChainMap(defaults)   #creates a chainMap with defaults configuration
>>> cm.maps[{'theme': 'Default', 'language': 'eng', 'showIndex': True, 'showFooter': True}]
>>> cm.values()
ValuesView(ChainMap({'theme': 'Default', 'language': 'eng', 'showIndex': True, 'showFooter': True}))
>>> cm2= cm.new_child({'theme':'bluesky'}) # create a new chainMap with a child that overrides the parent.
>>> cm2['theme']  #returns the overridden theme'bluesky'
>>> cm2.pop('theme')  # removes the child theme value
'bluesky' 
>>> cm2['theme']
'Default'
>>> cm2.maps[{}, {'theme': 'Default', 'language': 'eng', 'showIndex': True, 'showFooter': True}]
>>> cm2.parents
ChainMap({'theme': 'Default', 'language': 'eng', 'showIndex': True, 'showFooter': True})

计数器对象

Counter是字典的一个子类，其中每个字典键都是可散列对象，关联的值是该对象的整数计数。有三种初始化计数器的方法。我们可以将任何序列对象、key:value对的字典或格式为(object=value,...)的元组传递给它，如下例所示：

>>> from collections import Counter
>>> Counter('anysequence')
Counter({'e': 3, 'n': 2, 'a': 1, 'y': 1, 's': 1, 'q': 1, 'u': 1, 'c': 1})
>>> c1 = Counter('anysequence')
>>> c2= Counter({'a':1, 'c': 1, 'e':3})
>>> c3= Counter(a=1, c= 1, e=3)
>>> c1
Counter({'e': 3, 'n': 2, 'a': 1, 'y': 1, 's': 1, 'q': 1, 'u': 1, 'c': 1})
>>> c2
Counter({'e': 3, 'a': 1, 'c': 1})
>>> c3
Counter({'e': 3, 'a': 1, 'c': 1})

我们还可以创建一个空的计数器对象，并通过将其update方法传递给一个可迭代对象或字典来填充它。请注意，update方法添加计数，而不是用新值替换它们。填充计数器后，我们可以以与字典相同的方式访问存储的值，如下例所示：

>>> from collections import Counter
>>> ct = Counter()  # creates an empty counter object
>>> ct
Counter()
>>> ct.update('abca') # populates the object
>>> ct
Counter({'a': 2, 'b': 1, 'c': 1})
>>> ct.update({'a':3}) # update the count of 'a'
>>> ct
Counter({'a': 5, 'b': 1, 'c': 1})
>>> for item in ct:
 ...  print('%s: %d' % (item, ct[item]))
 ...
a: 5
b: 1
c: 1

计数器对象和字典之间最显着的区别是计数器对象对于缺失的项返回零计数，而不是引发键错误。我们可以使用其elements()方法从Counter对象创建迭代器。这将返回一个迭代器，其中不包括小于一的计数，并且顺序不被保证。在下面的代码中，我们执行一些更新，从Counter元素创建一个迭代器，并使用sorted()按字母顺序对键进行排序：

>>> ct
Counter({'a': 5, 'b': 1, 'c': 1})
>>> ct['x']
0
>>> ct.update({'a':-3, 'b':-2, 'e':2})
>>> ct
Counter({'a': 2, 'e': 2, 'c': 1, 'b': -1})
>>>sorted(ct.elements())
['a', 'a', 'c', 'e', 'e']

另外两个值得一提的Counter方法是most_common()和subtract()。最常见的方法接受一个正整数参数，确定要返回的最常见元素的数量。元素作为(key,value)元组的列表返回。

减法方法的工作方式与更新相同，只是它不是添加值，而是减去它们，如下例所示：

>>> ct.most_common()
[('a', 2), ('e', 2), ('c', 1), ('b', -1)]
>>> ct.subtract({'e':2})
>>> ct
Counter({'a': 2, 'c': 1, 'e': 0, 'b': -1})

有序字典

有序字典的重要之处在于它们记住插入顺序，因此当我们对它们进行迭代时，它们会按照插入顺序返回值。这与普通字典相反，普通字典的顺序是任意的。当我们测试两个字典是否相等时，这种相等性仅基于它们的键和值；但是，对于OrderedDict，插入顺序也被视为两个具有相同键和值的OrderedDict对象之间的相等性测试，但是插入顺序不同将返回False：

>>> import collections
>>> od1=  collections.OrderedDict()
>>> od1['one'] = 1
>>> od1['two'] = 2
>>> od2 =  collections.OrderedDict()
>>> od2['two'] = 2
>>> od2['one'] = 1
>>> od1==od2
False

类似地，当我们使用update从列表添加值时，OrderedDict将保留与列表相同的顺序。这是在迭代值时返回的顺序，如下例所示：

>>> kvs = [('three',3), ('four',4), ('five',5)]
>>> od1.update(kvs)
>>> od1
OrderedDict([('one', 1), ('two', 2), ('three', 3), ('four', 4), ('five', 5)])
>>> for k, v in od1.items(): print(k, v)

...
one 1
two 2
three 3
four 4
five 5

OrderedDict经常与 sorted 方法一起使用，以创建一个排序的字典。在下面的示例中，我们使用 Lambda 函数对值进行排序，并且在这里我们使用数值表达式对整数值进行排序：

>>> od3 = collections.OrderedDict(sorted(od1.items(), key= lambda t : (4*t[1])- t[1]**2))
>>>od3
OrderedDict([('five', 5), ('four', 4), ('one', 1), ('three', 3), ('two', 2)])
>>> od3.values() 
odict_values([5, 4, 1, 3, 2])

defaultdict

defaultdict对象是dict的子类，因此它们共享方法和操作。它作为初始化字典的便捷方式。使用dict时，当尝试访问尚未在字典中的键时，Python 会抛出KeyError。defaultdict覆盖了一个方法，missing(key)，并创建了一个新的实例变量，default_factory。使用defaultdict，而不是抛出错误，它将运行作为default_factory参数提供的函数，该函数将生成一个值。defaultdict的一个简单用法是将default_factory设置为int，并用它快速计算字典中项目的计数，如下例所示：

>>> from collections import defaultdict
>>> dd = defaultdict(int)
>>> words = str.split('red blue green red yellow blue red green green red')
>>> for word in words: dd[word] +=1
...
>>> dd
defaultdict(<class 'int'>, {'red': 4, 'blue': 2, 'green': 3, 'yellow': 1})

您会注意到，如果我们尝试使用普通字典来做这件事，当我们尝试添加第一个键时，我们会得到一个键错误。我们提供给defaultdict的int实际上是int()函数，它只是返回零。

当然，我们可以创建一个函数来确定字典的值。例如，以下函数在提供的参数是主要颜色（即red，green或blue）时返回True，否则返回False：

def isprimary(c):
     if (c=='red') or (c=='blue') or (c=='green'): 
         return True 
     else: 
         return False

了解命名元组

namedtuple方法返回一个类似元组的对象，其字段可以通过命名索引以及普通元组的整数索引进行访问。这允许在某种程度上自我记录和更易读的代码。在需要轻松跟踪每个元组代表的内容的应用程序中，这可能特别有用。此外，namedtuple从元组继承方法，并且与元组向后兼容。

字段名称作为逗号和/或空格分隔的值传递给namedtuple方法。它们也可以作为字符串序列传递。字段名称是单个字符串，可以是任何合法的 Python 标识符，不能以数字或下划线开头。一个典型的例子如下所示：

>>> from collections import namedtuple
>>> space = namedtuple('space', 'x y z')
>>> s1= space(x=2.0, y=4.0, z=10) # we can also use space(2.0,4.0, 10)
>>> s1
space(x=2.0, y=4.0, z=10)
>>> s1.x * s1.y * s1.z   # calculate the volume
80.0

除了继承的元组方法之外，命名元组还定义了三种自己的方法，_make()，asdict()和_replace。这些方法以下划线开头，以防止与字段名称可能发生冲突。_make()方法将可迭代对象作为参数，并将其转换为命名元组对象，如下例所示：

>>> sl = [4,5,6]
>>> space._make(sl)
space(x=4, y=5, z=6)
>>> s1._1
4

_asdict方法返回一个OrderedDict对象，其中字段名称映射到索引键，值映射到字典值。_replace方法返回元组的新实例，替换指定的值。此外，_fields返回列出字段名称的字符串元组。_fields_defaults方法提供将字段名称映射到默认值的字典。考虑以下示例代码片段：

>>> s1._asdict()
OrderedDict([('x', 3), ('_1', 4), ('z', 5)])
>>> s1._replace(x=7, z=9)
space2(x=7, _1=4, z=9)
>>> space._fields
('x', 'y', 'z')
>>> space._fields_defaults
{}

数组

array模块定义了一种类似于列表数据类型的数据类型数组，除了它们的内容必须是由机器架构或底层 C 实现确定的单一类型的约束。

数组的类型是在创建时确定的，并且由以下类型代码之一表示：

数组对象支持属性和方法：

数组对象支持所有正常的序列操作，如索引、切片、连接和乘法。

与列表相比，使用数组是存储相同类型数据的更有效的方法。在下面的例子中，我们创建了一个整数数组，其中包含从0到一百万减去1的数字，以及一个相同的列表。在整数数组中存储一百万个整数，大约需要相当于等效列表的 90%的内存：

>>> import array
>>> ba = array.array('i', range(10**6))
>>> bl = list(range(10**6))
>>> import sys
>>> 100*sys.getsizeof(ba)/sys.getsizeof(bl)
90.92989871246161

因为我们对节省空间感兴趣，也就是说，我们处理大型数据集和有限的内存大小，通常我们对数组进行原地操作，只有在需要时才创建副本。通常，enumerate 用于对每个元素执行操作。在下面的片段中，我们执行简单的操作，为数组中的每个项目添加一。

值得注意的是，当对创建列表的数组执行操作时，例如列表推导，使用数组的内存效率优势将被抵消。当我们需要创建一个新的数据对象时，一个解决方案是使用生成器表达式来执行操作。

使用这个模块创建的数组不适合需要矢量操作的矩阵工作。在下一章中，我们将构建自己的抽象数据类型来处理这些操作。对于数值工作来说，NumPy 扩展也很重要，可以在www.numpy.org上找到。

总结

在最后两章中，我们介绍了 Python 的语言特性和数据类型。我们研究了内置数据类型和一些内部 Python 模块，尤其是collections模块。还有其他几个与本书主题相关的 Python 模块，但与其单独检查它们，不如在开始使用它们时，它们的使用和功能应该变得不言自明。还有一些外部库，例如 SciPy。

在下一章中，我们将介绍算法设计的基本理论和技术。

Python 数据结构和算法实用指南（一）（4）https://developer.aliyun.com/article/1507536