配列の範囲はなぜ0から始まり終端を含まないのか

プログラミング初心者にとってインデックスは難しい

私が大学に入ってプログラミングをはじめた時に、馴染めなかったことが2つあります。

Cであれば、

for (i=0; i<5; i++)

などと書くとループ出来るわけですが、

  1. なぜ、i<=4と書かないのか?
  2. どうしてiは0から始めるのか?

がしっくり来ませんでした。

この記事では、プログラミング初心者のみなさんに対して、 この書き方がプログラミングをする上で自然であることを納得させます。

半開区間: なぜrange(0,5)は5を含まないのか?

今どきCはないですよね。Pythonを使いましょう。 Pythonではrange(0,5)と書くと、0,1,2,3,4を順に生成してくれます。これを ジェネレータといいます。 これを使うことで、ループを実装することが出来ます。

なぜ、このrange(0,5)は0,1,2,3,4,5と5まで生成してくれないのか?それについて考えましょう。

まず、この書き方を半開区間(half-open range)といいます。 もっと形式的に書くならば、[0,5)と書きます。 この概念に相当するものは、ほとんどの言語で用意されています。 Rubyならば0...5と書きますし、Rustならば0..5と書きます。

この書き方に違和感を覚えるのはおそらく、みなさんの頭の中で 配列がこう見えているからです。

https://d33wubrfki0l68.cloudfront.net/89c18321f8bca16a7682f97828291e9d41fad395/e1b35/images/1572751685.jpg

しかし、こう見るとどうでしょうか?

https://d33wubrfki0l68.cloudfront.net/efcd001757f9fe75d0d9ec3d1d743777bedb935d/2e71d/images/1572751812.jpg

数学でグラフを書く時のX軸となんら変わりないことがわかります。

こう表現すると、[0,5)の範囲が長さ5であることがより明確になります。 一般に、[a,a+n)の長さはnです。

プログラミングでは、 配列のそれぞれの要素について考える時は、 上のように配列を見る方が良いことが多いですが、 範囲を考える時には、下のように考えると良いことが多いです。

例えば、分割統治法を考えてみましょう。分割統治法というのは、 1つの範囲(この場合は、[0,5))を2つの範囲(この場合は、[0,2)[2,5)) に分割して、それぞれで問題を解くという方法ですが、 以下のように書くと、半開区間で範囲を扱うことの良さがわかります。

https://d33wubrfki0l68.cloudfront.net/3bfd85f5a6b6ce922055a229d89b6507db6561dc/9fb40/images/1572752104.jpg

これならば、この2つの半開区間が連続していることが明らかです。 なぜならば1つ目の終端と、2つ目の始端が同じ数字だからです。

しかしもし、[0,1][2,4]などと閉区間で書いてしまうと、いまいち却ってわかりにくくなります。

例えば、[a,b)を真ん中あたりのkというインデックスで分割することを考えましょう。すると計算するまでもなく、 [a,k)[k,b)に分割すれば良いということがわかります。

前からm個とそれ以降に分割するというのであれば、[a,a+m)[a+m,b)です。 計算がとてもシンプルなことがわかります。

このように、半開区間で範囲を考える方が、アルゴリズムの考え方にフィットしやすいのです。

0オリジンとは?

ではなぜ配列のインデックスは0から始まるのでしょうか?

これはいくつか理由が考えられます。

1つは、低レイヤーのメモリアドレスの概念を持ち込んでいる。

もう1つは、 半開区間で範囲を表現することを前提とした場合、 [0,n)と書いた時に長さがnであることを明確になるから。

納得出来るならどちらでも良いと思います。 前者は、C言語の配列を勉強すれば、より深く理解出来ると思いますが、 後者で納得しても全く問題ないと思います。


このエントリーをはてなブックマークに追加

See also