引言

在某种意义上，数据结构是算法的构建基础，对于任何AI或ML算法的有效运行都至关重要。这些结构，虽然通常被视为数据的简单容器，但实际上远不止于此：它们本身就是极其丰富的工具，对算法的性能、效率和整体计算复杂性产生的影响可能比人们想象的要大得多。因此，选择数据结构是一项需要深思熟虑的任务，它可以决定数据处理的速度、ML模型可以操作的规模，甚至特定计算问题的可行性。

本文旨在介绍在AI和ML领域中一些重要的数据结构，面向实践者、学生以及AI和ML爱好者。我们希望通过撰写本文，为大家提供AI和ML领域中重要数据结构的一些知识，以及一些关于如何有效地在最佳情况下使用这些结构的指导。

当我们逐一探讨一系列数据结构时，我们将给出AI和ML场景中可能使用这些结构的例子，每种结构都有其自身的优点和缺点。所有实现都将使用Python语言，因为Python在数据科学领域拥有巨大的普及度，并且适用于AI和ML中的各种任务。掌握这些核心构建块对于数据科学家可能面临的多种任务至关重要：例如，对大数据集进行排序、创建既快速又节省内存的高性能算法，以及以逻辑和高效的方式维护数据结构等。

在介绍了简单数组和动态数组的基础知识之后，我们将转向更高级的结构，如链表和二叉搜索树，最后以哈希表收尾，这是一种非常有用的结构，并且学习它的投资回报非常高。我们既涵盖了这些结构的机械构造，也介绍了它们在AI和ML应用中的实际使用，这种理论与实践的结合为读者提供了决定哪种结构最适合特定问题以及如何在稳健的AI系统中实现这些结构所需的理解。

在本文中，我们将深入探讨对AI和机器学习至关重要的各种数据结构，从数组和动态数组开始。通过了解每种数据结构的特性、优点和局限性，实践者可以做出明智的选择，从而提高AI系统的效率和可扩展性。

1、数组和动态大小数组

计算机科学中最基础的数据结构之一，数组是相同类型的元素的集合，这些元素存储在相邻的内存位置，允许直接随机访问每个元素。动态数组，类似于Python中的列表，在简单数组的基础上增加了自动调整大小的功能，当添加或删除元素时，会分配额外的内存。这种自动内存分配能力是动态数组的核心。使用数组的一些基本建议可能包括看似线性遍历数据的问题，或者元素数量完全不波动的情况，例如机器学习算法可能会处理的大小不变的数据集。

首先，我们讨论一下数组的优点：

• 通过索引轻松访问元素：快速检索操作，这在许多时间效率是关键的AI和ML场景中至关重要
• 适用于已知或固定大小的问题：当元素数量预先确定或变化不频繁时，数组是理想的选择

以下是数组的缺点：

• 固定大小（对于静态数组）：需要提前知道元素的最大数量，这可能会有限制
• 插入和删除成本高（对于静态数组）：每次插入或删除都可能需要移动元素，这在计算上很昂贵

数组，可能是因为它们易于理解且实用，在计算机科学教育中几乎无处不在；它们是课堂教学的自然主题。从计算机内存位置随机访问一个元素时具有O(1)或常量的时间复杂度，这使得它在运行时效率至上的系统中备受青睐。

在机器学习的世界中，数组和动态数组对于处理数据集至关重要，并且通常用于安排特征向量和矩阵。高性能数值库（如NumPy）使用数组与跨数据集高效执行任务的例程相结合，允许对训练模型所需的数值数据进行快速处理和转换，并用于预测。

使用Python内置的动态数组数据结构（列表）执行的一些基本操作包括：

# Initialization

my_list = [1, 2, 3]



# Indexing

print(my_list[0])        # output: 1



# Appending

my_list.append(4)        # my_list becomes [1, 2, 3, 4]



# Resizing

my_list.extend([5, 6])   # my_list becomes [1, 2, 3, 4, 5, 6]

2、链表

