C++ 查找表

引言

毫无疑问，查找表是编程中的一个基本概念，主要用于存储某些值，这些值在运行时已被预先计算好以便快速访问。在 C++ 中，查找表可以理解为一个数组或数据结构，它接收输入值并将其映射到相应的输出值。这些表以内存空间为代价来优化速度。在本文中，我们将讨论查找表在 C++ 中工作的各种方面。

问题陈述

通常，程序需要执行昂贵的数学计算，例如对数和三角函数。如果反复使用相同的输入，效率会很低；动态函数求值比每次重新计算这些函数要好。在实时系统或资源受限的环境中，计算资源可能不足，这种低效率更加明显。

例如，假设我们需要计算从 0 到 360 度的角的正弦值。与其每次需要时都重新计算每个角的正弦值，不如预先计算这些值并将它们存储在查找表中。之后，在运行时，每当需要特定角度的正弦值时，都可以简单地在表中查找，从而显著减少计算开销。

C++ 中查找表的实现

在 C++ 中，查找表通常使用数组或像 std::map 或 std::unordered_map 这样的数据结构来实现。实现的具体选择取决于表的大小、访问模式和内存限制等因素。

查找表的特性

C++ 中的查找表有几个特性。查找表的一些主要特性如下：

1. 预先计算的值：查找表包含特定函数或映射的预先计算的值。这些值是在线下计算并存储在表中，以便在程序执行期间稍后检索。
2. 基于索引的访问：查找表通常使用数组或关联数据结构实现，其中每个条目都有一个相应的索引或键值与之关联。为了找到给定问题的正确预先计算的答案，首先需要输入与该问题匹配的索引或键号，以便首先获得所需信息。
3. 快速检索：查找表允许快速检索预先计算的值，通常具有 O(1) 的时间复杂度。这使得它们在需要快速访问函数近似值或映射的情况下很有用。
4. 内存权衡：查找表通过牺牲内存来换取更快的运行时。它们通过保存预先计算的值来消除运行时重复计算的需要，但由于表本身占用了更多的内存空间。
5. 确定性行为：查找表保证了确定性行为，即预先计算的条目在程序执行期间不会改变。因此，最终结果在不同的程序运行中始终是一致的。
6. 精度控制：开发人员可以调整插值函数、输入值粒度、表大小等参数，以达到查找表所需的精度级别。在这方面，可以平衡所需精度和此类表所做的内存需求。
7. 应用通用性：查找表用于各种领域，包括信号处理、科学计算、图形渲染、游戏开发和优化算法。它们的效率提高了性能并简化了复杂的数学运算。
8. 离线初始化：状态表是在线下或在程序初始化期间初始化的，通常是一次性完成。这样做将计算密集型的初始化阶段与运行时执行分离开来，从而提高了整个程序的效率。
9. 易于使用：初始化后，查找表变得更易于使用，因为它们只需要输入值即可检索预先计算的结果。这种充分性有助于简化代码实现和维护，并最大程度地减少复杂性和潜在错误。
10. 可移植性：查找表可以在平台无关地实现，使其兼容各种编程语言、硬件架构和操作系统。它增强了代码的可重用性和互操作性。

程序 1：基于数组的查找表

数组提供了一种简单有效的方法来实现查找表，特别是当输入是连续整数或可以离散化时。例如，我们可以使用一个索引代表角度的数组，而相应的数组元素存储预先计算的 0 到 360 度角的正弦值，如果我们想为正弦值创建一个查找表。

输出

Sine of 45 degrees: 0.707107

说明

在此示例中，initialize_lookup_table 函数预先计算从 0 到 360 度的角的正弦值，并将它们存储在 sine_lookup_table 数组中。sine 函数从表中检索给定角度的预先计算的正弦值。

1. 包含指令

• #include <iostream>：它包含标准输入输出流库，对于输入和输出操作是必需的。
• #include <cmath>：它包含 C++ 数学函数库，该库提供了各种数学函数，如正弦 (std::sin)。

2. 宏定义

• #define ANGLE_RANGE 360：它定义了一个宏 ANGLE_RANGE，值为 360，表示将预先计算正弦值的角度范围。

