Chapter 2
第2章
算法中的数据结构

算法需要必要的内存数据结构用于执行时保存临时数据。选择恰当的数据结构对算法高效执行至关重要。某些类别的算法在逻辑上是递归的或迭代的，需要使用专门为这种算法设计的数据结构。例如，如果使用嵌套的数据结构，递归算法可能更容易实现，并且表现出更好的性能。本章在算法背景下讨论数据结构。本书用Python来描述算法，所以本章重点讨论Python中的数据结构，但所介绍的概念也适用于Java和C++等其他编程语言。

通过本章学习，你应该能够理解Python如何处理复杂的数据结构，并能够为特定种类的数据选用合适的数据结构。

本章涵盖以下主题：

❑ 探讨Python中的数据结构。

❑ 使用序列和数据帧。

❑ 探索矩阵和矩阵运算。

❑ 理解抽象的数据类型。

2.1 探讨Python中的数据结构

任何编程语言中，数据结构都用于存储和操作复杂的数据。在Python中，数据结构是用于以高效方式管理、组织和搜索数据的存储容器。它们用于存储成组出现的数据元素，这些数据元素需要一起被存储和处理，每一组这样的数据称为一个 集合 。在Python中，可以用于存储集合的重要数据结构总结如表2.1所示。

我们将在后续部分更详细地了解它们。

2.1.1 列表

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

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

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

使用列表

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

我们看看如何使用列表：

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

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

现在，我们将运行以下代码：

注意，Python是一种零索引语言。这意味着任何数据结构的初始索引都将为0，包括列表。Green是第二个元素，通过索引1检索，即bin_color[1]。

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

注意，list是Python中最普遍的一维数据结构之一。

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

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

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

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

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

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

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

注意，前面的代码会遍历该列表并打印每个元素。现在让我们使用pop ()函数从栈中删除最后一个元素。

修改列表：追加和弹出操作

让我们来看看如何修改一些列表，包括追加和弹出操作。

使用 append() 方法添加元素

当你想要在列表的末尾插入一个新元素时，可以使用append()方法。它通过将新元素添加到最近可用的内存位置来实现。如果列表已经达到了最大容量，Python会扩展内存分配，复制先前的元素到这个新开辟的空间，然后插入新的添加项：

使用 pop() 方法移除元素

要从列表中提取一个元素，特别是最后一个元素，pop()方法是一个方便的工具。当调用时，该方法会提取指定的项（如果没有给出索引，则提取最后一项）。被弹出的元素之后的元素将重新定位以保持内存的连续性：

Range()函数

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

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

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

上面的range函数给出从3到29的奇数。

要遍历一个列表，我们可以使用for函数：

我们可以使用range()函数来生成一个随机数列表。例如，为了模拟一个骰子的十次试验，我们可以使用以下代码：

列表的时间复杂度

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

❑ 插入一个元素：在列表的末尾插入一个元素通常具有恒定的时间复杂度，记为 O (1)。这意味着，无论列表的大小如何，此操作所需的时间都保持相当一致。

❑ 删除元素：在最坏的情况下，从列表中删除元素的时间复杂度可能为 O ( n )。这是因为，在最不利的情况下，程序可能需要在删除所需的元素之前遍历整个列表。

❑ 切片：当我们对列表进行切片或提取列表的一部分时，操作需要的时间与切片的大小成比例。因此，它的时间复杂度是 O ( n )。

❑ 元素检索：在没有任何索引的情况下，在列表中查找一个元素，在最坏的情况下，可能需要扫描其所有元素。因此，它的时间复杂度也是 O ( n )。

❑ 复制：创建列表的副本需要访问每个元素一次，从而使得时间复杂度为 O ( n )。

2.1.2 元组

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

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

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

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

元组的时间复杂度

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

❑ 访问元素：元组允许通过索引直接访问它们的元素。这个操作是常数时间， O (1)，这意味着无论元组的大小如何，所花费的时间都保持一致。

❑ 切片：当一个元组的一部分被提取或切片时，操作的效率与切片的大小成正比，使得时间复杂度为 O ( n )。