链表是另一种基本的数据结构，由一系列节点组成。列表中的每个节点都包含一些数据以及指向列表中下一个节点的指针。单向链表是列表中每个节点仅引用列表中下一个节点的链表，只允许向前遍历；而双向链表则同时包含对下一个节点和前一个节点的引用，能够进行向前和向后遍历。这使得链表成为某些任务中数组的替代选择。

链表的好处：

• 它们是动态的：链表的扩展或收缩不需要重新分配和移动整个结构的额外开销
• 它们支持节点的快速插入和删除：无需像数组那样进行节点移动

链表的不足：

• 元素存储位置的不确定性会导致较差的缓存情况，尤其是与数组相比
• 通过索引定位元素需要线性或更差的时间复杂度，需要从头部开始完全遍历，效率较低

链表尤其适用于元素数量不明确且需要频繁插入或删除的情况。这些应用使它们在需要动态数据、经常发生变化的情况下非常有用。事实上，链表的动态大小调整能力是它们的优点之一；它们显然非常适合于无法提前预测元素数量，并且可能导致大量浪费的情况。能够调整链表结构而无需进行整体复制或重写的巨大开销是一个明显的优势，特别是在需要经常调整数据结构的情况下。

尽管链表在AI和ML领域中的实用性不如数组，但它们确实在需要高度可变数据结构且需要快速修改的情况下找到了特定的应用，例如管理遗传算法中的数据池或其他需要经常对单个元素执行操作的情况。

我们要不要来一个链表操作的简单Python实现？当然可以。请注意，以下基本的链表实现包括一个Node类来表示列表中的每个元素，以及一个LinkedList类来处理列表上的操作，包括添加和删除节点。

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None



class LinkedList:

    def __init__(self):

        self.head = None



    def append(self, data):

        new_node = Node(data)

        if not self.head:

            self.head = new_node

            return

        last = self.head

        while last.next:

            last = last.next

        last.next = new_node



    def delete_node(self, key):

        temp = self.head

        if temp and temp.data == key:

            self.head = temp.next

            temp = None

            return

        prev = None

        while temp and temp.data != key:

            prev = temp

            temp = temp.next

        if temp is None:

            return

        prev.next = temp.next

        temp = None



    def print_list(self):

        current = self.head

        while current:

            print(current.data, end=' ')

            current = current.next

        print()

以下是上述代码的说明：

• 这个LinkedList类负责管理链表，包括链表的创建、添加数据、删除节点和显示链表。当它被初始化时，会创建一个头指针head，并默认标记为一个空链表。

• append方法负责在链表的末尾添加数据。如果链表为空，它会在链表的头部创建一个新节点；如果链表非空，它会遍历到链表的末尾来添加新节点。

• delete_node方法负责根据给定的键（数据）删除节点，它会考虑以下三种情况：目标键在头节点中；目标键在链表中的另一个节点中；没有节点包含该键。通过正确设置指针，它能够在不牺牲剩余节点顺序的情况下移除一个节点。

• print_list方法从头节点开始遍历链表，按顺序打印每个节点的内容，从而提供了一种简单的方法来理解链表的内容。

下面是一个上述LinkedList代码的使用示例：

# Create a new LinkedList

my_list = LinkedList()



# Append nodes with data

my_list.append(10)

my_list.append(20)

my_list.append(30)

my_list.append(40)

my_list.append(50)



# Print the current list

print("List after appending elements:")

my_list.print_list()       # outputs: 10 20 30 40 50



# Delete a node with data '30'

my_list.delete_node(30)



# Print the list after deletion

print("List after deleting the node with value 30:")

my_list.print_list()       # outputs: 10 20 40 50



# Append another node

my_list.append(60) 



# Print the final state of the list

print("Final list after appending 60:")

my_list.print_list()       # outputs: 10 20 40 50 60

3、树，特别是二叉搜索树（BST）