3. 全局变量

• double sine_lookup_table[ANGLE_RANGE + 1];：它声明了一个全局数组 sine_lookup_table，能够存储从 0 到 360 度角度范围的预先计算的正弦值。

4. 函数定义

• void initialize_lookup_table()：此函数通过预先计算并将从 0 到 360 度的角的正弦值存储在 sine_lookup_table 来初始化查找表。
• double sine(double angle)：它确保角度在定义的范围内（0 到 360 度），并从查找表中检索相应的正弦值。此外，此函数以角度（以度为单位）作为输入，并返回与该角度对应的预先计算的正弦值。

5. Main 函数

• int main()：程序的主函数。
• initialize_lookup_table()：它调用 initialize_lookup_table 函数来预先计算并填充正弦查找表。
• double angle = 45.0;：它定义了一个示例角度（45 度），将计算其正弦值。
• std::cout << "Sine of " << angle << " degrees: " << sine(angle) << std::endl;：它打印角度及其通过 sine 函数获得的正弦值。

复杂度分析

时间复杂度

• 初始化时间（initialize_lookup_table）
• 初始化查找表的时间复杂度为 O(n)，其中 n 是表的大小 （ANGLE_RANGE + 1）。
• 对于从零到三百六十度的每一个度数，它都会在其查找表中的每个位置计算一次正弦值。
• 因此，初始化时间与表的大小成线性关系。
• 查找时间（sine 函数）
• 从表中查找正弦值的时间复杂度为 O(1)。

空间复杂度

• 保存查找表所需的空间为 O(n)，其中 n 是表的大小（ANGLE_RANGE + 1）。
• 向量中的任何索引都包含一个特定角度的预先计算的正弦值，该角度属于该范围。
• 表使用的内存量取决于其在任何给定时间的大小。
• 除了查找表之外，还有其他变量和函数调用的额外内存开销。
• 尽管如此，这些额外的内存需求通常比实际查找表所需的小。

总之，初始化查找表需要线性时间复杂度（O(n)），而其运行时始终是恒定的（O(1)）。此外，存储查找表具有线性空间复杂度（O(n)）。因此，这些复杂度表明，当通过增加执行速度来寻求性能优化但牺牲更多内存消耗时，这项技术是多么有效。

程序 2

让我们再举一个例子来说明 C++ 中的查找表。

输出

Approximate square root of 2: 1.41421

说明

• 在此示例中，我们指定了一个查找表 sqrt_lookup_table 来记录平方根值的预先计算的近似值。此数组的大小为 TABLE_SIZE + 1，这样每个元素都代表一个索引，表示我们想要计算其平方根的分数。
• initialize_sqrt_table 函数使用牛顿-拉夫逊方法来初始化查找表。它计算每个索引 i 的 √i/TABLE_SIZE 的初始猜测值，然后通过牛顿-拉夫逊方法进行固定次数的迭代 MAX_ITERATIONS 来完善此猜测值。
• sqrt_approx 函数以浮点数 x 作为输入，并使用查找表返回近似平方根。它为 x（输入值）分配表中的一个索引，然后检索预先计算的近似值。如果输入为负数，则返回 NaN（非数字）值。
• 我们还有一个主函数，它初始化查找表，演示其用法，并近似计算示例数字（num）的平方根。

复杂度分析

时间复杂度

• 初始化查找表的时间复杂度为 O(n * m)，其中 n 表示 TABLE_SIZE，m 表示 MAX_ITERATIONS。
• 牛顿-拉夫逊方法应用于 n 次迭代中的每个索引，固定迭代次数为 m。
• 因此，初始化时间复杂度与表大小和最大迭代次数的乘积成正比。
• 在表中搜索近似值所涉及的时间复杂度为 O(1)。
• 鉴于索引直接从输入 x 计算得出，然后在常数时间内可以从表中检索其相应的近似值。

空间复杂度

