算法=逻辑+控制


观点

Robert Kowalski在其论文Algorithm = Logic + Control中指出:

An algorithm can be regarded as consisting of a logic component, which specifies the knowledge to be used in solving problems, and a control component, which determines the problem-solving strategies by means of which that knowledge is used. The logic component determines the meaning of the algorithm whereas the control component only affects its efficiency. The efficiency of an algorithm can often be improved by improving the control component without changing the logic of the algorithm. We argue that computer programs would be more often correct and more easily improved and modified if their logic and control aspects were identified and separated in the program text.

算法可以视为由逻辑部分和控制部分组成。其中,逻辑部分指明了解决问题时需要用到的知识。而控制部分则(根据逻辑部分用到的知识来)决定解决问题时需要用到的策略。逻辑部分确定算法的含义,而控制部分只影响其效率。在不改变算法逻辑部分的条件下,通常可以通过改进算法控制部分来提升算法的效率。我们认为,如果软件代码中的逻辑部分和控制部分能够有效的识别和区分开,那么软件将会变得更加容易改进和维护。

We have argued that conventional algorithms can usefully be regarded as consisting of two components:
(1) a logic component which specifies what is to be done and
(2) a control component which determines how it is to be done.

我们认为传统的算法可以被视为由两个部分组成:
(1) 一个表明算法做什么的逻辑部分
(2) 和一个决定了算法如何做的控制部分。

举例

那么如何来理解算法 = 逻辑 + 控制以及如何区分算法中的逻辑控制呢?作者举例几个例子来阐述,其中一个简单易懂的例子就是阶乘。

首先,阶乘的定义是:

  1. 0的阶乘是1
  2. 如果x的阶乘是v,那么x+1的阶乘就是v*(x+1)

我们一般有两种方式计算一个数n的阶乘:

  1. 自底向上。首先计算0的阶乘,然后是1,然后是2…一直到n。本质就是从0循环计算直到n
  2. 自顶向下。要计算n的阶乘,首先就要计算n-1的阶乘。要计算n-1的阶乘,首先就要计算n-2的阶乘。这样一直到需要计算0的阶乘,而我们知道0的阶乘是1。本质就是递归的求解。

分析

结合Robert Kowalski的观点和上面的阶乘的例子来理解。

阶乘算法可以视为由两个部分组成:

  1. 逻辑部分,是阶乘的定义。
    为什么呢?逻辑部分的定义就是做什么,而阶乘算法的做什么就是计算一个数的阶乘。其中”逻辑部分指明了解决问题时需要用到的知识“的知识,指的就是阶乘算法的定义。换而言之,算法的逻辑部分,指定是算法的业务逻辑。
  2. 控制部分,是阶乘的计算方法。
    为什么呢?控制部分的定义就是如何做,上面例子中如何计算的阶乘的方法有两种:自底向上和自顶向下。”在不改变算法逻辑部分的条件下,通常可以通过改进算法控制部分来提升算法的效率。“ 我们也确实可以通过优化阶乘计算过程中的细节来提高计算的效率,比如在自底向上的方法中,缓存计算过的值,避免重复计算来提高效率。但是我们很难通过调整阶乘定义的描述方式来优化整个阶乘算法的效率。

另外一个容易理解的例子是排序算法。不同的排序算法都可以实现排序的功能,而不用的排序算法的效率是不同的,比如冒泡排序,归并排序等。所以对排序算法来说,排序功能是逻辑部分,冒泡、归并等具体的做法则是排序算法的控制部分

结论

Robert Kowalski的观点帮助我们能够更好的分解程序中的算法,将做什么怎么做的代码分开,其实也是应用设计模式策略模式的过程。

我们都知道,程序是由算法和数据结构组成的(最开始由Niklaus Wirth在其书Algorithms + Data Structures = Programs提出),即算法 + 数据结构 = 程序,而Robert Kowalski的观点则是将这个公式进一步的细化,从而让我们能够得出:算法逻辑 + 算法控制 + 数据结构 = 程序


文章作者: Kiba Amor
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 Kiba Amor !
  目录