树是非线性数据结构（与数组相比）的一个例子，其中节点之间存在父子关系。每棵树都有一个根节点，并且节点可以包含零个或多个子节点，以分层结构组织。二叉搜索树（BST）是一种特殊的树，它允许每个节点最多包含两个子节点，通常称为左子节点和右子节点。在这种类型的树中，节点中包含的键必须分别大于或等于其左子树中包含的所有节点的键，或者小于或等于其右子树中包含的所有节点的键。这些BST的属性可以在树保持平衡的情况下促进更有效的搜索、插入和删除操作。

BST的优点：

• 与更常用的数据结构（如数组或链表）相比，BST提供了更快的访问、插入和删除操作。

BST的缺点：

• 但是，之前提到过，当BST不平衡/倾斜时，性能会降低。
• 这可能导致操作时间复杂度在最坏情况下退化到O(n)。

BST在处理数据集时，对于许多搜索、插入或删除操作特别有效。当数据集频繁变化并且数据频繁访问时，它们当然更合适。

此外，树是描述层次数据的理想结构，以创建数据之间的树状关系，如文件系统或组织结构图。这使得它们在需要这种层次数据结构化的应用中特别有用。

BST能够确保搜索操作是快速的，因为它们对于访问、插入和删除操作的平均时间复杂度为O(log n)。这使得它们在需要快速数据访问和更新的应用中特别受关注。

决策树是一种广泛用于机器学习中分类和回归任务的树形数据结构，它使模型能够根据由特征确定的规则来预测基于目标变量的结果。树结构也在人工智能中得到了广泛的应用，例如游戏编程；特别是在像国际象棋这样的策略游戏中，树被用来模拟场景并确定决定最优走法的约束条件。

下面是一个使用Python实现基本二叉搜索树（BST）的概述，包括插入、搜索和删除方法：

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key



def insert(root, key):

    if root is None:

        return TreeNode(key)

    else:

        if root.val < key:

            root.right = insert(root.right, key)

        else:

            root.left = insert(root.left, key)

    return root



def search(root, key):

    if root is None or root.val == key:

        return root

    if root.val < key:

        return search(root.right, key)

    return search(root.left, key)



def deleteNode(root, key):

    if root is None:

        return root

    if key < root.val:

        root.left = deleteNode(root.left, key)

    elif(key > root.val):

        root.right = deleteNode(root.right, key)

    else:

        if root.left is None:

            temp = root.right

            root = None

            return temp

        elif root.right is None:

            temp = root.left

            root = None

            return temp

        temp = minValueNode(root.right)

        root.val = temp.val

        root.right = deleteNode(root.right, temp.val)

    return root



def minValueNode(node):

    current = node

    while current.left is not None:

        current = current.left

    return current

上述代码的说明：

• 二叉搜索树的基础是TreeNode类，它包含节点的值（val）和指向其左子节点和右子节点的指针（left和right）。

• insert函数是二叉搜索树中插入值的递归策略的实现：在基础情况下，如果没有根节点，则创建一个新的TreeNode；否则，它将比自身大的键放到右子树中，将比自身小的节点放到左子树中，以保持BST的结构。

• search函数处理两种情况的基础情况：找不到具有指定值的节点和找不到指定根节点的值，然后根据与当前节点比较的值在正确的子树中进行递归搜索。

• delete_node方法可以分为三种情况：类似删除没有子节点的键（用右子节点替换）；没有右子节点（用左子节点替换）；以及删除有两个子节点的节点（用其“中序后继者”，即其右子树中的最小值）替换，进行递归节点删除并维持BST的结构。

• 一个辅助函数是查找子树中的最小值节点（即最左边的节点），这在删除有两个子节点的节点时会被用到。

以下是上述BST代码实现的一个使用示例。

# Create the root node with an initial value

root = TreeNode(50)



# Insert elements into the BST

insert(root, 30)

insert(root, 20)

insert(root, 40)

insert(root, 70)

insert(root, 60)

insert(root, 80)



# Search for a value

searched_node = search(root, 70)

