背景

在回答大部分我们无法解释的诡异问题时,我们最常用的辩词通常是历史原因

那么,历史又是出于什么原因,使用了0标号数组呢?Mike Hoye就是本着这么一种追根刨地的科学精神为我们找到了解答。以下是一些他的重要结论的摘录翻译:

据作者的说法,C语言中从0开始标号的做法是沿用了BCPL这门编程语言的做法。而BCPL中如果一个变量是指针的话,那么该指针可以指向一系列连续的相同类型的数值。那么p+0就代表了这一串数值的第一个。在BCPL中数组第5个元素的写法是p!5,而C语言中把写法改成了p[5],也就是现在的数组。具体原文摘录如下:

If a BCPL variable represents a pointer, it points to one or more consecutive words of memory. These words are the same size as BCPL variables. Just as machine code allows address arithmetic so does BCPL, so if p is a pointer p+1 is a pointer to the next word after the one p points to. Naturally p+0 has the same value as p. The monodic indirection operator ! takes a pointer as it’s argument and returns the contents of the word pointed to. If v is a pointer !(v+I) will access the word pointed to by v+I.

至于为什么C语言中为什么使用[]方括号来表示数组下标,这个设计也有一定来历。据C语言作者的说法是方括号是现代键盘上唯一较为容易输入的成对符号(不用shift)不信你对着键盘找找?

为什么这个反人类设计在一段时间内一直没有被改变

根据Mike的说法,BCPL是被设计在IBM硬件环境下编译运行的。在1960后的很长一段时间内,服务器硬件几乎被IBM统治。一个城市内也许至于一台超级计算机,还需要根据时间配额使用。当你当天的配额用完以后,你的程序就被完全清出计算队列。甚至连计算结果都不给你保留,死无全尸。这个时候写一段高效的程序,就显得比什么都重要了。而这时0下标数组又体现了出了它的另一个优势,就是:相较于1下标数组,它的编译效率更高。原文摘录如下:

So: the technical reason we started counting arrays at zero is that in the mid-1960’s, you could shave a few cycles off of a program’s compilation time on an IBM 7094. The social reason is that we had to save every cycle we could, because if the job didn’t finish fast it might not finish at all and you never know when you’re getting bumped off the hardware because the President of IBM just called and fuck your thesis, it’s yacht-racing time.

此外,还有另外一种说法。在C语言中有指针的概念,而指针数组标号实际上是一个偏移量而不是计数作用。例如对于指针p,第N个元素是*(p+N),指针指向数组的第一个元素就是*(p+0).

更高效

数组(Arrary)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。如果用a来表示数组的首地址,a[0]就是偏移为0的位置,也就是首地址,a[k]就表示偏移k个type_size的位置,所以计算a[k]的内存地址只需要用公式:

a[k]_address = base_address + k * type_size;

但,如果数组从1开始计数,那公式的k就要做相应的改变了:

a[k]_address = base_address + (k - 1 ) * type_size;

对比两个公式,我们发现,如果从1开始编号,每次随机访问数组元素都多了一次减法运算,对于cpu来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能的做到极致。从0开始,可以减少一次减法操作。

参考文献:

  1. https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
  2. https://blog.csdn.net/localhostcom/article/details/86358593
  3. https://www.zhihu.com/question/37408440
  4. http://cenalulu.github.io/linux/why-array-start-from-zero/