2.1　Python中的数据结构

在任何编程语言中，数据结构都用于存储和操作复杂的数据。在Python中，数据结构也是数据存储容器，用于以有效方式对数据进行管理、组织和查找。它们用于存储成组出现的数据元素，这些数据元素需要一起存储和处理，每一组这样的数据称为一个集合。在Python中，有五种不同的数据结构可以用来存储集合：

• 列表（list）：有序的可变元素序列。
• 元组（tuple）：有序的不可变元素序列。
• 集合（set）：无序元素序列（其中元素不重复）。
• 字典（dictionary）：无序的键值对序列。
• 数据帧（DataFrame）：存储二维数据的二维结构。

下面我们在更详细地介绍它们。

2.1.1　列表

在Python中，列表是用来存储可变元素序列的主要数据结构。列表中存储的数据元素序列不必是同一数据类型。

要创建一个列表，数据元素需要用[ ]括起来，并且需要用逗号隔开。例如，下面的代码创建了一个含有四个数据元素的列表，其数据类型不完全相同：

在Python中，列表是一种创建一维可写数据结构的便捷方法，在算法的不同内部阶段都特别有用。

使用列表

数据结构关联的实用功能非常有用，因为这些功能可以用来管理列表中的数据。

我们看看如何使用列表：

• 列表索引：由于元素在列表中的位置是确定的，因此可以使用索引来获取某个特定位置的元素。下面的代码演示了这个概念：

该代码创建的四元素列表如图2-1所示。

注意，索引从0开始，因此第二个元素Green由索引1即bin_color[1]检索。

• 列表切片：通过指定索引范围可以检索列表中的元素子集，这个过程叫作切片。下面的代码可以用来创建列表的一个切片：
• 

注意，列表是Python中非常流行的一维数据结构之一。

我们看看下面的代码片段：

如果未指定起始索引，则意味着起始索引为列表的开始，如果未指定终止索引，则表示终止索引为列表的末尾，前面的代码实际上已经演示了这个概念。

• 负索引：在Python中，也有负索引，负索引从列表的末尾开始计数。下面的代码对此进行了演示：

注意，如果我们想将参考点设置为最后一个元素而不是第一个元素，负索引特别有用。

• 嵌套：列表的每个元素可以是简单数据类型，也可以是复杂数据类型，这就允许在列表中进行嵌套。对于迭代和递归算法来说，这是非常重要的功能。

让我们来看看下面的代码，这是在一个列表中嵌套列表的例子：

• 迭代：Python允许使用for循环对列表中的每个元素进行迭代，这在下面的例子中进行了演示：

注意，前面的代码会遍历列表并打印每个元素。

lambda函数

在列表中可以使用大量的lambda函数。lambda函数在算法中特别重要，其提供了动态创建函数的能力。有时在文献中，lambda函数也被称为匿名函数。本小节将展示其用途：

• 过滤数据：为了过滤数据，需要先定义一个谓词，说明需要完成什么工作，它是输入一个参数并返回一个布尔值的函数。下面的代码演示了它的使用方法：

在这段代码中，我们使用了lambda函数来过滤一个列表，该函数指定了过滤标准。filter函数旨在依据定义的标准从序列中过滤掉不符合标准的元素。在Python中，filter函数通常与lambda函数一起使用。除了列表之外，它还可以用来从元组或集合中过滤元素。对于前面展示的代码，定义的过滤标准是x>100，这段代码将遍历列表中的所有元素，并过滤掉不符合这个标准的元素。

• 数据转换：map()函数可用于通过lambda函数进行数据转换。示例如下：

将map函数和lambda函数一起使用可以提供相当强大的功能。当与map函数一起使用时，lambda函数可以用来声明一个转换器，对给定序列的每个元素进行转换。在前面展示的代码中，转换器是取平方。因此，我们使用map函数对列表中的每个元素求平方。

• 数据聚合：对于数据聚合，可以使用reduce()函数，该函数会循环运行定义的函数，对列表中每对元素值进行处理：

注意，reduce函数需要定义一个数据聚合函数，前面代码中的数据聚合函数是doSum，它定义了如何对给定列表中的各项元素进行聚合。聚合从最前面的两个元素开始，然后用聚合结果替换这两个元素。这样，列表元素会减少，该过程不断重复，直到最后得到一个聚合数字。doSum函数中的x1和x2分别代表了每轮迭代中的两个数字，doSum则代表了它们聚合的标准。

前面代码块所得结果是一个单值（即270）。

range函数

range函数可以用来轻松地生成一个大的数字列表。它用作自动填充列表的数字序列。

range函数使用起来很简单，使用时只需指定列表中想要的元素个数。在默认情况下，列表中的元素从0开始，并逐渐递增1：

我们还可以指定结束的数字（不包含）和步长（两个相邻元素之间的差值）：

上面的range函数给出从3到29的奇数（不包括结束数字，也就是29）。

列表的时间复杂度

列表的时间复杂度可以使用大O记号来表示，整理如下：

注意，添加单个元素所需的时间与列表的规模无关，而表格中其他操作的复杂度则取决于列表的规模。列表的规模越大，性能受到的影响就越明显。

2.1.2　元组

第二个可以用于存储集合的数据结构是元组。与列表相反，元组是不可变的（只读）数据结构。元组由一些被（ ）包围的元素组成。

同列表一样，元组中的元素可以是不同类型的，元组也允许其元素使用复杂数据类型。因此，元组中也可以包含其他元组，这就提供了一种创建嵌套数据结构的方法。创建嵌套数据结构的能力在迭代和递归算法中特别有用。

下面的代码演示了如何创建元组：

