2

我试图理解算法的概念以及它们如何提高计算机程序的性能。

所以假设,我必须编写一个程序来生成一个数字列表,

  1. 从数字 1 开始。

  2. 加3。

  3. 将结果 (1+3=4) 存储在列表中。

  4. 将 5 添加到新数字。

  5. 将结果 (4+5=9) 存储在列表中。

  6. 保持交替将 3 和 5 添加到列表中的最新数字。

现在这是一个非常简单的程序,假设当数字大于 10,00,000 时程序必须停止,假设一个简单的程序执行此操作需要 10 秒来生成列表。

如何为这个问题设计一种算法,以使程序花费更少的时间来生成列表。

注意- 我试图通过一个例子来理解这里的概念,上面提到的时间是随机的,不是事实。如果有人不想使用上面的示例,如果有人可以通过“简单”示例帮助我理解这个概念,那就太好了。

4

4 回答 4

7

您在上面给出的(生成列表的步骤列表)一种算法。

效率的显着提高通常意味着从一种算法更改为另一种以更少的工作完成相同目的的算法。例如,对于上面的算法,您可能会尝试完全避免创建列表(这样),而是替换一个可以快速生成列表中任何特定位置结果的算法——给定 N 作为输入,它会做类似的事情

int n = N/2; 
int m = N-n; 
return 1 + n * 3 + m * 5;

请注意,这段代码可能并不完全正确(我认为它不能完全正确地处理奇数和偶数输入数字),但您明白了——而不是执行一系列操作来获得一个结果,它执行数量少得多的操作来产生相同的结果。

于 2013-01-04T15:15:53.587 回答
1

那么在你给你的例子中,你不能快得多。您必须输出整个列表,并且您描述的算法可以有效地完成它。

让我们稍微修改一下问题:您只需输出第一个大于 1000000 的数字。这可以比生成整个列表更智能地解决。

于 2013-01-04T15:15:02.027 回答
1

当人们着眼于改进程序或代码片段的性能时(即使用更好的算法来计算相同的结果),重要的是要考虑算法的可见输出。也就是说,算法的(输出)是如何被使用或消耗的?换句话说,算法返回什么,该返回是如何消耗的?

您问题中的上述步骤表明应该建立一个列表,但是然后呢?如果仅仅丢弃结果(您可以轻松编写这样的程序或函数),一个好的优化器(人或机器)可以根据结果从未使用过的事实替换空程序或空程序或函数。(说真的:这是基准测试中的一个常见问题,一种算法计算一些结果来衡量生成代码的性能,但没有使用该结果,因此编译器可能会删除整个循环、内存分配,甚至可能是整个函数!)

因此,关于如何分析如何更改算法以获得更好性能的问题的设置,真正重要的是:识别或指定输出的一部分(由程序的其他部分使用)。

给定一个规范(关于如何使用算法的结果),我们可以向后工作以找到能够以更少的工作产生相同结果的算法改进。

当我们编写算法时,我们可以通过这些组合来确定改进的机会。换句话说,您上面描述的算法可能会被其他算法用来一次只找到一个值,这意味着 Jeffry 的解决方案是性能更好的替换算法。

但是,列表算法的不同使用者可能会要求其可​​见效果的不同部分,因此不同的优化或算法替换可能是合适的。这就是我上面描述的情况,如果根本不使用结果,但另一个消费者可能只想计算列表中的节点数,在这种情况下,完全不同的优化更合适。

在某些情况下,我们可以指定算法返回一些东西,并且我们被迫出于某种原因生成代码,而不知道谁在使用结果。在这些情况下,优化器(人或机器)将被迫做出悲观的假设,即返回的每个可见效果都可能被消耗。例如,假设列表是返回的内容(作为您问题中的附加说明),并且我们阻止任何优化器进一步查看消耗,我们很可能必须实际构建列表(因此杰弗里的回答不起作用)。

简而言之,如果没有额外的上下文,我们就无法完全分析问题及其解决方案空间。

在某种程度上,附加上下文采用显式返回语句的形式(或其他一些外部可见的副作用,例如修改全局变量)。

此外,一些额外的上下文可能采用另一种算法的形式,即封闭、调用或组合(使用感兴趣的原始算法);因此,优化过程是递归的,并且(人或机器)可以“看到”的越多,产生的结果就越好。

于 2013-01-08T22:09:10.083 回答
0

让我们首先说您不使用算法来提高计算机程序的性能。算法就是程序(根据定义,算法是解决问题的有限操作序列)。

当然有一些著名的算法,已经由智者发明,可以完美地应用于一个问题(你的问题是关于图的?Dijkstra 的最短路径算法,Ford-Fulkerson 的最大流量,Prim 和 Kruskal 的最小生成树, 等等)。您通常希望在您的程序中重新使用这些性能良好的算法,而不是从头开始重新编写它们。

你会想要使用它们,因为

  1. 重写它可能会让你的表现更差
  2. 重写它肯定会消耗你的时间,你可以花时间解决问题(假设算法的使用是你问题的一个子集,即“为了解决我的问题,我需要先重新排序一个数组” - 重新排序的数组是解决方案的必要步骤,但不是你的问题)

至于数字 1,还涉及到一些数学计算,因为要衡量算法的性能,您必须做一些在此处更好解释的事情

希望我清楚地解决了您的疑问,不幸的是我不喜欢大符号和这样的性能计算,所以我只能指向维基百科链接

于 2013-01-04T15:20:36.020 回答