欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

为什么有些编程语言的数组要从零开始算?

程序员文章站 2022-03-06 20:45:28
...
像C语言的数组,Python的List都是从零开始记数。说实话从开始编程到现在,都没想过为什么这样设计?Matlab又不是从零开始了。
这是工程上有什么优势吗?

回复内容:

这个问题,Dijkstra 大神在 1982 年就写过一篇小文章了,题为 Why numbering should start at zero
总共也就 3 页手写,我就摘重点的大致翻译一下:


为了表示一个自然数序列 2, 3, …, 12,排除掉中间的那三个点 (...),总共有四种方式可供我们选择:

a) 2

b) 1

c) 2

d) 1

有没有什么原因使得我们应该选其中的某一种而不是其他的呢?是的,的确有。观察到 a) 和 b) 的优势是不等式的上下界之差恰好是序列的长度。基于此,作为一个中间结论:在 a) 和 b) 两种表达中中,两个序列是邻接的就意味着一个的上界等于另外一个的下界。但这些考量并没有让我们从 a) 和 b) 之中做出选择,所以我们从头开始。

存在一个最小的自然数。排除掉下界——就像 b) 和 d) 中那样——就会使得一个从最小的自然数开始的序列的下界变成非自然数。这样的表达方式很难看,所以对于下界应该更倾向于

当处理长度为 N 的序列时,我们期望通过下标来区分它的元素。下一个恼人的问题就是,我们该给它的第一个元素赋予什么下标值?使用 a) 的表达方式,当下标从 1 开始时,下标范围为 1 所以,让我们将序号从 0 开始:一个元素的序号(下标)等于序列中在它前面的元素个数。这个故事的寓意是我们更应该——过了这么多个世纪!——把 0 当作一个自然数。

是 BCPL 作者的杰作,目的是减少编译出的代码里的一个减法指令。 为什么有些编程语言的数组要从零开始算?

@haha王 提到Dijkstra那篇文章。Why numbering should start at zero。不过他并没有翻译全文。这里补充全文翻译。可能会有所错漏。

-----------------------------------

为什么应该从0开始计数

为了表示出自然数的子序列,2, 3, ... , 12,不使用省略记号那三个点号,我们可以选择4种约定方式:

  • a) 2 ≤ i
  • b) 1
  • c) 2 ≤ i ≤ 12
  • d) 1

是否有什么理由,使选择其中一种约定比其它约定要好呢?是的,确实有理由。可以观察到,a) 和 b)有个优点,上下边界的相减得到的差,正好等于子序列的长度。另外,作为推论,下面观察也成立:在 a),b)中,假如两个子序列相邻的话,其中一个序列的上界,就等于另一个序列的下界。但上面观察,并不能让我们从a), b)两者中选出更好的一个。让我们重新开始分析。


一定存在最小的自然数。假如像b)和d)那样,子序列并不包括下界,那么当子序列从最小的自然数开始算起的时候,会使得下界进入非自然数的区域。这就比较丑陋了。所以对于下界来说,我们更应该采用≤,正如a)或c)那样。现在考虑,假如子序列包括上界,那么当子序列从最小的自然数开始算起,并且序列为空的时候,上界也会进入非自然数的区域。这也是丑陋的。所以,对于上界,我们更应该采用

讨论:Mesa是由Xerox PARC(施乐帕克研究中心)开发出的编程语言,以上4种表示整数区间的方式,在Mesa中,全部都有专门的记号。使用Mesa的大量经验指出,采用另外三种表示方式,会不断引出拙劣和错误的代码。因此,现今有经验的Mesa程序员强烈建议,不要去使用后面三种特性,尽管它们也可以使用。不管是真是假,我也提出这个实践证据,有些人在结论还没有被实践验证时,会感觉有所不安。(讨论结束)


当处理长度为N的序列时,我们希望通过下标去区分它的元素,下一个值得分析的问题是,最开始的元素应该给予什么样的下标值。我们依然采用a)的约定,当下标从1开始时,下标区间是 1 ≤ i

讨论:很多编程语言对于计数的细节并没有足够的重视。在FORTRAN语言中,下标总是从1开始;而在PASCAL语言中,采用了约定c);距今更近的语言SASL, 倒退到FORTRAN的方式:在SAL中,序列也是在正整数上进行操作。(讨论结束)


最近的一次意外事件,促使我作出以上分析。当时,我所在大学的一个数学同事,并非计算机学家,情绪激动地指责一个年轻的计算机学家“迂腐”,因为计算机学家出于习惯而从0开始计数。我的数学同事将一些出于理性考虑后而自觉采用的合理约定,视为挑衅。(就连“...结束”这种约定,也视为挑衅。“...结束”这种约定是有用的:我就知道有个学生,他想当然地认为问题在第一页试卷中结束,而差点没有通过考试。) 我认为Antony Jay陈述得对:“在众人共同组成的宗教中,异教徒必须被驱逐出去,并非因为他们可能是错的,而是因为他们可能是对的。”