❑ 元素检索：在没有任何索引辅助程序的情况下，搜索元组中的元素，在最坏的情况下，可能需要遍历其所有元素。因此，它的时间复杂度为 O ( n )。

❑ 复制：复制一个元组或创建其副本，需要遍历每个元素一次，从而使其时间复杂度为 O ( n )。

2.1.3 字典和集合

在本小节中，我们将讨论集合和字典，它们用于存储没有明确或隐含顺序的数据。字典和集合都非常相似。区别在于字典有键值对，而集合可以被看作唯一键的集合。

让我们逐个来看一下它们。

字典

以键值对的形式保存数据是非常重要的，尤其是在分布式算法中。在Python中，这些键值对的集合被存储为一个称为字典（Dictionary）的数据结构。要创建一个字典，应该选择一个在整个数据处理过程中最适合识别数据的属性作为键。对键的值有一个限制，即它们必须是可散列的类型。可散列是指那种可以对其运行散列函数，且在其生命周期内生成的散列码永远不会改变的对象类型。这确保了键的唯一性，并且查找键的速度很快。数值类型和扁平不可变类型都是可散列的，是字典键的良好选择。值可以是任何类型的元素，例如，数字或字符串，Python还总是使用复杂的数据类型（如列表）作为值。如果用字典作为值的数据类型，则可以创建嵌套字典。

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

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

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

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

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

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

在遍历字典时，通常我们需要同时获取键和值。在Python中，我们可以使用.items()来遍历字典：

要从字典中删除一个元素，我们可以使用del函数：

字典的时间复杂度

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

❑ 通过键访问值：字典被设计用于快速查找。当你有了键之后，访问相应的值通常是一个常数时间操作，即 O (1)。除非发生散列冲突，但这种情况很少发生。

❑ 插入键值对：添加一个新的键值对通常是一个快速的操作，时间复杂度为 O (1)。

❑ 删除键值对：当键已知时，从字典中删除一个条目通常也是一个平均时间复杂度为 O (1)的操作。

❑ 搜索键：由于散列机制的存在，验证键的存在通常是一个常数时间 O (1)的操作。然而，在最坏情况下，特别是在发生许多散列冲突时，这可能会升级到 O ( n )。

❑ 复制：创建字典的副本需要遍历每个键值对，使得时间复杂度为线性的 O ( n )。

集合

与字典密切相关的是集合，它被定义为一个无序的、不同元素的集合，这些元素可以是不同类型的。定义集合的一种方式是将值放在{}中。例如，看一下以下代码块：

集合的定义特征是它只存储每个元素的唯一值。如果我们尝试添加另一个冗余的元素，它会忽略那个，如下所示：

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

❑ 一个集合名为yellow，里面包含了黄色的东西。

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

请注意，这两组之间有些公共部分。这两组及其关系可以借助如图2.3所示的维恩图来进行展示。

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

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

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

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

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

由于集合是无序的，集合中的项没有索引。这意味着我们不能通过引用索引来访问集合中的项。

我们可以使用for循环遍历集合中的项：

我们还可以使用关键字in来检查集合中是否存在指定的值。

集合的时间复杂度分析

表2.2是集合的时间复杂度分析。

何时使用字典，何时使用集合

假设我们正在寻找一个数据结构来存储我们的电话簿信息。我们想要存储一家公司员工的电话号码。对于这个目的，字典是合适的数据结构。每个员工的姓名将作为键，电话号码将作为值：

但是如果我们只想存储员工的唯一值，那么应该使用集合来实现：

2.1.4 使用序列和数据帧

数据处理是实现大多数算法时需要完成的核心任务之一。在Python中，通常使用pandas库的各种函数和数据结构来进行数据处理。

在本小节中，我们将介绍pandas库的以下两个重要数据结构，这些数据结构将在本书的后续部分用于实现各种算法：

❑ 序列： 一个包含数值的一维数组

❑ 数据帧： 用于存储表格数据的二维数据结构

让我们首先来看一下序列数据结构。

序列

在pandas库中，序列是用于存储同质数据的一维数组。我们可以将序列视为电子表格中的单个列，也可以将其视为存储特定变量的各种值。

一个序列可以这样定义：

