efficiency /algorithms与系统规格

Question

我们都在讨论算法的效率，这取决于输入大小-basically。

运行该算法的当前计算机的系统规格如何？在Core2 Duo 2.6 GHZ，4 GB RAM计算机或P-2,256MB RAM计算机上运行不同的排序算法有什么不同吗？

我相信肯定会有性能上的差异。但是，我想知道算法和系统规范之间的真正关系是什么……

Answer 1

硬件性能的提高将使您的算法运行时间恒定为C倍。这意味着，如果你有比计算机B慢2倍的计算机A，那么你的算法在计算机B上的速度将是计算机B的两倍。但是，当你考虑到算法的大输入值时，速度是两倍，这几乎没有什么区别。

这就是说，与C_O(n) = O(c_n) = O(n)相比，你会得到类似O(n)的结果。在计算机A和计算机B上，算法的复杂性和大值的一般运行时间将大致相同。

如果你使用像大O这样的符号来分析一个算法的运行时间，那么你会对算法的实际工作方式有一个更好的了解。当您比较O(logn)与O(n^2)的算法时，计算机性能不会给您带来任何类型的优势。

看一下n的一些数据值：

对于速度较慢的计算机，我假设每次操作1秒，对于速度较快的计算机，假设每次操作2秒。我会将较好的算法与较慢的计算机与较差的算法与较快的计算机进行比较。

N=10的：

算法1: O(logn)：4运算慢计算机:4秒算法2: O(n^2)：100运算快速计算机: 50秒

N=100的：

算法1: O(logn)：7运算速度计算机:7秒

算法2: O(n^2)：10,000次运算快速计算机: 1.4小时

差异很大

N=1,000的：

算法1: O(logn)：10次运算计算机速度: 10秒

算法2: O(n^2)：1,000,000次运算快速计算机: 5.8天

巨大的差异

随着n的增加，差异变得越来越大。

现在，如果您尝试在较快/较慢的计算机上运行这些算法中的每一个，以获得较大的输入大小。这无关紧要。简单地说，O(logn)会更快。

Answer 2

我不喜欢布赖恩·邦迪和奇米提供的答案。

也许这是因为我开始于一个不同的时代，当时32K被认为是大量的内存，大多数“个人计算机”有8K字节，而现在我在科学计算领域工作，其中最大的数据集是在一些世界上最大的系统上处理的，这些系统有数千个处理节点和令人难以置信的存储量。因此，我不会忽略这个问题的某些其他元素。

所讨论的数据集的大小产生了极大的不同。到目前为止，关于这个问题的大多数答案都忽略了这一点，并且只适用于非常小的数字N。其他回答的人都假设“它们都适合记忆”，或者类似的东西。

对于大型数据集，其他因素也会起作用，“大型”取决于您在解决问题时必须使用的资源。现代系统具有离线存储(例如DVD)、网络存储(例如nfs)、在线存储(例如串行ATA)以及两级存储器存储(系统主存储器和芯片上高速缓存)的机会。如何利用这些很重要，数据集越大，它们就越重要。你可能需要也可能不需要在你的“算法”中设计对这些的访问，但是如果你这样做了，它真的很重要！

当您将伸缩性增加到超过某个特定点时-单个CPU及其本地内存的限制是正确的-这些其他因素成为工作负载开销中越来越大的因素。当我是Digital的时候，我们在多CPU系统上做了一些真正的商业工作，我记得运行过一个基准测试，表明使用单CPU作为CPU工作负载能力的一个“单位”，第二个CPU(在紧密耦合的系统中)将总共提供大约1.8个CPU工作负载能力。也就是说，第二个CPU增加了大约0.8。对于三个CPU，增长下降到0.6左右，四个下降得更多，降到0.2左右，对于四个CPU的配置，总共大约2.6个CPU，尽管由于其他影响，我们在保持四个CPU的良好数字方面遇到了一些困难(测量工作成为额外资源的一大部分)。...The的底线是，多CPU并不一定像他们所说的那样--四倍的CPU不会给你四倍的处理能力，即使理论上你会有四倍的失败。...We在Alpha芯片上重复了这项工作，这是历史上第一个多核芯片，结果相当不错。当然，可以通过优化来提高每个额外CPU提供的部分，当然，从那时起，为了更智能地拆分计算线程，已经进行了大量的工作，但您永远不会一直做到100%，部分原因是它们都会减慢一些(额外的开销)来协调。

小感叹-我们对这项工作有一句话：“把所有重要的东西都交给编译器！”RISC，明白吗？这是因为编译器本身必须组织工作负载，以便相互竞争的线程不会彼此冲突！

最终，执行真正的海量数据处理需要一个非常聪明的策略，即通过本地内存将数据移入和移出更远的数据存储。而且，算法中的劳动分工是绝对至关重要的。在我与加州大学洛杉矶分校的Roberto Mechoso一起做全球循环建模的工作中，他们有一个数据代理设计，它说明了人们试图做一项伟大的工作。坦率地说，结果并不像它所能达到的那样好，但其中的设计思想值得研究。...Presuming如果你认为这是你的“算法”的一部分--而不仅仅是闲置的部分，那么资源的算法管理是合理的，如果不是最优的资源利用做大量计算的最重要的方面之一。

...I希望这能帮助你回答你的问题。

Answer 3

到目前为止还没有提出的一件事是，算法通常是用速度来描述的，例如O(n)，O(n log(n))等。但它们在资源使用方面也有特点，比如O (n )与O(n log(n))相比，速度的提高是以更大的内存使用量为代价的。在现代计算机中，当资源耗尽时，它们通常被较大的较慢的资源所取代，例如，将内存换成磁盘，其中较慢的资源是较慢的数量级。因此，当我们绘制算法的性能与时间的关系图，并期望得到一条直线、n对数n曲线等时……当内存耗尽时，我们经常会看到n值过大的峰值。在这种情况下，1 2GB和2 2GB内存之间的差异可能是巨大的，所以实际上，您的问题的答案是肯定的，系统规范是非常重要的，算法的选择需要了解系统规范和输入数据的大小。

例如，我开发了表面建模和分析软件，我知道我的程序在32位XP机器上可以很好地处理400万个点的TIN模型。350万和400万分之间的性能差异很小。在450万个点上，性能降级非常严重，以至于软件无法使用。