Почему индекс начинается с нуля
Перейти к содержимому

Почему индекс начинается с нуля

  • автор:

Почему нумерация должна начинаться с нуля

Почему нумерация должна начинаться с нуля главное изображение

Чтобы обозначить последовательность натуральных чисел 2, 3, …, 12 без неприятного троеточия, по соглашению можно использовать следующие четыре варианта нотации:

Есть ли предпочтительные варианты? Да. Первый и второй варианты имеют преимущество: разница между обозначенным началом и концом последовательности равна длине последовательности. Также в этих вариантах при использовании смежных последовательностей можно сказать, что конец одной последовательности будет началом второй. Пока недостаточно данных, чтобы выбрать между первым и вторым вариантом, поэтому начнём сначала.

Есть наименьшее натуральное число. Во втором и четвёртом варианте исключены нижние границы последовательности. Это приводит к тому, что для последовательностей, которые начинаются с наименьшего натурального числа, смежные последовательности уходят из области натуральных чисел. Это неудобно и некрасиво, поэтому для обозначения нижней границы предпочтительно использовать знак ≤ как в первом и третьем варианте.

Теперь рассмотрим последовательности, которые начинаются с наименьшего натурального числа. Включение верхней границы здесь превращает пустую последовательность в неестественную. Это неудобно и некрасиво, поэтому для обозначения верхней границы предпочтительно использовать знак < как в первом и четвёртом варианте. Приходим к выводу, что первый вариант предпочтительный.

Обратите внимание, язык программирования Mesa, разработанный в Xerox PARC, имеет специальную нотацию для записи интервалов чисел с помощью всех четырёх соглашений, указанных выше. Опыт использования Mesa показал, что использование второго, третьего и четвёртого варианта приводит к ошибкам. Поэтому программисты при работе с Mesa используют для обозначения последовательностей первый вариант соглашения. Эта ремарка для тех, кому важно получить результаты практических экспериментов, а не только теоретические заключения.

Когда речь идёт о последовательности с длиной N, которую мы хотим определить по нижнему индексу, следующий важный вопрос касается того, какой индекс присвоить первому элементу. Придерживаясь первого варианта нотации, получаем нижний индекс 1 ≤ i < N+1 . Но если начать с нуля, получим диапазон 0 ≤ i < N , что выглядит более понятно и красиво. Так что давайте нумеровать с нуля. Порядковый номер элемента равен числу элементов, которые предшествуют ему в последовательности. Мораль истории в том, что ноль стоит считать самым натуральным числом.

Многие языки программирования разработаны без должного внимания к этой детали. В Fortran сабскрипты начинаются с 1 , в Algol 60 и Pascal принят третий вариант нотации. Более новый SASL использует вариант, принятый в Fortran. Последовательность в SASL одновременно является функцией положительных чисел. Жалкий подход!

Эту заметку я написал, когда один из моих коллег-математиков, но не информатик, упрекнул более молодых специалистов по информатике в педантизме из-за их привычки нумеровать последовательности с нуля. Он сознательно назвал самое разумное соглашение провокацией. Также соглашение «End of. » рассматривается как провокационное. Тем не менее оно полезное. Я видел студента, который чуть не провалился на экзамене, так как посчитал, что вопросы заканчиваются в конце первой страницы. Думаю, Энтони Джей был прав, когда заметил следующее: «В корпоративных религиях, как и в любых других, еретиков изгоняют не потому, что они неправы, а потому, что они могут быть правыми».

Адаптированный перевод статьи Why numbering should start at zero by prof.dr. Edsger W. Dijkstra.

Почему во многих языках индексирование начинается с 0?

Предположим, что у вас есть массив из целых чисел, каждое по четыре байта. Массив расположен в памяти последовательно. Чтобы получить элемент N, надо взят указатель на массив и прибавить к нему (N — 1) * 4 байт, или, если вести отсчет от нуля, просто N * 4 байта