请注意，在pandas的基于序列的数据结构中，有一个名为“axis”的术语，用于表示特定维度中的一系列值。序列只有“axis 0”，因为它只有一个维度。接下来我们将看到这个轴概念如何应用在数据帧上。

数据帧

数据帧（DataFrame）是建立在序列数据结构之上的。它以二维表格数据的形式存储，用于处理传统结构化数据。让我们考虑以下表格。

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

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

请注意，在上面的代码中，df.column是一个列名列表。在数据帧中，单独的一列或一行被称为一个轴。

创建数据帧的子集

基本上，创建数据帧的子集的主要方法有两种：

❑ 列选择

❑ 行选择

让我们逐一看一下。

列选择

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

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

在数据帧中，列的位置是确定性的。可以通过其位置检索列，如下所示：

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

行选择

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

❑ 指定它们各行的位置

❑ 指定一个过滤器

通过其位置来取出各行的子集，具体操作如下：

请注意，上述代码将返回第二行和第三行以及所有列。它使用了iloc方法，该方法允许我们通过其数值索引访问元素。

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

请注意，此代码创建了一个满足筛选条件的行子集。

数据帧的时间复杂度分析

让我们揭示一些基本数据帧操作的时间复杂度。

❑ 选择操作

➢ 列选择： 访问数据帧的列，通常使用方括号表示法或点符号表示法（对于没有空格的列名），是一个 O (1)操作。它提供了快速引用数据而不进行复制。

➢ 行选择： 使用像.loc[]或.iloc[]这样的方法来选择行，尤其是使用切片，其时间复杂度为 O ( n )，其中“ n ”表示要访问的行数。

❑ 插入操作

➢ 列插入： 向数据帧添加新列通常是一个 O (1)的操作。然而，实际的时间可能会根据要添加的数据类型和数据大小而变化。

➢ 行插入： 使用.append()或.concat()等方法添加行通常会导致 O ( n )的时间复杂度，因为它通常需要重新排列和重新分配空间。

❑ 删除操作

➢ 列删除： 从数据帧中删除列，通过.drop()方法实现，是一个 O (1)的操作。它标记列以便进行垃圾回收，而不是立即删除。

➢ 行删除： 与行插入类似，行删除可能导致 O ( n )的时间复杂度，因为数据帧需要重新调整其结构。

2.1.5 矩阵

矩阵（Matrix）是一个二维数据结构，具有固定数量的列和行。矩阵中的每个元素可以通过其列和行来引用。

在Python中，可以使用numpy数组或列表来创建矩阵。但是，由于numpy数组是由位于连续内存位置上的同类数据元素组成的，所以它们比列表要快得多。在Python中，可以通过使用numpy数组中的array函数来创建矩阵，如下面的代码所示：

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

矩阵运算

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

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

大 O 记号和矩阵

在讨论操作的效率时，大 O 记号提供了一个高层次的理解，说明随着数据规模增长，操作的影响如何。

❑ 访问： 访问一个元素，无论是在Python列表还是numpy数组中，都是一个常数时间操作， O (1)。这是因为通过元素的索引，你可以直接访问它。

❑ 追加： 在Python列表的末尾添加一个元素是平均情况下的 O (1)操作。然而，对于numpy数组，在最坏情况下，这个操作可能是 O ( n )，因为如果没有连续可用的空间，整个数组可能需要被复制到一个新的内存位置。

❑ 矩阵乘法： 这是numpy的优势所在。矩阵乘法可能具有较高的计算复杂度。传统方法对于 n × n 矩阵的时间复杂度可能为 O ( n ³ )。然而，numpy使用了优化算法，比如Strassen算法，显著降低了这个复杂度。

现在我们已经学习了Python中的数据结构，让我们在下一节继续学习抽象数据类型。

2.2 探索抽象数据类型

抽象数据类型（ADT）是高级抽象，其行为由一组变量和一组相关操作定义。ADT定义了“预期发生什么”，但在“如何”实际实现方面给予程序员自由。示例包括向量、队列和栈。这意味着两个不同的程序员可以采用两种不同的方法来实现ADT，比如栈。通过隐藏实现级别的细节，并为用户提供通用的、与实现无关的数据结构，ADT的使用可以创建简单、清晰的代码。ADT可以在任何编程语言中实现，比如C++、Java和Scala。在本节中，我们将使用Python实现ADT。让我们先从向量（Vector）开始。

