为什么计数应该从零开始?

2013-06-15 06:36


众所周知,C语言数组下标是从0开始,其它很多语言皆如此。而 FORTRAN 则是数组下标从1开始的典范。所以就有数组下标是从1开始好还是从0开始好之争。连《C专家编程》中都如此调侃:

数组的下标应该是从0还是从1开始?我提议的妥协方案是0.5,可惜他们未予认真考虑便一口回绝。—— Stan Kelly-Bootle

仔细思考一下这个问题很有意思,建议你不妨自己思考一下再继续往下看。

其实这个问题早在 1982 年就已经由计算机科学领域的大师 Edsger Dijkstra 研究过并得出了一个结论。他手写了一篇名为《Why numbering should start at zero》的论文,关键部分截图和大体翻译如下:

表示一个自然数子序列,比如 2, 3, …, 12,不用中间那三个点,有四种方式可供我们选择:

a) 2<= i < 13

b) 1 < i <= 12

c) 2<= i <= 12

d) 1 < i < 13

有什么道理选其中一种而不选别的吗?是的,的确有。观察到 a) 和 b) 的优势是两边的边界值之差正好是子序列的长度。作为一个推论,下面的观察也成立:在它们两个当中,两个子序列是邻接的就意味着一个的上界等于另外一个的下界。这些观察并没有让我们从a) 和 b) 之中做出选择,所以我们从头开始。

一定存在一个最小的自然数。排除掉下界——就像 b) 和 d) 那样——就会迫使一个从最小的自然数开始的子序列的下界进入非自然数领域。这很难看,所以对于下界我们更喜欢<=,就像 a) 和 c) 那样。现在,考虑一下从最小的自然数开始的子序列:包含上界就会迫后者不那么像自然数(译者注:作者的意思是自然数是一个有下界没有上界的集合),当序列缩小成空序列时。这很难看,所以对于上界我们更喜欢<,就像 a) 和 d) 那样。我们得出结论, a) 是我们最喜欢的。

当处理长度为 N 的序列时,我们期望通过下标来区分它的元素。下一个令人烦恼的问题就是,我们该给它的第一个元素赋予什么样下标值?坚持 a) 的方式,当下标从1开始时,下标范围为 1<= i < N+1;当下标从0开始时则是更好看的 0<= i < N。所以,让我们的序数从0开始:一个元素的序数(下标)等于序列中在它前面的元素个数。这个故事的寓意是我们最好尊重0最为一个最自然的数——过了这么多个世纪!

———

顺便说一句,Python 选择了 a),所以 range(0,3) 返回的是序列是 0,1,2。

via http://wangcong.org/blog/archives/2230