14 авг 2016 в 18:12
@Etki: А почему не как ответ?
14 авг 2016 в 18:17
В электронике отсчет ножек многих микросхем тоже начинаются с 0. Я думал это связано.
14 авг 2016 в 18:17
На линейке первая цифра тоже 0! координата первого значения начинается с нулевой точки.
14 авг 2016 в 19:09

мне лень переводить, но большинство серьезных причин — приведено здесь quora.com/… И там ссылка на статью Дейкстры

14 авг 2016 в 19:38

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

В первую очередь потому, что с точки зрения реализации понятие «индекса» элемента в непрерывном агрегате напрямую связано с понятием «смещения» элемента от начала агрегата в памяти. Понятно, что смещение самого первого элемента агрегата равно нулю. Соответственно и индекс его разумно взять равным нулю.

Другими словами, как ни верти, но индекс первого элемента в агрегате все равно придется пересчитывать в значение 0 на машинном уровне. В такой ситуации реализация индексации с ненулевой базой будет всегда волей-неволей подразумевать неявное приведение ее к индексации с нулевой базой. В многих языках программирования просто не считают необходимым это делать. Зачем, действительно?

Отслеживать
ответ дан 14 авг 2016 в 23:03
AnT stands with Russia AnT stands with Russia
69.3k 3 3 золотых знака 63 63 серебряных знака 140 140 бронзовых знаков

При выделении динамической памяти в C/C++ возвращаемый указатель не обязательно указывает на начало выделенного из кучи участка памяти.

14 авг 2016 в 23:09

@hunter: А какое это имеет значение в данном случае? Главное, чтобы указатель указывал на начало пользовательской области памяти, т.е. на ту точку, от которой будут отсчитываться смещения. А то, что блок может также содерждать какие-то служебные области со служебными данными к данному вопросу не относится никак. Что именно вы хотели сказать?

14 авг 2016 в 23:11

то и хочу сказать что даже при выделении не фрагментированной области памяти из указателя на нулевой элемент рано или поздно может возникнуть необходимость получить указатель на ячейку памяти с меньшим адресом.

14 авг 2016 в 23:17

@hunter: Прекрасно. Но какое это имеет отношение к теме индексации? «Ячейка с меньшим адресом» не является частью пользовательских данных, и доступаться к ней путем отрицательной индексации пользовательских данных никто не будет (в здравом уме). Такая область памяти будет прекрасно доступна путем вычета некоего известного платформе смещения из указателя «пользовательского» уровня и все. Я по прежнему не вижу, какое это все имеет отношение к рассматриваемой теме или к моему ответу.

14 авг 2016 в 23:22

@avp: До языка С были языки B и BCPL с той же самой нулевой индексацией. Язык С унаследовал свой подход к массивам именно из B и BCPL, с одним важным изменением. В B и BCPL массивы физически реализовались через обычные указатели. В С физические указатели убрали, но стали их «эмулировать» (пресловутый «array type decay»). А все остальное в С осталось, как в B и BCPL именно для облегчения обратной совместимости с этими языками.

Почему в программировании счёт всегда начинается с нуля, а не с единицы

В проектах мы периодически говорим, что компьютер почти всё начинает считать с нуля, а не с единицы. Это значит, что первый элемент массива вызывается командой arr[0] , второй — arr[1] , а шестой — arr[5] . Объясняем, почему так.

Память, переменные и первый байт

Чтобы что-то посчитать, компьютеру нужно место, куда он будет записывать результаты подсчёта. Это место — какие-то ячейки памяти.

Физически ячейка памяти — это транзистор, у которого может быть два состояния: открытый или закрытый (как краны с водой). Эти состояния мы называем «логический ноль» и «логическая единица».

Минимальная ячейка, в которой может лежать единица или ноль, называется бит. Но в бите можно закодировать только 1 или 0 или «да/нет». Чтобы кодировать что-то более сложное, нужно взять не один бит, а группу. В компьютере принято объединять биты в группы по 8, такая группа называется «байт».

