| TOP | Code | Math | Luke | Math Book |
Previous: 关于逻辑 Next: One-liner curry decorator in Python

Why numbering should start at zero

2019-02-24

(03/23/2019 Update: 发现Guido也写过类似的文章解释为什么Python的下标从0开始,基本照搬了Dijkstra的观点。)

著名程序员Dijkstra在1982年的手稿中简要讨论了“为什么数字下标要从0开始”这个问题。

首先,他讨论了表示范围的最佳形式。 比如表示自然数序列2,3,···,12,有四种方法:

  1. \(2 \leq i \lt 13\),或者记作[2, 13)
  2. \(1 \lt i \leq 12\),或者记作(1, 12]
  3. \(2 \leq i \leq 12\),或者记作[2, 12]
  4. \(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)。 这也是一个很方便的性质吧,比如在当你要实现一个哈希表的时候。

Feedbacks are welome: @czheo