天天看点

聪明的数据结构和笨拙的逻辑代码

前言

《大教堂和市集》中有这样一句话:聪明的数据结构和笨拙的代码要比相反的搭配工作的更好 ,我深以为然。本篇博文就是对此话题的个人简单理解,涉及的编程问题基本上来源于Codewars。

关于《大教堂与市集》中文版可访问这里

释读

Pascal之父——Nicklaus Wirth提出著名公式“算法+数据结构=程序”

本篇博文的主题也可以用简单的数学语句表达出来:

聪明的数据结构 + 笨拙的逻辑代码 > 笨拙的数据结构 + 聪明的逻辑代码

极端的说法是:优秀的数据结构远比优秀的逻辑代码要更好用。

以下举一个来自Codewars中的编程问题:Playing on a chessboard

题目描述:给定一个输入参数n,它会得到一个二维数组(类似矩阵),行方向以1/2,2/3,3/4这样的方式递增,列方向以1/2,1/3,1/4这样的方式递增。返回一个数组,其值为所有元素的求和,如果求和值能约简为整数,则返回整数,否则返回[分子,分母]。

一个

n=3

时的数组例子:

[
[1/4,2/5,3/6],
[1/3,2/4,3/5],
[1/2,2/3,3/4]
]           

初始解题思路是:先生成一个长度为n的二维数组,然后通过二次for循环对数组写入正确的值(这样好方便下边的计算),然后对数组中的所有元素进行求和,判断求和值是否能约简为整数,返回相应要求的数组。

然而,这个解法太死板了,于是我去看了看其他程序员的解法,然后,非常震惊的解法找到了,该解法的思路是:先找到n与求和值结果之间的数学关系,关系是:从生成数组的左上至右下方向观察数据,发现其值为n/2或(n+1)/2,然后我们得到了输入参数n和求和值之间的数学关系是:

n*n/2

这便是所要求得结果,所以,最后的解决方案是:

function game(n) {
    return n%2==1?[n*n,2]:[n*n/2];
}           

被震惊到了吧!这里有这样一个逻辑:观察相关的数学关系表达式,这便是所谓的聪明的数据结构了,而逻辑逻辑代码则因为数据结构的关系,变得异常简单(实际只是一个if判断),而初始思路则可看出笨拙的数据结构(未得到数学表达式之前的数据结构)的表现了。

(未完 待补写)