Память — это длинный ряд ячеек
В прошлом уроке мы выяснили, что достать элемент списка по индексу — очень быстро, как протянуть руку к нужной полке. Теперь разберёмся, почему. Для этого надо понять, что такое память компьютера. Звучит страшно — но на самом деле всё просто.
Представьте камеру хранения на вокзале. Это длинный ряд одинаковых ячеек, и у каждой свой номер: ячейка 0, ячейка 1, ячейка 2, и так до самого конца. В каждую ячейку можно положить одну вещь. Память компьютера устроена ровно так же: это огромный ряд пронумерованных ячеек, в каждую кладётся маленький кусочек данных.
Номер ячейки называют адресом. Адрес — это просто «какая по счёту ячейка». Когда программа хочет что-то запомнить, она кладёт это в свободную ячейку и запоминает её номер. Когда хочет достать обратно — идёт по этому номеру.
Главное свойство такой камеры хранения: чтобы открыть ячейку, вам не нужно проходить мимо всех предыдущих. Если вам нужна ячейка номер 500, вы идёте прямо к ней. Не открываете по очереди 0, 1, 2, …, 499. Вы просто смотрите на табличку с номером и подходите. Это и есть секрет скорости.
Почему доступ по номеру мгновенный
Сравните два варианта найти вещь.
Вариант первый — вещи свалены в большой мешок без всякого порядка. Чтобы найти красный шарф, вы достаёте предметы один за другим: не тот, не тот, не тот… Чем больше вещей в мешке, тем дольше поиск. Если шарф лежит на самом дне, вы переберёте вообще всё.
Вариант второй — камера хранения с номерами. Вы заранее знаете: «красный шарф в ячейке 47». Вы идёте к ячейке 47 и открываете её. Сколько бы ни было ячеек — десять или миллион — вы доберётесь за одно действие, потому что номер сразу говорит, куда идти.
Компьютер с памятью работает по второму варианту. Когда вы пишете список[47], компьютер не перебирает элементы с начала. Он знает адрес начала списка в памяти и просто отсчитывает: «начало плюс 47 шагов». Получается адрес нужной ячейки, и он сразу её открывает.
Примечание: «отсчитать 47 шагов от начала» компьютер делает одной операцией, а не сорока семью. Он не шагает по одному — он сразу вычисляет нужный адрес. Поэтому неважно, просите вы элемент 5 или элемент 500000 — скорость одна и та же.
Почему элементы списка лежат подряд
Чтобы трюк с «началом плюс 47 шагов» работал, элементы списка должны лежать в памяти подряд, в соседних ячейках. Как вагоны одного поезда, сцепленные друг за другом: вагон 0, вагон 1, вагон 2.
Представьте список из четырёх чисел. В памяти он мог бы выглядеть так (адреса условные):
адрес: 1000 1001 1002 1003
значение: 10 20 30 40
индекс: 0 1 2 3Список начинается с адреса 1000. Хотите элемент с индексом 2? Компьютер считает: 1000 + 2 = адрес 1002, идёт туда, забирает 30. Хотите индекс 0? 1000 + 0 = 1000, забирает 10. Всё это — одно простое сложение и один поход в память. Быстро и одинаково для любого индекса.
Именно поэтому в прошлом уроке мы сравнивали список с полкой, где у каждой банки своё место. Полка работает быстро не потому, что банок мало, а потому, что вы знаете адрес и идёте прямо к нему.
А почему тогда поиск бывает медленным
Хороший вопрос возникает сам собой: если по номеру так быстро, почему вообще что-то бывает медленно? Потому что не всегда вы знаете номер.
Вернёмся к мешку и камере хранения. Если вопрос «что лежит в ячейке 47?» — вы отвечаете мгновенно, идёте по номеру. Но если вопрос «в какой ячейке лежит красный шарф?» — номер вам неизвестен, и придётся открывать ячейки одну за другой, пока не найдёте. Это совсем другая задача, и она медленная.
В программе это та же разница:
список[47]— «дай элемент с индексом 47». Номер известен. Мгновенно.- «найди в списке число 88» — номер неизвестен, надо перебирать. Медленно, если список большой.
Эту разницу — между «знаю адрес» и «надо искать» — мы подробно разберём в следующем уроке. Пока запомните: доступ по индексу быстрый именно потому, что номер ячейки сразу указывает, куда идти, и не нужно ничего перебирать.
Память — это длинный ряд пронумерованных ячеек. Элементы списка лежат в соседних ячейках подряд. Доступ по индексу мгновенный, потому что компьютер вычисляет адрес как «начало плюс индекс» одной операцией и идёт прямо туда — не перебирая остальные элементы.
Попробуй сам
Проверим интуицию «номер сразу указывает куда идти» прямо в Python. Доступ по индексу не зависит от того, маленький список или огромный:
маленький = list(range(10)) # [0, 1, ..., 9]
огромный = list(range(10_000_000)) # десять миллионов чисел
# Достаём по индексу из обоих
print(маленький[5])
print(огромный[5_000_000])
print(огромный[-1]) # -1 это последний элементВывод:
5
5000000
9999999Обратите внимание: достать элемент из списка на 10 миллионов чисел не медленнее, чем из списка на 10. Компьютер не «добирается» до середины огромного списка — он сразу вычисляет адрес и идёт туда. Это и есть мгновенный доступ по индексу.
Поэкспериментируйте: индекс -1 означает «последний элемент», -2 — «предпоследний». Попробуйте огромный[-2]. Компьютер всё равно сразу вычислит адрес и не будет ничего перебирать.
В следующем уроке мы возьмём эту разницу — «по индексу» против «искать перебором» — и посмотрим на числах, насколько она огромна, когда данных становится миллион.