DATA·II Структуры данных Глава 13 из 65
Сколько стоит программа
Хакерский триллер с секундомером: повторяем шаги игрока, который в 2021 году выяснил, почему GTA Online грузится шесть минут, — и учимся считать время работы программы до запуска.
Структуры данных
- 13 Сложность вы здесь
- 14 Массивы
- 15 Стек и очередь
- 16 Хеш-таблицы
- 17 Деревья
- 18 Кучи
- 19 Графы
Опирается на: 04 · Снова и снова 06 · Списки 09 · Задача внутри задачи
Что вы унесёте из главы
- замерять время программы и по двум-трём замерам понимать, как оно растёт
- оценивать сложность кода по его тексту: O, Ω, Θ и классы от 1 до 2ⁿ
- находить квадратичные места — проверку in по списку, срез в цикле — и чинить их
2Почему одна программа решает задачу за секунду, а другая не справится и до конца Вселенной?
В конце прошлой главы остров, населённый вдвое гуще, жил вчетверо медленнее: шестнадцать тысяч кроликов — секунда на день, сто тысяч — полминуты. Мы спросили, почему так и нельзя ли было знать это заранее. В главе 0 тот же вопрос, только крупнее, стоял вторым из больших вопросов курса: почему одна программа решает задачу за секунду, а другая не справится и до конца Вселенной? Начнём с человека, которому однажды надоело ждать.
Шесть минут
Первое правило расследования — мерить, прежде чем гадать. «Игра сложная» и «виновата сеть» — догадки. Четыре минуты на одном ядре при молчащих диске и сети — улика: процессор что-то считает, долго и в одиночку. Железо тут ни при чём; всё решает, как считает программа. Поэтому и мы, прежде чем что-то объяснять, научимся засекать время.
Секундомер
Секундомер в Python — функция time.perf_counter(): она возвращает время в секундах от какого-то момента, и разность двух вызовов показывает, сколько прошло. Но одно число говорит мало: 0,4 секунды — это быстро или медленно? Куда интереснее, как время меняется, когда растёт вход. Поэтому мерят на нескольких размерах, каждый раз удваивая. Вот функция, которая ищет в списке повторы самым прямым способом — сравнивает каждый элемент с каждым, как в главе о циклах в цикле.
Каждое удвоение — вчетверо дольше. Этот приём стоит запомнить: смотрите на отношение времён. Если при удвоении входа время выросло вдвое, работа растёт пропорционально $n$; вчетверо — как $n^2$; ввосьмеро — как $n^3$. Секунды зависят от компьютера, отношения — от алгоритма.
Для быстрых операций, которые занимают микросекунды, один замер тонет в шуме: на время влияет всё, что машина делает параллельно. Тогда операцию повторяют много раз и делят общее время на число повторов. Это делает модуль timeit.
Сумма и поиск в списке растут вдесятеро на каждый десятикратный рост $n$: чтобы сложить все числа или убедиться, что $-1$ среди них нет, надо посмотреть на каждое. А поиск во множестве не растёт совсем: на миллионе элементов он такой же, как на десяти тысячах, — несколько сотых долей микросекунды. В главе 8 мы видели эту разницу на «Войне и мире»; теперь видно, как она растёт.
Следующий секундомер делает такие замеры за вас. Впишите тело функции f(data): сервер вызовет её на списках случайных чисел длиной тысяча, две тысячи, четыре и так далее, пока один вызов не займёт около секунды, и нарисует график. Шкалы на нём логарифмические: на такой шкале $n^k$ превращается в прямую с наклоном $k$, и наклон виден на глаз.
Где горит
Мерить всю программу мало: в игре миллионы строк, и нужно найти те, что жгут время. Для этого есть профилировщик. У t0st не было исходного кода игры, и он взял профилировщик попроще, выборочный. Через равные промежутки времени тот заглядывает в работающую программу, смотрит, какая функция сейчас выполняется и кто её вызвал, и ведёт счёт. Какую функцию за четыре минуты чаще всех застали за работой, та и тормозит игру. Для Windows t0st знал единственный такой профилировщик, Luke Stackwalker, и тот не обновлялся больше десяти лет. Но своё дело он сделал: горячих мест нашлось два.
В Python профилировщик встроен: модуль cProfile считает, сколько раз вызвана каждая функция и сколько времени в ней прошло. Проверим наш остров из прошлой главы — один день на восьми тысячах кроликов и восьмистах лисах.
Колонка ncalls — сколько раз функцию вызвали, tottime — сколько секунд прошло в ней самой, cumtime — вместе со всем, что она вызывала. Виновник очевиден: rabbit_at. Её вызвали всего 800 раз — по разу на лису, — а времени она съела почти весь день. И isinstance вызван шесть с лишним миллионов раз. Откуда столько?
Вспомните, как лиса ищет кролика в своей клетке: rabbit_at идёт по всему списку зверей, пока не найдёт. В клетке кролика обычно нет, и лиса проверяет все 8800 зверей. Восемьсот лис — около семи миллионов проверок. Удвоим население: лис вдвое больше, и каждая проверяет вдвое более длинный список. Проверок вчетверо больше — отсюда и «вдвое больше зверей, вчетверо дольше день». Если лис — десятая часть зверей, то при $N$ зверях проверок примерно $\frac{N}{10} \cdot N = \frac{N^2}{10}$: квадрат.
Ни одна строчка острова не ошибочна. Ошибка в цене: проход по списку обходится недорого, но его повторяют для каждой лисы. Линейная работа, повторённая линейное число раз, даёт квадрат. Запомните это правило: в GTA оно сработает дважды.
Улика первая: strlen
Профилировщик дал t0st адреса в машинном коде, но без имён: игра защищена от взлома, и её код зашифрован. t0st снял копию памяти игры прямо во время загрузки — пока код работает, он расшифрован — и разобрал её дизассемблером. У одного из горячих адресов нашлось имя: strlen, стандартная функция языка C, которая считает длину строки. Её вызывала функция разбора текста — по всем признакам sscanf. А разбирала она JSON: десять мегабайт текста с каталогом магазина — около 63 тысяч предметов, которые можно купить в игре. Один предмет выглядел так:
Что дорогого в подсчёте длины строки? В языке C строка — это ряд байтов в памяти, конец которого отмечен нулевым байтом. Своей длины строка не помнит. Чтобы её узнать, strlen идёт от начала и считает байты, пока не встретит ноль, — для десятимегабайтной строки это десять миллионов шагов. А sscanf, которую просят прочитать одно число с текущего места, во многих реализациях вызывает strlen — от этого места до самого конца каталога. Прочитали число из пяти цифр — и пробежали мегабайты. Следующее число — снова мегабайты, чуть меньше.
strlen до конца строки перед каждым чтением. Переключите на «длина известна» — так работает заплатка t0st.Если в строке длиной $L$ разбирают $K$ значений, разбросанных по ней равномерно, то strlen в сумме пробежит около $K \cdot \frac{L}{2}$ байт — площадь того рыжего треугольника. Каталог вдвое больше — вдвое больше значений, и каждое вдвое дороже: вчетверо дольше. Опять линейная работа, повторённая линейное число раз. «Честно говоря, — признавался t0st, — я и не знал, что большинство реализаций sscanf вызывают strlen, так что не могу винить разработчика».
Строки Python свою длину помнят: len(s) берёт готовое число. Но ту же ловушку легко устроить и здесь. Вот разбор каталога, который после каждого прочитанного числа отрезает прочитанное: text = text[j:]. Срез — это новая строка, копия всего хвоста, то есть та же пробежка до конца, что у strlen. Рядом — тот же разбор, который помнит номер текущей позиции.
Ответы одинаковые, а время растёт по-разному: у второго разбора — вдвое на каждое удвоение, у первого — всё ближе к вчетверо. На маленьком каталоге разница — сотые доли секунды: копировать в памяти мегабайт машина умеет очень быстро. Квадрат просыпается на больших данных — а каталог GTA весил десять мегабайт.
Улика вторая: проверка на повторы
Второе горячее место нашлось рядом с первым. Каждый разобранный предмет игра кладёт в массив — пары «хеш предмета и указатель на сам предмет». Хеш — число, которое служит предмету номером. Но перед тем как положить предмет, игра проверяет, нет ли его уже в массиве. Проверяет так: идёт по массиву с начала и сравнивает хеш с каждым элементом.
Первому предмету сравнивать не с чем, второму — с одним, тысячному — с девятьюстами девяноста девятью. Всего для $n$ предметов
$$0 + 1 + 2 + \ldots + (n - 1) = \frac{n(n-1)}{2}$$сравнений. Эту сумму, по легенде, в уме посчитал маленький Гаусс. t0st считал чуть щедрее, $\frac{n^2+n}{2}$, и для 63 тысяч предметов у него вышло 1 984 531 500 проверок — почти два миллиарда, «если я правильно посчитал». Разница двух формул — 63 тысячи сравнений на два миллиарда — роли не играет.
И самое обидное. Массив перед загрузкой пуст, а все предметы в каталоге разные. Проверка ни разу не могла найти повтор, и у игры даже была функция, которая кладёт предмет без проверки. «Хеши уникальные — почему не взять хеш-таблицу?» — спрашивал t0st. Повторим опыт на Python: каталог с проверкой по списку и с проверкой по множеству.
Удвоение — вчетверо, и последняя строка предсказывает 63 тысячи, не дожидаясь их: время на 16 тысячах, умноженное на квадрат отношения размеров. Секунд пятнадцать-двадцать на Python, а у t0st, по его замерам, эта проверка отнимала у игры полторы минуты. Множество справляется со всем за миллисекунды, потому что in для него не перебирает элементы. Как ему это удаётся, расскажут следующие главы.
Заплатка
Исходного кода у t0st не было, поэтому чинить он стал снаружи. Он написал маленькую библиотеку, которую можно внедрить в работающую игру, и подменил в ней две функции. Новая strlen, встретив очень длинную строку, запоминает её начало и длину и, когда её потом спрашивают о месте внутри этой строки, отвечает вычитанием, никуда не бегая. Новая вставка в каталог кладёт предмет сразу, без проверки. Потом засёк время:
| Что исправлено | Загрузка сетевой игры |
|---|---|
| ничего | около 6 мин |
| только проверка на повторы | 4 мин 30 с |
только strlen | 2 мин 50 с |
| обе ошибки | 1 мин 50 с |
Загрузка короче на $\frac{360 - 110}{360} \approx 69{,}4\,\%$. 28 февраля 2021 года t0st опубликовал расследование под заголовком «Как я сократил загрузку GTA Online на 70 %». Пост вышел на первое место на Hacker News и разошёлся по миру. 15 марта t0st сообщил, что Rockstar пообещала скорое исправление и выплатила ему 10 000 долларов через свою программу вознаграждений за найденные ошибки — в виде исключения: обычно там платят за уязвимости. На следующий день вышло обновление игры, и t0st, проверив его на том же компьютере, написал: «Исправлено полностью».
Как и на острове, ни одна строчка не была ошибочной: каждая делала, что должна, только стоила дороже, чем казалось. На тестовом каталоге в сто предметов квадрат стоит миллисекунды, и его никто не замечает. Вырастет каталог в сто раз — квадрат вырастет в десять тысяч. Чтобы замечать такое до того, как это заметят игроки, нужно научиться оценивать цену программы по её тексту, без секундомера.
Как растут функции
Обе улики, как и остров, сводятся к одному: как число шагов растёт с размером входа $n$. Это называют сложностью алгоритма. Несколько видов роста встречаются так часто, что у них есть имена:
- постоянное время, $1$: число шагов не зависит от $n$ — взять элемент списка по индексу, проверить
inво множестве; - логарифмическое, $\log n$: удвоили вход — добавился один шаг; так работает двоичный поиск из главы 0: миллион вариантов за двадцать вопросов;
- линейное, $n$: посмотреть на каждый элемент по разу — сумма, максимум,
inпо списку; - $n \log n$: хорошие сортировки, например слиянием из гонки главы 0;
- квадратичное, $n^2$: каждый с каждым — пузырёк, проверка на повторы перебором, лисы на острове;
- экспоненциальное, $2^n$: каждый новый элемент удваивает работу — перебор всех подмножеств, наивный рекурсивный
fib.
Логарифм здесь и дальше — по основанию 2, хотя в оценках основание роли не играет (почему — чуть ниже). В числах эти функции выглядят так:
| $n$ | $\log_2 n$ | $n \log_2 n$ | $n^2$ | $2^n$ |
|---|---|---|---|---|
| 10 | 3,3 | 33 | 100 | 1024 |
| 100 | 6,6 | 664 | 10 000 | $1{,}3 \cdot 10^{30}$ |
| 1000 | 10 | 9966 | $10^6$ | $1{,}1 \cdot 10^{301}$ |
| $10^6$ | 20 | $2 \cdot 10^7$ | $10^{12}$ | $\approx 10^{301\,030}$ |
Обычный процессор делает порядка миллиарда простых действий в секунду. Значит, $n^2$ на миллионе — это $10^{12}$ действий, около четверти часа, а $n \log n$ — двадцать миллисекунд. А $2^n$ уже при $n = 100$ — это $10^{30}$ действий: $4 \cdot 10^{13}$ лет, три тысячи возрастов Вселенной. Другие сочетания прикиньте сами.
Переключите скорость машины на суперкомпьютер. Самые быстрые суперкомпьютеры середины 2020-х выполняют порядка $10^{18}$ операций в секунду — в миллиард раз больше ноутбука. Для $n^2$ это значит, что за то же время можно взять вход в $\sqrt{10^9} \approx 31\,600$ раз больше. Для $2^n$ — что $n$ можно увеличить на 30: $2^{30} \approx 10^9$. Ускорение в миллиард раз отодвигает экспоненциальную стену всего на тридцать шагов.
О большое
Подсчёт шагов редко даёт аккуратную формулу. Проверка на повторы делает $\frac{n(n-1)}{2}$ сравнений, плюс по одному присваиванию на каждый виток внешнего цикла, плюс подготовка — что-нибудь вроде $0{,}5\,n^2 + 2n + 7$. Но при больших $n$ слагаемое $0{,}5\,n^2$ забивает всё остальное: на миллионе оно в двести пятьдесят тысяч раз больше, чем $2n$. А множитель $0{,}5$ зависит от того, что считать одним шагом, от языка и от процессора. Поэтому договорились отбрасывать и младшие слагаемые, и постоянные множители и говорить: проверка на повторы работает за $O(n^2)$, «о большое от эн квадрат».
Пусть $f$ и $g$ — функции натурального аргумента с положительными значениями. Говорят, что $f(n) = O(g(n))$, если существуют числа $c > 0$ и $n_0$, такие что $f(n) \le c \cdot g(n)$ для всех $n \ge n_0$. Говорят, что $f(n) = \Omega(g(n))$, если существуют $c > 0$ и $n_0$, такие что $f(n) \ge c \cdot g(n)$ для всех $n \ge n_0$. И $f(n) = \Theta(g(n))$, если верно и то и другое.
По-человечески: $O$ — «растёт не быстрее, чем», с точностью до постоянного множителя и начиная с какого-то места; $\Omega$ — «растёт не медленнее, чем»; $\Theta$ — «растёт так же, как». Число $n_0$ разрешает функции вести себя как угодно на маленьких $n$: нас интересует, что будет, когда данных много.
$3n^2 + 10n + 100 = \Theta(n^2)$.
Сверху: $3n^2 + 10n + 100 \le 4n^2$ равносильно $n^2 - 10n - 100 \ge 0$, а это верно при $n \ge 5 + \sqrt{125} \approx 16{,}2$. Значит, подходят $c = 4$ и $n_0 = 17$, и $f = O(n^2)$. Снизу: $3n^2 + 10n + 100 \ge 3n^2$ при всех $n$, то есть $c = 3$, $n_0 = 1$, и $f = \Omega(n^2)$. Вместе — $\Theta(n^2)$.
Подберите $c$ и $n_0$ сами. А потом возьмите $g$, которая растёт медленнее $f$: никакое $c$ уже не спасёт, нарушение рано или поздно найдётся.
Из определения сразу видно, почему основание логарифма не имеет значения. $\log_{10} n = \frac{\log_2 n}{\log_2 10} \approx 0{,}3 \log_2 n$: логарифмы с разными основаниями отличаются постоянным множителем, а постоянные множители $O$ не замечает. Как устроены логарифмы, подробно рассказано в «Царице наук», а почему любая показательная функция обгоняет любую степенную, пусть и не сразу, — там же, в «главном заезде».
Ещё одна тонкость. $O$ — оценка сверху, и формально верно, что сумма списка работает за $O(n^2)$: она ведь не медленнее квадрата. Но так никто не говорит: сказать «$O(n^2)$» про линейный алгоритм — всё равно что на вопрос «сколько ехать» ответить «меньше года». Обычно, говоря «$O(\ldots)$», имеют в виду самую точную оценку, то есть, строго говоря, $\Theta$.
Угадай сложность
Оценивать сложность по тексту программы помогают несколько правил. Блоки, идущие друг за другом, складываются, и побеждает самый тяжёлый: $O(n) + O(n^2) = O(n^2)$. Вложенные циклы перемножаются: внешний на $n$ шагов, внутренний на $n$ — это $n^2$. Цикл, который каждый раз делит $n$ пополам, делает $\log n$ шагов. И правило, которое нарушили в GTA: у каждой строки есть цена, даже если она выглядит как одна операция. x in список, s[i:], sorted(a), список.insert(0, x), sum(a) — каждая проходит по данным. Положите такую строку в цикл — и получите квадрат.
Экспонента
В главе 9 мы видели, что рекурсивный fib(n) с каждыми пятью единицами $n$ работает дольше в одиннадцать раз. Теперь можно посчитать точно.
Пусть $T(n)$ — сколько раз вызывается функция при вычислении fib(n) рекурсией из главы 9, а $F_k$ — числа Фибоначчи ($F_0 = 0$, $F_1 = 1$, $F_2 = 1$, …). Тогда $T(n) = 2F_{n+1} - 1$, и $2^{\lfloor n/2 \rfloor} \le T(n) < 2^{n+1}$.
Вызов fib(0) и fib(1) — один вызов, а fib(n) при $n \ge 2$ — это он сам плюс вызовы для $n-1$ и $n-2$: $T(0) = T(1) = 1$, $T(n) = T(n-1) + T(n-2) + 1$. Формула верна при $n = 0$ и $n = 1$: $2F_1 - 1 = 2F_2 - 1 = 1$. Если она верна для $n-1$ и $n-2$, то $T(n) = (2F_n - 1) + (2F_{n-1} - 1) + 1 = 2F_{n+1} - 1$ — это индукция из главы 9. Оценки: $T(n-1) \ge T(n-2)$, поэтому $T(n) \ge 2T(n-2)$, и за каждые два шага вниз число вызовов хотя бы удваивается: $T(n) \ge 2^{\lfloor n/2 \rfloor}$, ведь $T(0) = T(1) = 1$. С другой стороны, $T(n) \le 2T(n-1) + 1$, откуда по индукции $T(n) \le 2^{n+1} - 1$.
Значит, $T(n)$ растёт экспоненциально: где-то между $1{,}41^n$ и $2^n$. Точнее, как $1{,}618^n$ — золотое сечение, о котором говорила глава 9. Измерим цену одного вызова и предскажем остальное.
Сорок — десяток секунд, пятьдесят — около получаса, шестьдесят — пара суток, восемьдесят — человеческая жизнь, сто — больше миллиона лет. А fib(120) рекурсией считался бы дольше, чем существует Вселенная. И всё это ради чисел, которые цикл из главы 9 находит за микросекунды. Экспонента сидит не в задаче, а в алгоритме: он решает одни и те же подзадачи миллиарды раз. Как это исправить одной строкой, расскажет глава 22.
Худший, средний и лучший
Сколько сравнений делает x in список? Зависит от того, где x. Если он первый — одно. Если его нет — $n$. Если он стоит в случайном месте — в среднем около $\frac{n}{2}$. У одного алгоритма бывает несколько оценок, и их нужно различать.
Худший случай — наибольшее время среди всех входов размера $n$. Это гарантия: медленнее не будет никогда. Средний случай — время, усреднённое по входам, и тут всегда нужна оговорка, по каким: «если все порядки элементов равновероятны». Лучший случай почти ничего не говорит: любой алгоритм можно научить мгновенно отвечать на один удобный вход.
Когда говорят «алгоритм работает за $O(n^2)$», обычно имеют в виду худший случай. Но иногда средний говорит больше. Быстрая сортировка из главы 21 в худшем случае квадратична, а в среднем делает около $1{,}39\, n \log_2 n$ сравнений — и на практике обгоняет многих соперников с гарантией $n \log n$. А противник, который знает ваш алгоритм, может нарочно подсунуть худший вход: в главе 16 так будут атаковать хеш-таблицы. «Худший случай» и «$O$» легко спутать, но это разные вещи. Первое говорит, какой вход мы рассматриваем, второе — как грубо описываем время. У одного алгоритма бывает $\Theta(n)$ в лучшем случае и $\Theta(n^2)$ в худшем — например, у сортировки вставками, которую вы встретите в главе 20.
Ответ на второй вопрос
В главе 0 пузырёк и слияние соревновались на пяти тысячах чисел, и мы обещали, что научимся считать такие гонки заранее. Пузырёк делает $\frac{n(n-1)}{2}$ сравнений, слияние — не больше $n \log_2 n$. Измерим цену одного «шага» каждой сортировки на небольшом входе — и предскажем время на большом, ещё не запуская.
На пяти тысячах прогноз и замер почти совпадают, на миллионе расходятся не больше чем на четверть: слияние занимает около полутора секунд, как и предсказано по двадцати тысячам. Пузырьку на том же миллионе, по прогнозу, понадобилось бы около пяти с половиной часов. Проверять не будем: прогноз для того и нужен, чтобы знать время программы, не запуская её.
Время работы программы определяется не столько скоростью машины, сколько тем, как число шагов её алгоритма растёт с размером входа. Быстрый процессор умножает скорость на постоянное число. Другой алгоритм меняет саму функцию роста: $n^2$ против $n \log n$ на миллионе чисел — часы против секунды, и разрыв растёт вместе с данными. Экспонента $2^n$ упирается в стену при любом железе: каждое лишнее $n$ удваивает работу, и при $n = 100$ даже машина в $10^{18}$ операций в секунду считала бы сорок тысяч лет. Оценивать алгоритм заранее можно по его тексту: подсчитать шаги как функцию от $n$, отбросить постоянные множители и младшие слагаемые — останется класс роста, $O(\ldots)$, — и по одному замеру на малом входе предсказать время на любом. Дальше ответ пойдёт вглубь. В главе 21 мы научимся получать $n \log n$ там, где наивный способ квадратичен, — разрезанием задачи пополам. А в главе 57 встретим задачи, для которых никто в мире не знает алгоритма быстрее экспоненты, и никто не может доказать, что его нет.
Задачи
Четыре задачи, и в трёх из них главный тест — с секундомером: решение «каждый с каждым» на больших входах не уложится в лимит времени. Первая — без секундомера, но с подвохом: считать нужно на бумаге.
В каждом фрагменте отмечена строка work(). Напишите четыре функции, которые для данного $n \ge 1$ возвращают, сколько раз эта строка выполнится:
Тесты спрашивают и $n = 10^{12}$: прогнать фрагмент и посчитать не выйдет, нужна формула.
Первые два — квадрат и сумма Гаусса: $0 + 1 + \ldots + (n-1)$.
В count_c число делят пополам, пока оно больше единицы. Сколько раз можно поделить $n$ пополам? Подсказка — число его двоичных цифр: метод n.bit_length() из прошлой главы.
В count_d внутренний цикл удваивает k от 1, пока k < n, — это наименьшее $m$, при котором $2^m \ge n$. Для $n = 1$ это 0, для $n = 5$ — 3. Удобно: (n - 1).bit_length().
Ответы: $n^2$, $\frac{n(n-1)}{2}$, $\lfloor \log_2 n \rfloor$ и $n \lceil \log_2 n \rceil$ — то есть $\Theta(n^2)$, $\Theta(n^2)$, $\Theta(\log n)$ и $\Theta(n \log n)$. На count_b легко ошибиться: внутренний цикл короче внешнего, но в среднем проходит половину длины, а вдвое меньший квадрат — всё равно квадрат.
Напишите dedupe(items): новый список из элементов items без повторов, в порядке первого появления. Например, dedupe([3, 1, 3, 2, 1]) — это [3, 1, 2]. Элементы — числа или строки. Исходный список менять нельзя. На миллионе элементов функция должна укладываться в секунду-другую, так что проверка if x not in result не пройдёт.
Заготовка правильная, но квадратичная: это та же проверка, что в GTA. Где хранить то, что уже видели, чтобы in был мгновенным?
Заведите рядом со списком result множество seen. Проверяйте x in seen, а добавляйте в оба.
Время — $O(n)$: каждый элемент один раз проверяется во множестве и, может быть, один раз добавляется. Есть и однострочник: list(dict.fromkeys(items)) — ключи словаря уникальны и, начиная с Python 3.7, хранятся в порядке добавления. А list(set(items)) не годится: множество порядок не хранит.
Напишите has_pair(nums, target): есть ли в списке два элемента на разных местах, сумма которых равна target. Например, в [3, 9, 4, 7] есть пара на сумму 13 (9 + 4), а на сумму 6 — нет: тройка в списке одна, и брать её дважды нельзя. Числа бывают отрицательными и повторяются. Списки в тестах — до двухсот тысяч чисел, на ответ даётся секунда; перебор всех пар — это двадцать миллиардов сравнений.
Идите по списку слева направо. Для очередного числа x ему нужен напарник target - x. Был ли такой левее?
Храните всё, что уже прошли, во множестве. Проверяйте напарника до того, как добавить x, — тогда число не станет парой самому себе.
Один проход и мгновенные проверки во множестве: $O(n)$ вместо $O(n^2)$. Порядок «сначала проверить, потом добавить» решает случай с одним числом: в [3] на сумму 6 пары нет, а в [3, 3] — есть. Есть и другой путь: отсортировать список и идти двумя указателями с концов навстречу, $O(n \log n)$ — он пригодится, когда памяти под множество нет.
Функция total_price(catalog) получает каталог — строку из предметов вида {"key": "WP_TINT_7", "price": 45000, "bitShift": 7}, разделённых запятыми, — и возвращает сумму всех цен. Заготовка работает правильно, но тесты дают ей каталог из 63 000 предметов, как в GTA, и секунду на ответ. В секунду она не укладывается. Найдите квадрат и почините его, не меняя ответа.
Каждое rest = rest[…:] — копия всего хвоста каталога, как пробег strlen. Сколько таких копий на 63 000 предметов?
Не режьте строку — помните позицию. У метода find есть второй аргумент, откуда начинать поиск: catalog.find('"price":', pos).
Это та же заплатка, что у t0st: помнить, где мы, вместо того чтобы каждый раз заново мерить хвост. Каждый символ каталога теперь просматривается один раз, и время линейно. В рабочей программе, впрочем, и так не пишут: JSON разбирает модуль json, одним вызовом json.loads("[" + catalog + "]"). Тот же совет t0st дал разработчикам: заменить библиотеку разбора JSON на более быструю.
Куда дальше
Всю главу мы опирались на одно чудо: x in множество не перебирает элементы и не дорожает с ростом $n$, а x in список идёт по всем подряд. Откуда такая разница? И почему список.append(x) мгновенный, а список.insert(0, x) на миллионе элементов ощутимо медленнее? Ответ спрятан в том, как список и множество лежат в памяти машины, а туда мы ни разу не заглядывали: список был для нас «значениями по порядку». В следующей главе мы поставим опыт, как естествоиспытатели, и по одним замерам, ещё не зная устройства, выведем, как Python хранит список.