2.2.1 向量

向量（Vector）是用于存储数据的单维结构。它们是Python中最流行的数据结构之一。在Python中有两种创建向量的方式，如下所示：

❑ 使用Python列表： 创建向量的最简单方式是使用Python列表（List），如下所示：

请注意，这段代码将创建一个包含四个元素的列表。

❑ 使用numpy的array：创建向量的另一个流行方式是使用numpy的array。numpy的array通常比Python列表更快、更节省内存，特别是对涉及大量数据的操作而言。这是因为numpy设计用于处理同质数据，并且可以利用底层优化。可以按以下方式实现numpy的array：

请注意在这段代码中我们使用np.array创建了名为Vector_2的向量。

向量的时间复杂度

在讨论向量操作的效率时，了解时间复杂度是至关重要的：

❑ 访问： 在Python列表和numpy数组（向量）中访问一个元素都需要常数时间 O (1)，这确保了快速的数据检索。

❑ 追加： 向Python列表追加一个元素的平均时间复杂度为 O (1)。然而，对于numpy数组，由于numpy数组需要连续的内存位置，追加操作在最坏情况下可能需要高达 O ( n )的时间复杂度。

❑ 搜索： 在向量中查找一个元素的时间复杂度为 O ( n )，因为在最坏情况下，你可能需要扫描所有元素。

2.2.2 栈

栈（Stack）是一种线性数据结构，用于存储一维列表。它可以以 后进先出（LIFO） 或 先进后出（FILO） 的方式存储项目。栈的定义特征在于元素添加到其中和从中移除的方式。新元素被添加到一端，而元素只能从该端移除。

以下是与栈有关的操作：

❑ isEmpty： 如果栈为空则返回true

❑ push： 添加一个新的元素

❑ pop： 返回最近添加的元素并将其从栈中删除

图2.4显示了如何使用推送（push）和弹出（pop）操作从栈中添加和删除数据。

图2.4的顶部显示了使用push操作向栈添加元素项的情况。在步骤1.1、1.2和1.3中，push操作被使用三次向栈添加三个元素。图2.4的下半部分用于从栈中取出所存储的值，在步骤2.2和2.3中，pop操作以后进先出LIFO方式从栈中取出了两个元素。

下面，我们在Python中创建一个名为Stack的类，并在这里定义所有与栈（stack）相关的操作。这个类的代码如下：

要将四个元素推送到栈中，可以使用以下代码：

注意，上图的代码创建了一个有四个数据元素的栈。

栈的时间复杂度

我们看看栈的时间复杂度（使用大 O 记号）：

❑ 推送：这个操作将一个元素添加到栈的顶部。由于它不涉及任何迭代或检查，推入操作的时间复杂度为 O (1)，即常数时间。无论栈的大小如何，元素都会被放置在顶部。

❑ 弹出：弹出是指从栈中移除顶部元素。由于不需要与栈的其余部分进行交互，因此弹出操作的时间复杂度也为 O (1)。这是对顶部元素的直接操作。

实例

栈在许多用例中被用作数据结构。例如，当用户想要浏览网络浏览器中的历史记录时，这是一种后进先出的数据访问模式，可以使用栈来存储历史记录。另一个例子是当用户想要在文字处理软件中执行撤销操作时。

2.2.3 队列

与栈类似，队列（Queue）将 n 个元素存储在单维结构中。这些元素按照先进先出的格式进行添加和移除。队列的一端称为后端（Rear），另一端称为前端（Front）。当从前端移除元素时，该操作称为出队（dequeue）。当在后端添加元素时，该操作称为入队（enqueue）。

图2.5的顶部部分展示了入队操作。步骤1.1、1.2和1.3向队列中添加了三个元素，结果队列显示在1.4中。请注意，此时， Yellow 为队尾（Rear）， Red 为队首（Front）。

图2.5的下半部分展示了出队（dequeue）操作。步骤2.2、2.3和2.4从队列的队首逐一移出队列中的元素。

图2.5所展示的队列可以使用如下代码来实现：

