algorithm - 如何在评估性能时考虑缓存未命中？

Question

通常性能以 O() 数量级表示:O(Magnitude)+K 其中 K 通常被忽略，因为它主要适用于较小的 Ns.

但我越来越多地看到性能受底层数据大小支配，但这不是算法复杂性的一部分

假设 algorithm A 是 O(logN) 但使用 O(N) 空间并且 algorithm B 是O(N) 但使用 O(logN) 它曾经是 algorithm A 更快的情况。现在，由于多层缓存中的缓存未命中，算法 B 可能会更快地处理大数，如果 K

较小，则可能会更快

问题是你如何表示这个？

Answer 1

好吧，O(N) 命名法的使用抽象掉了一些重要的细节，这些细节通常在 N 接近无穷大时无关紧要。这些细节可以而且通常是 N 值小于无穷大时最重要的因素。为了帮助解释，考虑如果一个术语被列为 O(N^x)，它只是指定了 N 的最重要的因素。实际上，性能可以表征为:

aN^x + bN^(x-1) +cN^(x-2) + ... + K

因此，当 N 接近无穷大时，主导项变为 N^x，但显然在 N 的值小于无穷大时，主导项可能是次要项之一。查看您的示例，您给出了两种算法。我们将提供 O(N) 性能的算法称为算法 A，将提供 O(logN) 性能的算法称为算法 B。实际上，这两种算法具有如下性能特征:

性能 A = aN + b(log N) + c

性能 B = x(log N) + y

如果您的常数值为 a=0.001 和 x=99,999，您可以看到 A 如何提供比 B 更好的性能。此外，您提到一种算法会增加缓存未命中的可能性，并且这种可能性取决于大小的数据。您需要计算缓存未命中的可能性作为数据大小的函数，并在计算整个算法的 O 性能时将其用作一个因素。例如:

如果缓存未命中的成本是 CM(我们假设它是常数)，那么对于算法 A，整体缓存性能是 F(N)CM。如果缓存性能是算法 A 的主要循环中的一个因素(O(log N) 部分)，那么算法 A 的实际性能特征是 O( F(N)(log N))。对于算法 B，整体缓存性能将为 F(log N)*CM。如果在算法 B 的显性循环期间出现缓存未命中，则算法 B 的实际性能为 O(F(log N)*N)。只要能确定F()，就可以比较算法A和B。