為什麼有些編程語言的數組要從零開始算？

12-13

像C語言的數組，Python的List都是從零開始記數。說實話從開始編程到現在，都沒想過為什麼這樣設計？Matlab又不是從零開始了。
這是工程上有什麼優勢嗎？

我提一些這裡暫時沒有提到的。

下標通常用無號整數表示。一個n位無號整數的表示範圍是{0, 1, ..., 2^n - 1}。如果下標由1開始，意味著只能有2^n-1個下標可以使用。現代用32-bit/64-bit做下標可能不覺得是大問題，但在用8-bit/16-bit做下標的時候就是比較大的問題。
可對下標採用同餘算術（Modular arithmetic）。

是 BCPL 作者的傑作，目的是減少編譯出的代碼里的一個減法指令。

這個問題，Dijkstra 大神在 1982 年就寫過一篇小文章了，題為 Why numbering should start at zero
總共也就 3 頁手寫，我就摘重點的大致翻譯一下：

為了表示一個自然數序列 2, 3, …, 12，排除掉中間的那三個點 (...)，總共有四種方式可供我們選擇：

a) 2 &<= i &< 13

b) 1 &< i &<= 12

c) 2 &<= i &<= 12

d) 1 &< i &< 13

有沒有什麼原因使得我們應該選其中的某一種而不是其他的呢？是的，的確有。觀察到 a) 和 b) 的優勢是不等式的上下界之差恰好是序列的長度。基於此，作為一個中間結論：在 a) 和 b) 兩種表達中中，兩個序列是鄰接的就意味著一個的上界等於另外一個的下界。但這些考量並沒有讓我們從 a) 和 b) 之中做出選擇，所以我們從頭開始。

存在一個最小的自然數。排除掉下界——就像 b) 和 d) 中那樣——就會使得一個從最小的自然數開始的序列的下界變成非自然數。這樣的表達方式很難看，所以對於下界應該更傾向於 &<=，就像 a) 和 c) 那樣。現在，考慮一下從最小的自然數開始的序列：假如包含上界，當序列縮小成空序列時，就會使得 c) 不那麼像自然數集。這樣的表達方式也很難看，所以對於上界應該更傾向於 &<，就像 a) 和 d) 那樣。綜上所述，我們應該傾向於使用 a) 的表達方式。

當處理長度為 N 的序列時，我們期望通過下標來區分它的元素。下一個惱人的問題就是，我們該給它的第一個元素賦予什麼下標值？使用 a) 的表達方式，當下標從 1 開始時，下標範圍為 1 &<= i &< N+1；當下標從 0 開始時則是 0 &<= i &< N，更好看。所以，讓我們將序號從 0 開始：一個元素的序號（下標）等於序列中在它前面的元素個數。這個故事的寓意是我們更應該——過了這麼多個世紀！——把 0 當作一個自然數。

反對這裡答案的為了效率。

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開始

@haha王提到Dijkstra那篇文章。Why numbering should start at zero。不過他並沒有翻譯全文。這裡補充全文翻譯。可能會有所錯漏。

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

為什麼應該從0開始計數

為了表示出自然數的子序列，2, 3, ... , 12，不使用省略記號那三個點號，我們可以選擇4種約定方式：

a) 2 ≤ i &< 13
b) 1 &< i ≤ 12
c) 2 ≤ i ≤ 12
d) 1 &< i &< 13

是否有什麼理由，使選擇其中一種約定比其它約定要好呢？是的，確實有理由。可以觀察到，a) 和 b)有個優點，上下邊界的相減得到的差，正好等於子序列的長度。另外，作為推論，下面觀察也成立：在 a)，b)中，假如兩個子序列相鄰的話，其中一個序列的上界，就等於另一個序列的下界。但上面觀察，並不能讓我們從a), b)兩者中選出更好的一個。讓我們重新開始分析。

一定存在最小的自然數。假如像b)和d)那樣，子序列並不包括下界，那麼當子序列從最小的自然數開始算起的時候，會使得下界進入非自然數的區域。這就比較醜陋了。所以對於下界來說，我們更應該採用≤，正如a)或c)那樣。現在考慮，假如子序列包括上界，那麼當子序列從最小的自然數開始算起，並且序列為空的時候，上界也會進入非自然數的區域。這也是醜陋的。所以，對於上界，我們更應該採用 &<, 正如a)或b)那樣。因此我們得出結論，約定a)是更好的選擇。

討論：Mesa是由Xerox PARC(施樂帕克研究中心)開發出的編程語言，以上4種表示整數區間的方式，在Mesa中，全部都有專門的記號。使用Mesa的大量經驗指出，採用另外三種表示方式，會不斷引出拙劣和錯誤的代碼。因此，現今有經驗的Mesa程序員強烈建議，不要去使用後面三種特性，儘管它們也可以使用。不管是真是假，我也提出這個實踐證據，有些人在結論還沒有被實踐驗證時，會感覺有所不安。(討論結束)