这个和数组访问的方式有关,数组是存在内存里的,如何访问一个内存,只需要拿到这个内存的地址就可以了。
但是如何拿到第i个元素的地址呢,拿到数组的首地址,加上相对偏移就能计算出第i个元素的地址,这个偏移比较好算,因为每个元素的大小都是一样的,就用元素大小乘以元素个数就能获得偏移量了。
数组内存结构就是连续排列的很多内存块。则可知:
第1个元素的地址=首地址a
第2个元素的地址=首地址a + 1*元素大小
第3个元素的地址=首地址a + 2*元素大小
第4个元素的地址=首地址a + 3*元素大小
第5个元素的地址=首地址a + 4*元素大小
...............
第i个元素的地址=首地址a + (i-1)*元素大小

所以如果用1来做元素第一个编号在计算内存地址的时候总会进行一次减法,用0就不会,所以用违背常规的方法换来了计算速度。

用反汇编也可以得到证实。 补充一点
模运算:
以下标为0开始的时候:
a[i mod N]
以下标为1开始的时候:
a[i mod N + 1] 不从零开始的才是逗逼。

不从零开始的设计初衷可能是为了让人感觉自然,贴近自然人的习惯。但是在大多数语言都从0开始计算下标的时候,不从0开始的反而不自然了。

从效率上来说,从0开始是效率最高的,下标数直接就是存储位置的偏移量;从1开始还得下标减1才是偏移量,性能差异虽然微乎其微,但终究不是最直接的方式。 反对这里答案的为了效率。

c语言:

一般认为,c语言这是为了想避免在运行时去减下标的开销,其实,编译器完全可以采用转换为虚起始地址的方法,来避免所有的运行开销。
所以,另一种可信的解释是c语言的数组与指针互操作。

以上来自《程序设计语言——实践之路》
(原文:In C, the lower bound of every array dimension is always zero. It is often assumed that the language designers adopted this convention in order to avoid subtracting lower bounds from indices at run time, thereby avoiding a potential source of inefficiency. As our discussion has shown, however, the compiler can avoid any run-time cost by translating to a virtual starting location. (The one exception to this statement occurs when the lower bound has a very large absolute value: if any index (scaled by element size) exceeds the maximum offset available with displacement mode addressing [typically 2^15 bytes on RISC machines], then subtraction may still be required at run time.)
A more likely explanation lies in the interoperability of arrays and pointers in C (Section 7.7.1): C's conventions allow the compiler to generate code for an index operation on a pointer without worrying about the lower bound of the array into which the pointer points. Interestingly, Fortran array dimensions have a default lower bound of 1; unless the programmer explicitly specifies a lower bound of 0, the compiler must always translate to a virtual starting location.)

Python:

曾经有人在Twitter上问我为什么Python使用以0为首位的数组索引法(0-based),并且还给我了一个相关优秀文章的链接。这让我想起许多往事:Python的前身之一,ABC语言使用的是以1为首位的数组索引方式(1-based),而对Python有着巨大影响的C语言则使用的是0-based。我早期开发的程序语言(Algol、Fortran、Pascal)有的使用1-based,有的则比较灵活。我认为切片语法是我做出这个决定的原因之一。

我们先来看看切片语法的使用吧。它最常见的使用应该是“切出数组的前n位”和“切出数组第i位后的 n位”(前者是后者在i==起始位下的特例)。如果我们不需要使用难看的+1或-1补偿方式,那么代码就会美观许多。

通过使用0-based索引法,Python的半开区间以及缺省匹配区间都很美观,如:a[:n] 和a[i:i+n];前者是a[0:n]的省略写法。

在1-based索引法下,如果你想用a[:n]来表示切出前n个元素的话,你只能选择在切片语法中使用切片起始位和切片长度2个参数,或者闭区间的用法。使用1-based索引法,半开区间切片语法就显得不够美观。同样地,使用闭区间切片语法的话,你只能用a[i:i+n-1]来表示从第i位取n个元素。所以如果使用1-based索引法的话,使用切片长度更合适。你可以写成a[i:n]。事实上,ABC语言就是这样的——它用了一种特殊的用法,写为a@i|n。(参考ABC QUICK REFERENCE)

但是index:length的用法适合其它情况吗?老实说,我不太记得了,但我想我当时的确很喜欢它美观的半开区间语法。特别是两个切片操作位置相邻并且第一个切片操作的终点索引就是第二个切片的起点索引的时候,它的写法实在是太漂亮了。比如,你想以i , j两点来切分一个数组的话,它们将会是a[:i]、a[i:j]、和 a[j:]。

这就是Python 使用0-based索引法的原因。


以上来自Python之父:为什么Python数组下标从0开始

在字符串截取函数中这个问题会得到直观的理解。第一个字,第二个字,第三个字——下标数字应该理解成那个逗号分割位置的编号,而不是位置本身的编号。否则你说1是第一个字的左边还是右边?
不喜欢内存这种底层+历史原因,因为那并不能解释为什么后来不改掉。 我是跟着来搞笑的。

换我这种渣渣写c语言的编译器的话,我绝对愿意将数组定为0开始,地址计算方便多了,编译器好写多了,反正是c语言这么接近汇编的东西是吧……所以不妨我们为了方便就这么规定了吧,哼,才不是因为懒呢! 我提一些這裡暫時沒有提到的。
  1. 下標通常用無號整數表示。一個n位無號整數的表示範圍是{0, 1, ..., 2^n - 1}。如果下標由1開始,意味著只能有2^n-1個下標可以使用。現代用32-bit/64-bit做下標可能不覺得是大問題,但在用8-bit/16-bit做下標的時候就是比較大的問題。
  2. 可對下標採用同余算術(Modular arithmetic)。