让我们使用以下代码来执行图2.5中展示的入队和出队操作：

请注意，上述代码首先创建了一个队列，然后将四个项入队到队列中。

队列的时间复杂度分析

让我们来研究一下队列的时间复杂性：

❑ 入队：这个操作将一个元素插入到队列的末尾。由于它的直接性质，无须进行迭代或遍历，因此入队操作的时间复杂度为 O (1)——常数时间。

❑ 出队：出队意味着从队列中移除前端元素。由于该操作仅涉及第一个元素，而无须进行任何检查或迭代遍历整个队列，因此其时间复杂度保持在 O (1)的常数级别。

使用栈和队列背后的基本思想

让我们通过一个类比来探讨使用栈和队列的基本概念。假设我们有一张桌子，我们把从邮局（比如加拿大邮政）寄来的信件放在上面，我们将这些信件堆叠起来，直到有时间逐封地打开查看。有两种可能的方式来处理这些信件：

❑ 我们把信件放在一个栈中，每当收到一封新信件，我们将其放在栈的顶部。当我们想要阅读一封信时，我们从顶部开始。这就是我们所说的 栈 。请注意，最新到达的信件将位于顶部，并且将首先被处理。从信件列表顶部取出一封信称为弹出（pop）操作。每当新信件到达时，将其放在顶部称为推送（push）操作。如果我们最终拥有一个庞大的栈，并且不断有大量信件到达，则我们可能永远没有机会处理在信件堆的底端等待我们的非常重要的信件。

❑ 我们把信件放在一堆中，但我们希望先处理最旧的信件；每当我们想查看一封或多封信时，我们都要确保先处理最旧的那一封。这就是我们所说的 队列 。向堆中添加一封信称为入队（enqueue）操作。从堆中移除一封信称为出队（dequeue）操作。

2.2.4 树

在算法的背景下，树（Tree）是一种非常有用的数据结构，因为它具有分层数据存储能力。在设计算法时，我们会在需要表示数据元素之间的分层关系的地方使用树来存储或处理数据。

我们深入了解一下这个有趣且相当重要的数据结构。

每棵树都有有限个节点，起始数据元素对应的节点被称为根节点，所有节点通过连接关系组织在一起，连接也被称为分支。

术语

我们来看看与树这种数据结构相关的一些术语。

树的种类

树有不同的种类，下面将分别进行解释：

❑ 二叉树： 如果一棵树的度数是2，那么这棵树被称为二叉树（二元树）。例如，图2.6所展示的树就是一棵二叉树，因为它的度数是2。

上图所展示的是一棵有四层和八个节点的树。

❑ 满树： 满树是指所有非叶节点度都等于相同值的树，这个值就是树的度。图2.7展示了前面讨论的树的种类。

请注意，最左边的二叉树不是满树，因为节点 C 的度数是1，其他节点的度数都是2。中间的树和右边的树都是满树。

❑ 完美树： 完美树是一种特殊类型的满树，其中所有的叶节点都位于同一层。例如，上图中最右侧图所展示的二叉树就是一棵完美的满树，因为所有的叶子结点都在同一层，即 第2层 。

❑ 有序树 ：如果一个节点的子节点按照特定的标准以某种顺序排列，则称为 有序树 。例如，一棵树可以从左到右按升序排列，其中同一层的节点在从左到右遍历时，其值会递增。

实例

树这种抽象数据类型是开发决策树的主要数据结构之一，这一点将在第7章“传统的监督学习算法”中讨论。由于它的层次结构，它在网络分析的相关算法中也很受欢迎，这一点将在第6章“无监督机器学习算法”中详细讨论。树也被用于各种需要实现分治策略的搜索和排序算法中。

2.3 小结

在本章中，我们讨论了可以用来实现各种类型算法的数据结构。通过学习本章内容，你现在应该能够选择正确的数据结构来存储和处理算法中的数据。你还应该能够理解我们选择对算法性能的影响。

第3章将介绍排序和搜索算法，在这些算法的实现中，我们将使用本章介绍的一些数据结构。 7djSFZ6FyZincXRuz13pu/bQxdNNMIj8DRSToSiRA77ymO2RJVSJ6MPVLPMKVCih