什么才是优秀的程序代码

Posted by Ivan on 2017-02-08

首先,我想说的是,我谈及的“优秀程序代码”,不是指“优秀程序”,也不是更易阅读的“代码”,恰恰相反,我可能想写的是更不易阅读的代码,这里的“优秀”指的是高效、快速。

在写之前,我想先用一个原则引入这个文章:

KISS原则 *Keep It Simple, Stupid*

是的,这是我心中优秀的代码程序,就是简单、高效。

相信所有人都知道时间复杂度这个东西,是的,优秀的代码永远都在做一件事:降低时间复杂度,哪怕写的过程是复杂的、理解起来是相对难的(比如,快速排序、堆排序)。那么,我接下来,想较一下真。

卡常数

据考证,[卡](Qa’a)是古埃及第一王朝的最后一位法老。

他发现并研究了一种常数,后世以他的名字叫做卡常数。卡特兰数的起源也是因为卡的后人与特兰克斯结婚,生下来的孩子就叫卡特兰,而他只是发表了祖传的家书而已。

Sereja也是卡的后人,提出括号序列问题,也是从家书里得到的资料。然而Sereja为了不让这个秘密公开,于是隐瞒了这道题的真正做法。可是由于卡的后人不是各个都像卡特兰一样爱慕虚荣,这一算法也无法找到。“欲见贤人而不以其道,犹欲其入而闭之门也”。卡之常数的奥秘,需要以一颗诚心去追寻。

看不懂对吗?

我也看不懂,因为这是一群高中生写的。按照我的理解,卡常数,就是内循环里的那些看似不重要的语句其实每一句话的运行速度是不一样的,这个客观规律,是真实存在的,举个栗子🌰

程序1

1
2
3
4
5
6
for (int i = 0; i <= K; i++)
for (int j = 0; j <= K; j++)
for (int k = 0; k <= K; k++) {
r.a[i][j] += a[i][k] * x.a[k][j];
if (r.a[i][j] >= 1ll << 62 || k == K) r.a[i][j] %= mod;
}

程序2

1
2
3
4
for (int i = 0; i <= K; i++)
for (int j = 0; j <= K; j++)
for (int k = 0; k <= K; k++)
r.a[i][j] = (r. a[i][j] + a[i][k] * x.a[k][j] % mod) % mod;

按照常人的理解,程序1程序2的复杂度都是O(n^3),没错,那么他们的时间是一样的吗?

并不一样。

在机器性能并没有那么高的情况下,在测试数据量没有那么少的情况下,第二种比第一种快了一倍。

为什么?

因为第二种代码更加精炼吗?并不完全是。

程序1中,if (r.a[i][j] >= 1ll << 62 || k == K)实际上是耗费时间的,if操作在执行的时候真实的操作是这样的:

1
2
3
4
if(这里面是true吗?)
左边是true吗?
右边是true吗?
||操作是true吗?

这必然会消耗大量的时间,同理

1
2
r.a[i][j] += a[i][k] * x.a[k][j];
r.a[i][j] = a[i][k] * x.a[k][j] + r.a[i][j];

一样吗?实际上是不一样的,后者比前者快一点。

你可能觉得,这也太较真了吧?但是高效就是高效,效率提高才是硬道理。

不积跬步,无以至千里;不积小流,无以成江海。

原则

  • 一杆内存在心中

  • 多写一个不必要的循环递归,浑身难受

  • 多写一个不必要的逻辑判断,浑身难受

  • 多写一个无关变量,浑身难受

  • 不找到最优解,浑身难受

  • 始终自发的想着如何用栈、树去解决问题

  • 代码效率哪怕提升的是一倍,花一天优化代码也是值得的

  • 时刻遵循RP定律写代码,RP++

我从我接触OI那一刻起,我觉得算法是美的,每一个人写出来的算法都体现了一种算法,永远对高效快速的低复杂度的精炼代码充满敬畏之心!❤️