當處理長度為N的序列時，我們希望通過下標去區分它的元素，下一個值得分析的問題是，最開始的元素應該給予什麼樣的下標值。我們依然採用a)的約定，當下標從1開始時，下標區間是 1 ≤ i &< N + 1；而當從0開始時，可以得到一個更漂亮的區間 0 ≤ i &< N。所以，讓我們的序數從0開始：一個元素的序數(下標)，等於序列中，在它前面的元素個數。這個故事提醒我們，在經過這麼多個世紀之後，最好將0當成最自然的數字。

討論：很多編程語言對於計數的細節並沒有足夠的重視。在FORTRAN語言中，下標總是從1開始；而在PASCAL語言中，採用了約定c)；距今更近的語言SASL, 倒退到FORTRAN的方式：在SAL中，序列也是在正整數上進行操作。(討論結束)

最近的一次意外事件，促使我作出以上分析。當時，我所在大學的一個數學同事，並非計算機學家，情緒激動地指責一個年輕的計算機學家「迂腐」，因為計算機學家出於習慣而從0開始計數。我的數學同事將一些出於理性考慮後而自覺採用的合理約定，視為挑釁。(就連「...結束」這種約定，也視為挑釁。「...結束」這種約定是有用的：我就知道有個學生，他想當然地認為問題在第一頁試卷中結束，而差點沒有通過考試。) 我認為Antony Jay陳述得對：「在眾人共同組成的宗教中，異教徒必須被驅逐出去，並非因為他們可能是錯的，而是因為他們可能是對的。」

今天看到《Algorithms》1.1 中的一個 QA：

Q. Why do array indices start at 0 instead of 1?
A. This convention originated with machine-language programming, where the address of an array element would be computed by adding the index to the address of the
beginning of an array. Starting indices at 1 would entail either a waste of space at the
beginning of the array or a waste of time to subtract the 1.

----

這個和數組訪問的方式有關，數組是存在內存里的，如何訪問一個內存，只需要拿到這個內存的地址就可以了。
但是如何拿到第i個元素的地址呢，拿到數組的首地址，加上相對偏移就能計算出第i個元素的地址，這個偏移比較好算，因為每個元素的大小都是一樣的，就用元素大小乘以元素個數就能獲得偏移量了。
數組內存結構就是連續排列的很多內存塊。則可知：
第1個元素的地址=首地址a
第2個元素的地址=首地址a + 1*元素大小
第3個元素的地址=首地址a + 2*元素大小
第4個元素的地址=首地址a + 3*元素大小
第5個元素的地址=首地址a + 4*元素大小
...............
第i個元素的地址=首地址a + (i-1)*元素大小

所以如果用1來做元素第一個編號在計算內存地址的時候總會進行一次減法，用0就不會，所以用違背常規的方法換來了計算速度。

用反彙編也可以得到證實。

不從零開始的才是逗逼。

不從零開始的設計初衷可能是為了讓人感覺自然，貼近自然人的習慣。但是在大多數語言都從0開始計算下標的時候，不從0開始的反而不自然了。

從效率上來說，從0開始是效率最高的，下標數直接就是存儲位置的偏移量；從1開始還得下標減1才是偏移量，性能差異雖然微乎其微，但終究不是最直接的方式。

我是跟著來搞笑的。

換我這種渣渣寫c語言的編譯器的話，我絕對願意將數組定為0開始，地址計算方便多了，編譯器好寫多了，反正是c語言這麼接近彙編的東西是吧……所以不妨我們為了方便就這麼規定了吧，哼，才不是因為懶呢！

忘記是哪本書里寫的了

最初下標從0開始是為了將就編譯器設計者，因為偏移量的概念已經在他們的腦海里根深蒂固了

其實無所謂從0或1開始，都是習慣

數組的下標應該是從0還是從1開始？我提議的妥協方案是0.5，可惜他們未予認真考慮便一口回絕。—— Stan Kelly-Bootle

補充一點
模運算：
以下標為0開始的時候：
a[i mod N]
以下標為1開始的時候：
a[i mod N + 1]

如果是c語言，《c專家編程》中說是為了編譯器的方便。畢竟，c一開始就是用來寫編譯器的！

不是為了方便計算地址的偏移量嗎？

在字元串截取函數中這個問題會得到直觀的理解。第一個字,第二個字,第三個字——下標數字應該理解成那個逗號分割位置的編號，而不是位置本身的編號。否則你說1是第一個字的左邊還是右邊？
不喜歡內存這種底層+歷史原因，因為那並不能解釋為什麼後來不改掉。

也有從1開始的，比如Lua

從哪個開始算不一回事情自然數都是從1開始算得說白了從0開始算不過是為了指針使用方便因為arr（0）得地址和arr地址一樣如果 arr +1 就是第二個元素了？簡單說比arr地址多1得地址代表第二個變數，這樣更符合邏輯？

彙編的書一般都有提及到數組的實現，的確是從0開始性能要來得高一些。
數組第一個元素的內存地址就是數組起始內存地址+0。