当人们着眼于改进程序或代码片段的性能时(即使用更好的算法来计算相同的结果),重要的是要考虑算法的可见输出。也就是说,算法的(输出)是如何被使用或消耗的?换句话说,算法返回什么,该返回是如何消耗的?
您问题中的上述步骤表明应该建立一个列表,但是然后呢?如果仅仅丢弃结果(您可以轻松编写这样的程序或函数),一个好的优化器(人或机器)可以根据结果从未使用过的事实替换空程序或空程序或函数。(说真的:这是基准测试中的一个常见问题,一种算法计算一些结果来衡量生成代码的性能,但没有使用该结果,因此编译器可能会删除整个循环、内存分配,甚至可能是整个函数!)
因此,关于如何分析如何更改算法以获得更好性能的问题的设置,真正重要的是:识别或指定输出的一部分(由程序的其他部分使用)。
给定一个规范(关于如何使用算法的结果),我们可以向后工作以找到能够以更少的工作产生相同结果的算法改进。
当我们编写算法时,我们可以通过这些组合来确定改进的机会。换句话说,您上面描述的算法可能会被其他算法用来一次只找到一个值,这意味着 Jeffry 的解决方案是性能更好的替换算法。
但是,列表算法的不同使用者可能会要求其可见效果的不同部分,因此不同的优化或算法替换可能是合适的。这就是我上面描述的情况,如果根本不使用结果,但另一个消费者可能只想计算列表中的节点数,在这种情况下,完全不同的优化更合适。
在某些情况下,我们可以指定算法返回一些东西,并且我们被迫出于某种原因生成代码,而不知道谁在使用结果。在这些情况下,优化器(人或机器)将被迫做出悲观的假设,即返回的每个可见效果都可能被消耗。例如,假设列表是返回的内容(作为您问题中的附加说明),并且我们阻止任何优化器进一步查看消耗,我们很可能必须实际构建列表(因此杰弗里的回答不起作用)。
简而言之,如果没有额外的上下文,我们就无法完全分析问题及其解决方案空间。
在某种程度上,附加上下文采用显式返回语句的形式(或其他一些外部可见的副作用,例如修改全局变量)。
此外,一些额外的上下文可能采用另一种算法的形式,即封闭、调用或组合(使用感兴趣的原始算法);因此,优化过程是递归的,并且(人或机器)可以“看到”的越多,产生的结果就越好。