就像有缓存无感知算法和缓存最优算法一样，是否有寻址最优算法？

Question

3

缓存（无感知|最优|感知）算法通常在其模型中考虑寻道时间吗？如果没有，是否有考虑寻道时间的模型示例，以及是否存在针对该模型的算法分析。

- san

我不明白如何能够拥有一个在寻找方面表现糟糕的缓存最优算法...这两者不是基本上是同义词吗？ - user541686

@Mehrdad，这正是我想要了解的，缓存优化是否也意味着寻道优化。我不确定它们是否有关联。 - san

1

我不理解你所谓的“寻求最优性”的含义...是指总寻道时间吗？最小化寻道的唯一方法是使数据更本地化；看起来几乎无法通过定义来使数据“更”非本地化但“更少”导致寻求，不是吗？ - user541686

@Mehrdad 我认为举个例子会有所帮助，比如说我想要转置一个存储在磁盘上的矩阵。对于这个问题，有一些高速缓存优化算法可供选择。我感兴趣的是是否存在一些算法可以根据某种模型实现最小数量的寻道操作，以及这些高速缓存优化算法本身是否能够实现这一点。 - san

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sophit · Accepted Answer

是的，我个人编写过敏感搜索算法。文件系统确实使用寻址敏感的数据结构（类似于算法）。

例如，NTFS（以及许多其他文件系统）以B-tree格式存储数据，以最小化查找并优化顺序读取。

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

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

例如，堆数据结构比树更加友好。对于性能敏感的代码，当它是可行选择时，会选择使用堆而不是树。

至少在过去十年中，这个缓存问题一直是一个主要的性能问题。几乎所有非平凡程序在为大小而优化时运行速度更快，而缓存未命中是原因。