Сколько операций в секунду

В задаче сказано: n до 2·10⁵, лимит времени — секунда. Пройдёт ли решение, которое перебирает все пары? Отвечать на такой вопрос нужно до того, как написан код, — иначе можно потратить час на решение, которое в лимит не уложится никогда. Подвигайте n и посмотрите, где на шкале времени окажутся разные алгоритмы: от наносекунды до возраста Вселенной.

При n = 2·10⁵ перебор пар — это строка n²: от десятка секунд до минут даже на Go и десятки минут на Python. Алгоритм за n log n укладывается в доли секунды на любом языке. А теперь поставьте n = 20: здесь даже 2ⁿ — около миллиона шагов, доли секунды. Ограничения в условии задачи почти всегда подсказывают, какой сложности решение ждут.

Идея

Время ≈ число шагов ÷ скорость. Число шагов даёт сложность алгоритма: подставьте n в O(n log n) или O(n²). Скорость — сколько простых шагов в секунду делает язык: у Python это десятки миллионов, у Go — от сотен миллионов до миллиардов. Ответ получается с точностью до порядка, но для решения «пройдёт или нет» этого почти всегда хватает.

Пример. Перебор пар при n = 2·10⁵ — это n²/2 = 2·10¹⁰ проверок. При 10⁹ шагов в секунду — двадцать секунд, при 10⁷ — полчаса. Сортировка тех же данных — n log₂ n ≈ 3,5·10⁶ сравнений: по оценке, тысячные доли секунды на Go и десятые на Python. На деле Python сортирует быстрее оценки: встроенная сортировка написана на C, и её шаги стоят как в компилируемом языке. Разница между алгоритмами здесь больше, чем между языками, и так бывает почти всегда.

Сколько стоит простая операция

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

Все линии идут под одним наклоном — время растёт пропорционально n, — но на разной высоте. Высота и есть цена операции. В Python все четыре вида стоят одного порядка — сотня-другая наносекунд: каждая строка цикла проходит через интерпретатор, и эта цена перекрывает разницу между самими операциями. В Go чтение массива из кэша — доли наносекунды, а поиск в map в 30–40 раз дороже: тут уже видна настоящая работа процессора и памяти.

Отсюда правило, которое знает каждый участник олимпиад: компилируемый язык делает порядка 10⁸–10⁹ простых шагов в секунду, Python — порядка 10⁷. Шаг настоящего алгоритма обычно дороже одной операции из замера: внутри него несколько сравнений, обращения к памяти и ветвления. Поэтому оценку честнее делать с запасом: считать 10⁸ шагов в секунду для Go и 10⁷ для Python.

Сколько успеет за секунду

Перевернём вопрос: какое наибольшее n успевает алгоритм данной сложности за секунду? Для этого нужно решить неравенство «шаги(n) ≤ скорость» — а это двоичный поиск по ответу: удваиваем n, пока помещается, потом делим отрезок пополам.

Таблица под сценой выше делает то же самое на измеренных скоростях. Запомнить стоит грубую версию для компилируемых языков:

• n ≤ 10–12 — можно перебирать все перестановки, O(n!);
• n ≤ 20–25 — все подмножества, O(2ⁿ);
• n ≤ 500 — три вложенных цикла, O(n³);
• n ≤ 5000–10⁴ — два вложенных цикла, O(n²);
• n ≤ 10⁶ — сортировка и логарифмические структуры, O(n log n);
• n ≤ 10⁷–10⁸ — только линейный проход.

Для Python границы сдвигаются: у полиномиальных алгоритмов — в разы (для n² — примерно в √10 ≈ 3 раза, для n — в 10), а у экспоненциальных всего на несколько единиц: 2ⁿ растёт так быстро, что десятикратная разница в скорости — это лишние три-четыре элемента.

Насколько точна оценка

Оценка верна с точностью до порядка — раз в пять-десять в обе стороны. Сама оценка ничего не стоит: пара умножений в уме. Но надо понимать, что она не учитывает:

• Константу внутри O. O(n log n) у сортировки слиянием и у быстрой сортировки — разные секунды. Лишний проход по данным — это удвоение.
• Память. Чтение из кэша процессора — доли наносекунды, из оперативной памяти — около сотни. Алгоритм, который скачет по большому массиву, бывает в десятки раз медленнее, чем обещает подсчёт шагов: в статье о хеш-таблице поиск в словаре на миллионе ключей дороже, чем на тысяче, хотя шагов столько же.
• Ввод и вывод. Прочитать миллион чисел — тоже работа, и в Python медленный способ чтения может съесть заметную часть лимита.
• Машину. Сервер проверки может быть медленнее вашего ноутбука. Сравните в сцене «Ваш браузер» с сервером — разница бывает в разы в обе стороны.

Если оценка показывает «впритык» — в пределах трёх-пяти раз от лимита, — нужен честный замер. Если запас в сто раз или нехватка в сто раз, замер не нужен: ответ уже ясен.

Задача

Настоящий каталог землетрясений и вопрос, на который легко ответить перебором всех пар. На этом каталоге перебор в Go даже проходит. Оцените, что будет при n = 2·10⁵, и найдите решение, которому всё равно.