Why numbering should start at zero
(03/23/2019 Update: 发现Guido也写过类似的文章解释为什么Python的下标从0开始,基本照搬了Dijkstra的观点。)
著名程序员Dijkstra在1982年的手稿中简要讨论了“为什么数字下标要从0开始”这个问题。
首先,他讨论了表示范围的最佳形式。 比如表示自然数序列2,3,···,12,有四种方法:
- \(2 \leq i \lt 13\),或者记作
[2, 13)
。 - \(1 \lt i \leq 12\),或者记作
(1, 12]
。 - \(2 \leq i \leq 12\),或者记作
[2, 12]
。 - \(1 \lt i \lt 13\),或者记作
(1, 13)
。
方法1是最好的
Dijkstra认为方法1和2是比较好的表示形式,原因有两个。
其一,范围的上限减去下限等于范围内元素的个数。 比如方法1中,13 - 2 = 11,而范围内刚好就有11个元素。 方法2也有同样的性质,但方法3和4就没有。
其二,连续的范围没有重叠。
两个连续的范围我们希望可以写成“a到b”和“b到c”这样的形式。
如果使用方法3,12就同时包含在[2, 12]
和[12, 24]
这两个范围里;
类似的,使用方法4,13既不包含在(2, 13)
里也不在(13, 25)
里。
用方法1和2就没有这样的问题。比如[2, 13)
和[13, 25)
是两个连续的范围,13只会包含在后一个里。
虽然方法1和2都能满足上面两条性质,但Dijkstra继续给出了方法1比方法2好的理由:
我们常常会用到有下限无上限的集合,最典型的是自然数集合。
比如要表示自然数集合内的范围“0到10”,
用方法1可以写成[0, 11)
,
用方法2可以写成(-1, 10]
。
方法2的问题是形式中出现了-1这个非自然数,
用非自然数来表示一个自然数集合内的范围显然不是一个好的选择。
为什么下标要从0开始
Dijkstra进而在其手稿中继续讨论数字下标为什么从0开始的问题,
他给出的第一个理由是,如果你能接受前半段关于表示范围的最佳表示方法的结论,那么N个元素的数列下标可以采用[0, N)
或者[1, N+1)
两种形式,前一种不需要+1也就显得更简洁了。
另一个理由是,如果从0开始标号,那数列中某个元素的下标就等于排在它前面元素的个数,这在很多时候是一个可以方便使用的性质。
0 1 2 3 4 5 6 7 8 9
^
There are 4 elements before this.
第三个理由有点模糊,他说0是”最自然的数”(a most natural number),却没有给出具体的解释。 于是我强行解释一下:计算机中的数用二进制表示,所有的位都是off时,便是起点,也就是最自然的数吧。
你问我资瓷不资瓷Dijkstra,那肯定回答资瓷
Dijkstra绕了个圈子论证了从0开始的正当性,我能联想到与此相关的最直接的编程技巧是C语言中的数组操作:读取数组元素的操作和指针操作有比较直接的等价关系。
具体地说,C语言中arr[idx]
等价于*(arr + idx)
。
指针操作你可以看作对base地址偏移offset的量,
即在*(arr + idx)
式子中,arr
是base地址,idx
是offset。
试想如果下标设计成从1开始,那C语言可能需要设计成arr[idx]
等价于*(arr + idx - 1)
了。
另外,有热心网友指出mod计算时,x % N
的范围是[0, N)
。
这也是一个很方便的性质吧,比如在当你要实现一个哈希表的时候。