Получается, что байт — это 8 транзисторов памяти, которые компьютер интерпретирует как единое целое (например, число). Внутри байта находятся логические нули или единицы, стоящие в любом порядке.

Кодирование происходит в двоичной системе: в зависимости от расположения логических единиц и нулей подразумеваются разные числа в привычной нам десятичной системе счисления. Например:

00000000 — ноль, минимальное значение байта

11111110 — двести пятьдесят четыре

11111111 — двести пятьдесят пять, максимальное значение байта

Обратите внимание, что минимальное значение, которое можно хранить в одном байте — не единица, а именно ноль.

Логика компьютера

Теперь представьте: компьютер исполняет программу, где ему нужно обойти какой-нибудь массив и что-то там подсчитать. Для обхода массива ему нужна область памяти для подсчёта. Что происходит дальше:

  1. Процессор находит свободное место в памяти и запоминает: «Вот тут у меня будет лежать счётчик для этого массива».
  2. Место в памяти обнуляется, чтобы там не было никакого мусора. Мало ли там какие данные лежали от прошлой программы?
  3. Обнулённый счётчик — это 00000000, то есть ноль.
  4. Раз счётчик уже есть и у него есть валидное значение «ноль», то компьютер начинает считать именно с нуля.

Благодаря тому что компьютер начинает считать с нуля, в 8 бит он может поместить 256 значений: от 0 до 255. Если бы компьютер считал от 1 до 255, в 8 бит поместилось бы 255 значений — то есть на одно меньше.

Можно ли всё-таки считать с 1?

Можно, но это необычно. Чтобы компьютер начал считать всё с единицы, нам нужно объяснить ему, как это делать. Например, подход может быть таким:

  1. Мы создаём массив, в котором элементов на один больше, чем нам нужно. Например, если мы собираемся там хранить 100 чисел, делаем массив на 101 элемент.
  2. Когда начинаем его заполнять, то первым элементом мы указываем единицу: arr[1] = 15 , вторым — двойку и так до конца.
  3. Так мы заполним 100 элементов, которые можно начинать считать с единицы, а нулевой элемент останется незаполненным.

При этом с точки зрения компьютера в массиве всё равно будет 101 элемент, которые он будет начинать считать с нуля. Но человеку так может быть удобнее, когда номера элементов совпадают с его порядковым номером.

Как ошибаются из-за счётчиков с нуля

Самая частая ошибка при начале счёта с нуля — путать между собой длину массива и индекс последнего элемента. Следите за руками:

  • Мы сделали массив на 100 элементов.
  • Первый элемент массива — это arr[0] , а последний — arr[99] .
  • Когда мы запросим длину массива, то в ответ получим число 100.
  • А если мы обратимся к arr[100] , то получим ошибку, потому что элемента с индексом 100 в массиве нет.

Эта же ошибка встречается и в циклах, когда нам нужно перебрать все индексы с первого до последнего. Чаще всего начинают считать с единицы и пропускают нулевой элемент.

Как грамотно обойти массив с помощью счётчиков на разных языках (и не запутаться в единицах и нулях)

Представим, что у нас есть массив arr[] , в котором хранится 100 чисел, и нам нужно вывести их на экран.

Классический алгоритм такой:

  1. Заводим переменную для счётчика, обычно её обозначают буквой i .
  2. В i записывается ноль. Начинается цикл.
  3. Внутри цикла берётся массив. Из него достаётся элемент под номером i , то есть соответствующий текущему номеру прохода цикла. Так как в начале алгоритма в счётчике ноль, то мы получим нулевой элемент цикла (то есть по-человечески — первый).
  4. Когда шаг цикла выполнен, в переменную i добавляется единица.
  5. Теперь цикл повторяется, но из массива достаётся не нулевое, а первое значение (то есть по-человечески — второе).
  6. Цикл повторяется до тех пор, пока i меньше, чем длина массива.