if searched_node:

    print(f"Found node with value: {searched_node.val}")

else:

    print("Value not found in the BST.")



# output -> Found node with value: 70



# Delete a node with no children

root = deleteNode(root, 20)



# Attempt to search for the deleted node

searched_node = search(root, 20)

if searched_node:

    print(f"Found node with value: {searched_node.val}")

else:

    print("Value not found in the BST - it was deleted.")



# output -> Value not found in the BST - it was deleted.

4、哈希表

哈希表是一种非常适合快速数据访问的数据结构。它们利用哈希函数计算一系列槽位或桶的索引，并从中返回所需的值。哈希表由于这些哈希函数而能够提供几乎即时的数据访问，并且可以扩展到大型数据集而不会降低访问速度。哈希表的效率在很大程度上依赖于哈希函数，该函数将条目均匀分布在桶数组中。这种分布有助于避免键冲突，即不同的键解析到同一个槽位；适当的键冲突解决是哈希表实现的核心关注点。

哈希表的优点：

• 快速数据检索：为查找、插入和删除提供了平均情况下的常数时间复杂度（O(1)）
• 平均时间复杂度效率高：大多数情况下都相当迅速，这使得哈希表非常适合一般的实时数据处理

哈希表的缺点：

• 最坏情况时间复杂度不佳：如果有许多项哈希到同一个桶，性能可能退化为O(n)
• 依赖于良好的哈希函数：哈希函数对哈希表性能的重要性非常显著，因为它直接影响数据在桶之间的分布

哈希表通常用于需要快速查找、插入和删除操作，而不需要有序数据的情况。当需要通过其键快速访问项以加快操作时，它们特别有用。哈希表对于其基本操作的常数时间复杂度属性使得它们在需要高性能操作的情况下非常有用，尤其是在时间至关重要的情况下。

哈希表非常适合处理大量数据，因为它们提供了一种高速的数据查找方式，而且随着数据量的增长，性能不会下降。人工智能经常需要处理大量数据，其中使用哈希表进行检索和查找非常有意义。

在机器学习中，哈希表有助于对大型数据集进行特征索引——在预处理和模型训练过程中，通过哈希表可以方便地实现快速访问和数据操作。哈希表还可以使某些算法更加高效——在某些情况下，在k近邻计算中，它们可以存储已经计算过的距离，并从哈希表中检索它们，以加快大型数据集的计算速度。

在Python中，字典类型就是哈希表的一种实现。下面将解释如何利用Python字典，并介绍一种处理冲突的策略：

# Creating a hash table using a dictionary

hash_table = {}



# Inserting items

hash_table['key1'] = 'value1'

hash_table['key2'] = 'value2'



# Handling collisions by chaining

if 'key1' in hash_table:

    if isinstance(hash_table['key1'], list):

        hash_table['key1'].append('new_value1')

    else:

        hash_table['key1'] = [hash_table['key1'], 'new_value1']

else:

    hash_table['key1'] = 'new_value1'



# Retrieving items

print(hash_table['key1'])



# output: can be 'value1' or a list of values in case of collision



# Deleting items

del hash_table['key2']

结论

对支撑AI和机器学习模型的几种数据结构的调查可以向我们展示这些底层技术相对简单的构建模块所具备的一些能力。数组的内在线性特性、链表的适应性、树的层次化组织和哈希表的O(1)搜索时间各自提供了不同的优势。这种理解可以告知工程师如何最好地利用这些结构——不仅是在他们构建的机器学习模型和训练集中，而且在他们选择和实施背后的推理中。

掌握与机器学习和AI相关的基本数据结构是一项有深远影响的技能。有许多地方可以学习这种技能组合，从大学到研讨会再到在线课程。甚至开源代码也可以成为熟悉学科工具和最佳实践的宝贵资产。与数据结构一起工作的实践能力不容忽视。因此，对于当今、未来以及之后的数据科学家和AI工程师们：练习、实验，并从可用的数据结构材料中学习。