algorithm - 就像有缓存遗忘和缓存优化算法一样，是否有寻求最佳算法？

Question

缓存（遗忘|最佳|感知）算法通常会在其模型中考虑寻道时间。如果没有，是否有考虑寻道时间的模型示例，以及该模型中的算法分析。

Answer 1

是的，我亲自编写了寻求敏感算法。文件系统当然使用搜索敏感数据结构（类似于算法）。

例如，NTFS（和许多其他文件系统）以B-tree格式存储数据，以最大限度地减少搜索并优化顺序读取。

不幸的是，当固态驱动器和其他技术即将完全取代旋转介质时，您在 2014 年提出了这个问题。SSD 确实会遭受一些寻道损失，但它们每秒可以处理数万次寻道，而旋转 HDD 可能每秒甚至无法处理 100 次寻道。这使得寻找问题比过去几年少得多。

一个类似且更相关的问题是 CPU 上的高速缓存行一致性。RAM 速度跟不上 CPU 速度，多核 CPU 使NUMA成为真正的性能问题。为了优化性能，许多算法实现都被推动使用尽可能少的内存，并且使用近处内存而不是远处内存。

例如，堆数据结构比树更易于缓存。当这是一个实际的选择时，性能敏感的代码将选择使用堆而不是树。

至少在过去十年中，这个缓存问题一直是最重要的性能问题。几乎所有重要的程序在针对大小而不是速度进行优化时运行得更快，并且缓存未命中是原因。