Есть хитрость в выходе из цикла: значение счётчика i должно быть меньше, чем длина массива (а не «меньше или равно»).

Дело в том, что длина цикла измеряется по-человечески — 1, 2, 3 и далее. А счётчик работает по-компьютерному — 0, 1, 2… Это значит, что в массиве из 100 чисел длина массива будет 100, а максимальное значение счётчика — 99.

Пример такого кода в JavaScript:

for (var i = 0; i++, i
for i in range(len(arr)): print(arr[i])
for(int i = 0; i

Обход массивов вообще без счётчиков (и связанных с ними нулей)

В некоторых языках есть более компактная версия этой конструкции, которая буквально означает «Обойди этот объект». Вот примеры в JavaScript:

for (var i in arr)
for i in arr: print(i)

Здесь нужно смотреть на слово in, что буквально означает «по всем составляющим этого объекта». В разных языках у него разное значение

  • В JavaScript в переменную i положат номера элементов массива arr[] , то есть эта переменная будет работать как счётчик. Фраза i in arr означает «для каждого номера элемента массива arr: положи этот номер в переменную i ».
  • В Python фраза i in arr означает «возьми сами элементы массива arr и положи их по очереди в переменную i »

То есть JavaScript использует for…in для простого управления счётчиками, а Python вообще избавляется от понятия счётчика и сразу отдаёт в переменную то значение, которое он сейчас перебирает.

Если совсем просто:

  • Допустим, у нас есть массив arr[] , который состоит из чисел 2, 12, 85, 6.
  • В конструкции на JavaScript в переменной i будут числа 0, 1, 2, 3.
  • А в конструкции на Python в переменной i будут 2, 12, 85, 6.

Но это если уже совсем угореть. Всё, хорош, и так понятно: компьютеры считают с нуля.

Получите ИТ-профессию

В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.

Почему массивы начинаются с нуля

Самое очевидное объяснение: индекс — это смещение относительно начала массива. Так элементы массива легче адресовать в памяти.

Проверим это на C.

#include int main() < int data[3] = ; int i = 0; printf("Array address: %p\n", data); do < printf("Array[%u] = %p\n", i, (void *)(&data[i])); i++; >while(i

Array address: 0x7ffd7c514a6c
Array[0] = 0x7ffd7c514a6c
Array[1] = 0x7ffd7c514a70
Array[2] = 0x7ffd7c514a74

Как первый (нулевой) элемент, так и сам массив находятся по одному и тому же адресу, поскольку 0-й элемент удалён на 0 элементов от начала. Эта связь между указателями и массивами в C настолько тесная, что их даже можно рассматривать вместе.

Однако это ответ на вопрос «зачем», а не «почему». Нумеровать массивы с нуля стали не сразу. Удивительно, но развитие такого простого вопроса не умещается в предложении или абзаце.

Потому что так удобнее

К началу 1960-х годов сформировалось три подхода к организации структуры, которую сегодня мы называем статическим массивом:

    Исчисление с 0. Нижняя граница массива начинается с нуля.

Непривычно для обывателя, если это не житель Германии, свыкшийся с нумерацией этажей в зданиях. Последний элемент массива из, скажем, 8 элементов имеет номер 7.

Не всё так однозначно. Единообразия даже у самых первых языков программирования не существовало:

  1. Нумерация с нуля: LISP 1.5, APL (допускает выбор при запуске программы).
  2. Нумерация с единицы: APL, Бейсик, ранний Фортран.
  3. Произвольные границы: Алгол-60, затем Фортран, CPL, SIMULA, CLU, PL/1, Кобол, Паскаль, Алгол-68, JOVIAL.

Конечно, это не самый сильный аргумент. Часто языки снабжались синтаксическим сахаром для нумерации с 1. К примеру, в Алголе массив V[0:3] начинается с 0, а массив V[3] — с 1.

Создатель языка APL Кеннет Айверсон в книге «A Programming Language» объясняет, почему далее по тексту он будет пользоваться нумерацией элементов массива с нуля. При этом язык допускает отсчёт как с единицы, так и с нуля. Айверсон приводит уже описанный выше аргумент о сдвигах в позиционной нумерации.

Тем не менее и в эпоху до C звучали предложения выбирать нумерацию с 0. Логично предположить, что это была историческая неизбежность, до которой оставалось несколько лет.

Потому что парусные регаты мешали вычислениям

В 1967 году Мартин Ричардс впервые реализует компилятор своего детища — BCPL (Basic Combined Programming Language). Этот язык программирования был призван исправить проблемы созданного в начале шестидесятых языка CPL путём отказа от технологий, затрудняющих компиляцию.

Первый компилятор BCPL был написан для операционной системы CTSS машины IBM 7094 Массачусетского технологического института. На тот момент компьютеры — это уже не целые комнаты и электронные лампы, но всё ещё огромные шкафы с транзисторами и консоли управления без экранов. Ресурсов серии 7090 хватило, чтобы запустить американца в космос. Но мощность измерялась в тысячах машинных слов, микросекундах тактов и килофлопсах, а цена — в миллионах долларов.

В пятидесятых и шестидесятых IBM выдавала институту щедрые скидки на свои научные компьютеры или даже предоставляла их бесплатно. В 1963 году в МТИ поставили IBM 7094. На компьютер уговор был такой: 8 часов в сутки получают специалисты института, 8 часов — другие колледжи и университеты Новой Англии, а третью смену отдавали самой IBM для личных нужд.

На этом особенности не кончались. Несколько раз в год IBM обсчитывала регаты: президент IBM соревновался в заплыве на больших яхтах в проливе Лонг-Айленд, и каждое из судов получало очки гандикапа по специальной сложной формуле. Когда в вычислительный центр приходило задание, операторам полагалось всё бросить и запустить вычисления этих очков.

Машинный зал с установленным компьютером IBM 7094 в Колумбийском университете США. Фотоархив

Вообще, и без этого был шанс не получить результат вычислений. Изначально 7094 работал в режиме пакетной обработки. Вспомогательная система на IBM 1401 загружала пакет задач с перфокарт на ленту, а затем запускала задачи одну за другой и записывала результаты для последующей печати. Для каждой задачи приводилась оценка времени. Если задача выходила за пределы отпущенного, её принудительно прерывали.

В итоге компиляция в BCPL была оптимизирована по максимуму. То есть и указатели на элементы массива должны максимально близко походить на машинный код, без необходимости вычитать единицу при указании на элемент массива. Хотя во время выполнения программы не играет роли схема организации массивов, нумерация с нуля могла появиться для оптимизации времени компиляции.

Впрочем, конкретно эта версия — лишь гипотеза Майка Хойе. Ей нет никаких подтверждений от собствено Ричардса или хотя бы упоминаний в литературе. Мартин Ричардс в переписке с Хойе лишь приводит общие соображения о том, что он хотел достичь близости к машинному коду, поэтому указатель p и p + 0 — это одна и та же переменная. Ни на какие яхты Ричардс не жалуется.

К тому же на момент появления первого компилятора BCPL уже была готова операционка Compatible Time-Sharing System. В ней на одной машине с разделением времени компьютер выполняет одну задачу за один раз, но с оптимизацией ввода и вывода, чтобы паузы одного пользователя заполнялись работой других. Это уже не былая пакетная обработка задач.

Точно известно, что в дальнейшем BCPL значительно повлиял на все современные языки программирования.

В 1969 году Кен Томпсон урезал функциональность BCPL до языка B. В дальнейшем, для развития операционной системы Unix, Деннис Ритчи улучшил B добавлением функций PDP-11, в результате чего и получился C. Полвека спустя список языков, на которые оказал влияние C, занимает в «Википедии» целую страницу.

В языке BCPL v!5 и 5!v совпадают, поскольку являются указателем на !(v+5) или !(5+v) . Аналогично в C v[5] эквивалентно 5[v] .

Потому что так предложил Дейкстра

В 1982 году Эдсгер Дейкстра опубликовал статью «Почему нумерация должна начинаться с нуля». В ней он низверг как нумерацию с единицы, так и произвольные границы индексов. Очевидно, что Дейкстра — не человек, который легко поддаётся влиянию C, но также он раскритиковал Алгол-60, своё собственное детище, и Паскаль.

Известно, что Дейкстра ближе к концу жизни всё больше писал от руки, а не набирал тексты на машинке. Архив рукописей Эдсгера Вибе Дейкстры

Если необходимо записать интервал натуральных чисел 2, 3, …, 12 без опухоли из точек, возможны четыре варианта:

Затем автор замечает, что для нижней границы предпочтителен знак «⩽», поскольку наименьшее натуральное число существует. В противном случае, если последовательность начинается с наименьшего натурального числа, нижняя граница не будет натуральным числом.

Затем статья делает вывод, что из соображений простоты для последовательности из N членов предпочтительнее диапазон 0 ⩽ i < N , а не 1 ⩽ i < N+1 .

Куда менее известный документ — это полушуточная техническая заметка от 1 апреля 1980 года IEN 137 под названием «О священных войнах и призыв к миру» [On Holy Wars and a Plea for Peace].

В заметке Дэнни Коэн приводит интересный аргумент: в системе счисления с основанием b при отсчёте с нуля первые b ^ N неотрицательных чисел представляются ровно N цифрами. Например, если речь про двоичную запись, то 2 ^ 3 = 8 , и восьмой элемент массива будет иметь номер 1112, а не 10002. Понятно, что с такими преобразованиями легко бы мог справиться компилятор.

Потому что так более элегантно

Это объяснение может раздражать субъективностью. Соображения о красоте у каждого свои и совпадать не обязаны. Но авторы языков программирования — тоже люди со своими предпочтениями.

В конце восьмидесятых Гвидо ван Россум при создании Python как учёл свой предыдущий опыт с языком ABC, так и задумал привлечь аудиторию хакеров от мира Unix и C.

С 1983 года Гвидо работал в Центре математики и информатики в Амстердаме над реализацией языка ABC. Проект ставил целью создать язык программирования, пригодный для обычных людей, но не настолько ужасно реализованный, как Бейсик. Нумерация массивов в ABC начиналась с единицы. Такой же схемы придерживались другие знакомые Россуму языки — Алгол, Фортран и Паскаль.

Однако в вышедшем в 1991 году Python нумерация начинается с нуля, а не единицы. Получилось так в результате долгих размышлений.

Одна из причин — слайсы. Чаще всего при создании слайса используются операции «получить первые n элементов» и «начиная с i, получить следующие n элементов». При этом первый случай эквивалентен i == первый индекс . Гвидо посчитал, что лучше, если обе операции возможны без лишней головной боли в виде коррекции +1 и −1.

Если первый элемент имеет номер 1, то возможно указывать первый элемент и число элементов, которые нужно получить. Россум уже был знаком с подобным по ABC и вполне мог бы положиться на этот опыт.

Тем не менее автора Python очаровал синтаксис слайсов полуоткрытого интервала, если нумерация начинается с нуля: a[:n] (или a[0:n] ) и a[i:i+n] . К примеру, строку a легко разбить на три части a[:i] , a[i:j] и a[j:] .

Заметим, что в воспоминаниях Гвидо не приводит ни призывы гениев информатики, ни практики других языков, ни принципы, заложенные мастодонтами компьютерных вычислений шестидесятых. Зато слово «элегантность» в пяти абзацах его объяснения встречается 3 раза.

Почему же массивы начинаются с нуля?

Так исторически сложилось.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *