Две задачи, которые кажутся похожими

В прошлых уроках мы наткнулись на важную разницу. Достать элемент по индексу — мгновенно: компьютер знает адрес и идёт прямо туда. А искать элемент по значению — приходится перебирать ячейки одну за другой, пока не найдём. Сейчас мы посмотрим, насколько велика эта разница. И ответ вас удивит: она не «немного больше», она огромна.

Возьмём конкретный пример. У нас есть список чисел, и мы хотим узнать: «есть ли в нём число 777?». Если список не отсортирован (числа лежат как попало), у нас нет адреса — мы вынуждены смотреть каждое число подряд: первое? не оно. второе? не оно. И так до тех пор, пока не найдём или не дойдём до конца.

числа = [10, 88, 5, 777, 42, 9]

def искать_перебором(данные, цель):
    for число in данные:
        if число == цель:
            return True
    return False

print(искать_перебором(числа, 777))
print(искать_перебором(числа, 999))

Вывод:

True
False

В худшем случае — когда числа 777 в списке нет — мы посмотрим все элементы. Если в списке миллион чисел, мы заглянем в миллион ячеек. Вот это «заглянуть во все» и есть источник медленности.

Считаем на пальцах: 1000 против 1 миллиона

Давайте прикинем, сколько «заглядываний» нужно в худшем случае. Не в секундах — просто сколько раз мы посмотрим на элемент.

Поиск перебором (число неизвестно где):

• список из 1000 элементов: до 1000 заглядываний;
• список из 1 000 000 элементов: до 1 000 000 заглядываний.

Стало в тысячу раз больше данных — и работы стало в тысячу раз больше. Перебор «растёт вместе с данными»: удвоили список — удвоили работу, увеличили в миллион раз — в миллион раз больше заглядываний.

Теперь доступ по индексу (мы знаем номер, как из прошлого урока):

• список из 1000 элементов: 1 заглядывание;
• список из 1 000 000 элементов: 1 заглядывание.

Размер данных вырос в тысячу раз — а работы столько же, одно действие. Доступ по индексу не зависит от размера списка.

Вот эта разница и есть суть. Представьте две задачи на работе:

• «Дай мне 500-ю строку из файла, я знаю номер» — мгновенно.
• «Найди в файле строку, где упоминается заказ №777, я не знаю где» — придётся читать файл, пока не наткнёшься.

На маленьком файле обе задачи кажутся одинаково быстрыми. На файле в миллион строк первая всё ещё мгновенна, а вторая заставит компьютер прочитать до миллиона строк. Та же программа, те же данные — но одна задача «не замечает» размера, а вторая «давится» им.

Почему на маленьких данных разницы не видно

Тут кроется ловушка, в которую попадают все новички. На списке из десяти элементов перебор и доступ по индексу работают одинаково мгновенно — глазом не отличить. Поэтому легко решить: «да какая разница, всё быстро».

Разница прячется до тех пор, пока данные маленькие, и вылезает, когда данных становится много. Перебор на 10 элементах — это 10 заглядываний, доля микросекунды. Перебор на 100 миллионах — это 100 миллионов заглядываний, и вот уже программа думает заметное время. А доступ по индексу как был одним действием, так и остался — хоть на 10, хоть на 100 миллионах.

Поэтому профессионалы выбирают структуру данных и способ поиска с расчётом на большие данные, даже если сейчас данных мало. Сегодня в таблице тысяча строк, через год — десять миллионов, а код остался прежним. Если он «растёт вместе с данными», в один день он перестанет успевать.

Примечание: именно поэтому существует сортировка и специальные структуры данных. Если список заранее отсортирован, искать в нём можно гораздо умнее, чем перебором, — не заглядывая во все элементы. А словарь (dict) в Python умеет находить значение почти как «по адресу», даже без сортировки. Об этих приёмах — дальше в курсе.

Попробуй сам

Сравним перебор на разных размерах и почувствуем, как он растёт. Будем искать число, которого в списке нет (худший случай — заглянуть во все):

import time

for n in [1000, 100_000, 10_000_000]:
    данные = list(range(n))      # числа от 0 до n-1
    цель = -1                    # такого числа нет -> переберём всё

    старт = time.perf_counter()
    найдено = цель in данные     # это и есть перебор по списку
    прошло = time.perf_counter() - старт

    print(f"n={n:>10}: перебор занял {прошло*1000:.3f} ms")

# Для сравнения: доступ по индексу на самом большом списке
большой = list(range(10_000_000))
старт = time.perf_counter()
_ = большой[9_000_000]           # знаем индекс -> мгновенно
прошло = time.perf_counter() - старт
print(f"доступ по индексу на 10M: {прошло*1000:.6f} ms")

Примерный вывод (числа на вашей машине будут другими, но пропорции — те же):

n=      1000: перебор занял 0.008 ms
n=    100000: перебор занял 0.700 ms
n=  10000000: перебор занял 70.000 ms

доступ по индексу на 10M: 0.000200 ms

Посмотрите на перебор: данные выросли в 100 раз (с 1000 до 100000) — и время выросло примерно в 100 раз. Ещё в 100 раз больше данных — ещё примерно в 100 раз больше времени. Перебор честно растёт вместе с размером. А доступ по индексу на десяти миллионах элементов всё равно занимает крошечную долю миллисекунды — он размера просто не замечает.

Мостик: дальше будет Big-O

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

Поэтому программисты придумали короткую запись для этих идей — она называется Big-O нотация. «Растёт вместе с данными» записывают как O(n). «Не зависит от размера» — как O(1). Это просто компактные ярлыки для того, что мы уже поняли интуитивно в этом модуле.

Следующий модуль — как раз про Big-O: формальную нотацию, её определение и классы сложности. Там появятся буквы, формулы и значки. И вот что важно знать заранее: если математика покажется тяжёлой — это нормально. Вы уже понимаете самое главное на уровне интуиции (камера хранения, перебор против индекса, рост вместе с данными). Формальная запись — это просто аккуратный способ записать ту же интуицию. Если в каком-то месте формулы собьют с толку — ничего страшного, вернётесь к этому модулю, перечитаете про ячейки и заглядывания, и формулы встанут на место.

Поздравляем — вы прошли вводный модуль и теперь готовы к формальной нотации Big-O. Увидимся в следующем модуле.