• O(n) 用于定义存储查找表（n 为 TABLE_SIZE）的空间复杂度。
• 其每个条目都包含某些最大值分数的预先计算的平方根近似值。
• 用于创建表的内存与其尺寸成正比。
• 除了查找表之外，还有用于存储其他变量和函数调用的额外内存开销。
• 鉴于此额外内存需求可能比查找表本身所需的小，因此影响不大。

查找表的优点

C++ 中的查找表有几个优点。C++ 中查找表的一些主要优点如下：

1. 性能提升：通过预先计算值并将它们存储在查找表中，显著减少了重复计算的计算开销，从而加快了执行时间。
2. 可预测的行为：由于查找表是预先计算的且是静态的，因此它们提供了确定性行为，消除了动态计算的变异。
3. 简单性：通过使用查找表，复杂的计算变得更容易，它们被分解成不太复杂的部件，使代码更易于阅读和维护。
4. 优化资源利用：可以实现内存权衡，因为开发人员可以根据可用的内存空间来决定存储查找表。增加内存使用发生在存储预先计算的值时；然而，这会大大节省计算资源，特别是在计算能力有限或性能至关重要的情况下。

陷阱和注意事项

1. 内存开销：在内存受限的环境中，查找表通过存储预先计算的值会消耗更多内存，这可能是不希望的。
2. 精度和准确性：由于在表初始化期间使用了有限精度算术或插值技术，预先计算的值可能会引入不准确之处。开发人员需要确认所需的精度级别与应用程序的精度相匹配。
3. 表大小和访问模式：必须选择好查找表的大小和访问模式，以在内存使用和性能之间取得平衡。对于非均匀访问模式，可以使用其他数据结构（如 map）代替。

缺点

C++ 中的查找表有几个缺点。C++ 中查找表的一些主要缺点如下：

1. 内存开销：查找表会消耗额外的存储空间来预先存储计算结果，可能会产生内存开销；这在内存有限的环境中或对于大型表来说可能是一个问题。相对于表的大小，内存使用量呈线性增长，这可能会导致更大的内存需求。
2. 存储复杂性：管理和存储广泛的查找表可能会使任务复杂化，尤其是在处理多维或稀疏数据时。为了设计用于表存储和检索的高效数据结构和算法，可能需要额外的优化工作。
3. 初始化：初始化查找表的时间可能在计算成本上很高，特别是对于复杂函数或基于大型数组的函数。如果预先计算的值是在线下或在程序初始化阶段生成的，启动时间可能会延迟。
4. 精度有限：查找表仅使用离散输入值来近似函数值。这些近似值的准确性可能有限，因为它取决于输入值的粒度和涉及的插值方法，从而导致精度损失。
5. 表大小选择和性能权衡：做出最优的表大小选择涉及在内存消耗和性能之间做出决定。通过增加表的大小，它们的精度会提高，但使用的内存量也会增加，而较小的表可能会通过牺牲一定的精度来换取更小的内存占用，从而影响效率。很难找到这种平衡。
6. 插值错误：查找表的设计方式是它们使用插值技术来近似预计算点之间的值。使用的插值方法可能会导致错误，尤其是在高曲率区域或存在突然变化的情况下。
7. 维护开销：在具有复杂依赖关系的大规模系统中，更改或更新查找表可能是一项繁琐的任务。因此，函数行为或输入要求的更改可能需要重新生成或重新校准查找表，从而导致维护开销。
8. 缓存效率低下：考虑到具有分层内存系统的计算机体系结构，从大型查找表中检索值可能在缓存使用方面效率低下。非连续模式的缓存未命中会导致低性能，因为它们是由非连续内存访问引起的。
9. 算法复杂性：算法复杂性源于查找表，特别是当函数近似涉及复杂的计算和非线性映射时。高效算法用于初始化、插值以及从表中检索信息。

结论

C++ 查找表在平衡内存消耗和性能方面非常有用。程序员可以预先计算值并将它们放入一个特殊的容器中，而不是反复计算相同的内容，以便能够快速访问它们，从而显著提高时间效率，特别是对于繁重的数值计算代码。然而，在不考虑内存限制、精度需求和访问策略的情况下盲目执行此操作，以获得最佳性能和正确的结果。