注意，在前面的代码中，a[2]指的是第三个元素，即一个元组(100,200,300)。a[2][1]指的是这个元组中的第二个元素，也就是200。

元组的时间复杂度

元组的Append函数的时间复杂度总结如下（使用大O记号）：

注意，Append函数是在一个已经存在的元组末尾添加一个元素，其复杂度为O(1)。

注意，元组是不可变的数据类型，其中没有Append函数。这里所说的Append其实是创建了一个新的元组，具体见如下代码：

可以看到，我们成功地将新元素添加到元组的末尾，但其实是创建了一个新的元组。

2.1.3　字典

以键值对的形式保存数据是非常重要的，尤其是在分布式算法中。在Python中，这些键值对的集合被存储为一个称为字典的数据结构。要创建一个字典，应该选择一个在整个数据处理过程中最适合识别数据的属性作为键。值可以是任何类型的元素，例如，数字或字符串。Python总是使用复杂的数据类型（如列表）作为值。如果用字典作为值的数据类型，则可以创建嵌套字典。

为了创建一个为各种变量分配颜色的简单字典，需要将键值对用{ }括起来。例如，下面的代码创建了一个由三个键值对组成的简单字典：

前面一段代码所创建的三个键值对也在图2-2中进行了说明。

现在，我们看看如何检索和更新与键相关联的值：

1. 要检索一个与键相关联的值，可以使用get函数，也可以使用键作为索引：

2. 要更新与键相关联的值，可以使用以下代码：

请注意，前面的代码演示了如何更新一个与字典中的某个特定键相关的值。

字典的时间复杂度

下表给出了使用大O记号表示的字典的时间复杂度：

从字典的复杂度分析中可以发现一个需要注意的重要现象，那就是获取或设置键值所需的时间与字典的大小完全无关。这意味着，将一个键值对添加到一个大小为3的字典中所花费的时间与将一个键值对添加到一个大小为100万的字典中所花费的时间是一样的。

2.1.4　集合

集合被定义为元素集，可以是不同类型的元素，这些元素都被{ }括起来。例如，请看下面的代码块：

集合定义的特性是，它只存储每个元素的不同值。如果我们试图添加另一个具有重复值的元素，它会忽略重复值，如下面的代码所示：

为了演示在集合上可以进行什么样的操作，我们来定义两个集合：

• 一个名为yellow的集合，里面包含了黄色的东西。
• 另一个名为red的集合，里面包含了红色的东西。

请注意，这两个集合之间有公共部分。这两个集合及其关系可以借助图2-3进行展示。

如果想在Python中实现这两个集合，代码将是这样的：

现在，考虑以下代码，它演示了如何使用Python进行集合操作：

如前面的代码片段所示，Python中的集合可以有并和交等运算。我们知道，并运算将两个集合的所有元素合并到一起，而交运算则给出两个集合之间的公共元素集合。需要注意以下两点：

• yellow|red用于获得前面定义的两个集合（yellow和red）的并。
• yellow&red用于获得前面定义的两个集合（yellow和red）的交。

集合的时间复杂度

以下是集合的时间复杂度分析：

从集合的复杂度分析中可以发现一个需要注意的重要现象，那就是添加一个元素所需的时间与该集合的大小完全无关。

2.1.5　数据帧

数据帧是Python的pandas包中的一种数据结构，用来存储可用的表格数据。它是算法中重要的数据结构之一，用于处理传统的结构化数据。我们看看以下表格：

现在，我们使用数据帧来表示它。

可以使用以下代码创建一个简单的数据帧：

请注意，在上面的代码中，df.column是一个用来指定各列名称的列表。

数据帧术语

我们来看看在数据帧中使用的一些术语：

• 轴（axis）：在pandas的文档中，一个数据帧的单列或单行称为轴。
• 轴族（axes）：如果轴的数量大于1，则它们作为一组，称为轴族。
• 标签（label）：数据帧允许用标签来命名列和行。

创建数据帧的子集

从根本上说，创建数据帧子集的方法主要有两种（比如说子集的名字是myDF）：

• 选择列
• 选择行

选择列

在机器学习算法中，选择合适的特征集是一项重要任务。算法在特定阶段时可能不需要全部特征。在Python中，特征选择是通过选择列来实现的，下面对选择列进行说明。

可以按列的名称来检索各列，如下所示：

在数据帧中，列的位置是确定的，可以通过指定列的位置取出各列，具体如下：

请注意，在这段代码中，我们正在检索DataFrame的前三行（一共有三行数据）。

选择行

数据帧中的每一行都对应着问题空间中的一个数据点。如果我们想要创建问题空间中数据元素的子集，则需要执行选择行操作。这个子集可以通过使用以下两种方法之一来创建：

• 指定各行的位置
• 指定一个过滤器

通过位置来检索各行的子集，具体操作如下：

注意，上面的代码将返回前两行以及所有列。

如果要通过指定过滤器来创建子集，需要使用一个或多个列来定义选择标准。例如，可以通过如下的方法选择数据元素的子集：

请注意，这段代码创建了由所有满足过滤器中规定条件的行所组成的子集。

2.1.6　矩阵

矩阵是一种具有固定列数和行数的二维数据结构，矩阵中的每个元素都可以通过指定它的列和行来引用。

在Python中，可以通过使用numpy中的array函数来创建矩阵，如下面的代码所示：

上面的代码创建了一个三行三列的矩阵。

矩阵运算

有很多运算可以用于矩阵数据。例如，我们尝试对前面创建的矩阵进行转置，可以使用transpose()函数，将列转换成行、行转换成列：

需要注意的是，在多媒体数据处理中经常使用矩阵运算。

前面已经学习了Python中的数据结构，我们下面学习抽象数据类型。