运行时更改数据结构表示：寻找其他例子

Question

哪些程序/算法在运行时更改其数据结构表示以获得更好的性能？

背景： 数据结构“定义”了现实世界中的概念在计算机内存中的结构和表示方式。对于不同类型的计算，应该/可以使用不同的数据结构以实现可接受的性能（例如，链表与数组实现）。

自适应（与自我更新相对）数据结构是根据具体使用模式更改其内部状态的数据结构（例如，自平衡树）。这些更改是内部的，即取决于数据。此外，这些更改是按设计预期进行的。

其他算法可以从外部的表示形式更改中受益。例如，在矩阵乘法中，转置“第二个矩阵”（以便高效地使用缓存）是一个众所周知的性能技巧。这实际上是将矩阵表示从行优先顺序更改为列优先顺序。因为“A”与“Transposed（A）”不同，所以在乘法后再次对第二个矩阵进行转置，以保持程序语义的正确性。

第二个例子是在程序启动时使用链表填充“数据结构”，并在列表内容变得“稳定”后更改为基于数组的实现。

我正在寻找在其应用程序中执行外部表示形式更改的类似经验的程序员，以便在程序的显式部分更改数据结构的表示（选择实现方式）时获得更好的性能。

- madewael

---

我认为这是一个有趣的问题，但可悲的是，在现今的SO上，有趣的问题遭到了反对。无论如何，您可能会对朱迪树感兴趣，这些树已经被精心设计用于解决这种类型的问题。 - j_random_hacker

@j_random_hacker，事实上，有准则指导提问，并且事实上，这个问题没有遵循这些准则。当然，你可以同意或不同意这些准则-那将是一个观点。 - Daniel Daranas

“在我更详细地说明我实际上正在寻找什么之前”，您需要更详细地阐述问题，而不仅仅是概述您希望回答问题的人，而您实际上尚未提出问题。否则，这可能会被关闭或暂停，直到您这样做为止。 - Nuclearman

@Nuclearman，你能帮我改进一下我的问题吗？ - madewael

当您提到“外部表示的更改”时，您是否意味着添加附加组件、插件等行为？ - Peng Zhang

@Peng Zhang 我的意思是外部变化是程序的一部分，而不是数据结构的一部分。例如，自适应数据结构会改变表示，因为这就是它们所做的。矩阵乘法中第二个矩阵的转置是程序的一部分，即使让它运行更快。 - madewael

Answer 1

为了实现更高效的算法，转换输入表示模式在许多情况下都很常见。我甚至可以说这是一般设计高效算法的重要思路之一。以下是一些例子：

• 堆排序。它将原始输入列表转换为二叉堆（可能是最小堆），然后重复调用删除最小元素函数以获取已排序的列表元素。在渐进意义下，它与最快的基于比较的排序算法并列。

• 查找列表中的重复项。不改变输入列表，这需要O(n^2)的时间。但是如果可以对列表进行排序，或者将元素存储在哈希表或布隆过滤器中，则可以在O(n log n)的时间内或更快地查找所有重复项。

• 解线性规划问题。线性规划问题是一种具有许多经济学和其他应用的优化问题。解决LP中最重要的技术之一是对偶性，这意味着将原始LP转换为所谓的“对偶”LP，然后解决对偶LP。根据您的情况，解决对偶问题可能比解决原始（“原始”）LP要容易得多。 本书章节 从一个很好的原始/对偶LP的例子开始。

• 大整数或多项式乘法。目前已知的最快方法是使用FFT；请参阅 这里 或 这里 获取一些很好的描述。其基本思想是从您的多项式的通常表示（系数列表）转换为评估基础上的表示（在某些精心选择点处的该多项式的评估列表）。评估基础使得乘法变得微不足道——您只需将每对评估相乘即可。现在，您已经在评估基础上获得了乘积多项式，并且可以进行插值（与评估相反）以获取所需的系数。快速傅里叶变换(FFT)是执行评估和插值步骤的一种非常有效的方法，整个过程可能比直接使用系数更快。

• 最长公共子串。如果要查找出现在一堆文本文档中的最长子串，则其中最快的方法之一是从每个文档创建后缀树，然后将它们合并并找到最深的公共节点。

• 线性代数。通过将原始矩阵转换为诸如 Hermite正规形式或计算 QR分解等规范形式，可以最有效地执行各种矩阵计算。这些替代矩阵表示使标准操作，例如查找逆矩阵、行列式或特征值更快速地计算。

除了这些，肯定还有许多其他的例子，但我试图提出一些不同的例子。

- Dan R