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