mad*_*ael 11 algorithm self-updating data-structures
哪些程序/算法在运行时更改其数据结构的表示以获得更好的性能？
上下文: 数据结构"定义"现实世界概念在计算机内存中的结构和表示方式.对于不同类型的计算,应该/可以使用不同的数据结构来实现可接受的性能(例如,链表与阵列实现).
自适应(参见自更新)数据结构是根据具体使用模式(例如,自平衡树)改变其内部状态的数据结构.这些变化是内部的,即取决于数据.而且,这些变化是通过设计预期的.
其他算法可以从表示的外部变化中受益.例如,在矩阵乘法中,转换"第二矩阵"是一种众所周知的性能技巧(这样可以更有效地使用缓存).这实际上是将矩阵表示从行主要顺序更改为列主要顺序.因为"A"与"Transposed(A)"不同,所以在乘法之后再次转置第二矩阵以保持程序在语义上正确.
第二个例子是在程序启动时使用链表来填充"数据结构",并在列表内容变为"稳定"后改为基于数组的实现.
我正在寻找与其他示例程序具有类似经验的程序员,其中在其应用程序中执行外部表示更改以获得更好的性能.因此,数据结构的表示(所选实现)在运行时作为程序的显式部分而改变.
在许多情况下都会出现转换输入表示以实现更有效的算法的模式。我什至可以说，这是思考设计高效算法的一种重要方式。我想到的一些例子：
堆排序。它的工作原理是将原始输入列表转换为二进制堆（可能是最小堆），然后重复调用remove-min函数以按排序顺序获取列表元素。渐近地，它与最快的基于比较的排序算法联系在一起。
在列表中查找重复项。在不更改输入列表的情况下，这将花费 O(n^2) 时间。但是，如果您可以对列表进行排序，或者将元素存储在哈希表或布隆过滤器中，则可以在 O(n log n) 时间内或更好的时间内找到所有重复项。
求解线性规划。线性规划 (LP) 是一种优化问题，在经济学和其他领域有许多应用。求解LP最重要的技术之一是对偶性，这意味着将原始LP转换为所谓的“对偶”，然后求解对偶。根据您的情况，解决对偶问题可能比解决原始（“原始”）LP 容易得多。本书章节以原始/对偶 LP 的一个很好的例子开始。
非常大的整数或多项式的乘法。已知最快的方法是使用 FFT；请参阅此处或此处了解一些不错的描述。这个想法的要点是将多项式的通常表示（系数列表）转换为评估基础（该多项式在某些精心选择的点处的评估列表）。评估基础使乘法变得微不足道 - 您只需将每对评估相乘即可。现在，您在评估基础上有了乘积多项式，并且可以像您想要的那样进行插值（与评估相反）以获取系数。快速傅立叶变换 (FFT) 是执行评估和插值步骤的一种非常有效的方法，整个过程比直接处理系数要快得多。
最长公共子串。如果您想找到一堆文本文档中出现的最长子字符串，最快的方法之一是从每个子字符串创建后缀树，然后将它们合并在一起并找到最深的公共节点。
线性代数。通过将原始矩阵转换为规范形式（例如Hermite 范式）或计算QR 分解，可以最有效地执行各种矩阵计算。矩阵的这些替代表示使得诸如查找逆矩阵、行列式或特征值之类的标准事物的计算速度更快。
除此之外当然还有很多例子，但我试图想出一些变化。