ALGO·III Алгоритмы Глава 26 из 65
Подбросим монетку
Казино, где выигрывает заведение, то есть мы. За каждым столом случайность работает на программиста: пасьянс Улама, дротики, которые считают π, рулетка быстрой сортировки, кости, которые проверяют простоту, лотерейный барабан, фейсконтроль и счётчик у входа.
Алгоритмы
- 20 Поиск и сортировка
- 21 Разделяй и властвуй
- 22 Динамика
- 23 Жадные
- 24 Кратчайшие пути
- 25 Потоки и пары
- 26 Случайность вы здесь
- 27 Поиск в тексте
Опирается на: 21 · Разделяй и властвуй 16 · Хеш-таблица: атака и защита
Что вы унесёте из главы
- оценивать вероятности и площади методом Монте-Карло и знать, сколько опытов нужно для нужной точности
- отличать алгоритмы Лас-Вегаса от алгоритмов Монте-Карло и проверять простоту больших чисел тестом Миллера — Рабина
- выбирать случайный элемент из потока, проверять членство фильтром Блума и считать различные элементы в килобайте памяти
Прошлая глава кончилась странным советом. Чтобы найти самое слабое место сети, можно вместо потоков стягивать случайные линии, пока не останутся два города, и повторить это много раз. Звучит как отказ думать. Но монетка бывает лучшим инструментом программиста. Она даёт ответ там, где точный расчёт безнадёжен, защищает от входов, подобранных злоумышленником, а миллионы вещей с ней можно помнить в нескольких килобайтах. Глава устроена как казино. За каждым столом своя игра, и в каждой выигрывает заведение — то есть мы.
Стол первый: пасьянс
Так появился метод Монте-Карло: чтобы найти вероятность, сыграйте много раз и посчитайте долю удач. Мы уже встречали его в главе 12, где Кристен Нюгор разыгрывал судьбы нейтронов для первого норвежского реактора. А Улам появлялся в главе 22 с вопросом о возрастающих подпоследовательностях случайной перестановки — он вообще любил спрашивать, как ведёт себя случайное.
Canfield для начала сложноват: у него много правил и есть выбор ходов, так что вероятность зависит ещё и от игрока. Возьмём пасьянс «Часы», где выбора нет совсем. Колоду раскладывают в 13 стопок по 4 карты рубашкой вверх: двенадцать стопок по кругу, как часы, — для тузов, двоек и так до дам, — и тринадцатая в середине, для королей. Открываем верхнюю карту средней стопки и кладём её к стопке её ранга, например семёрку — на «семь часов». Оттуда берём верхнюю закрытую карту, кладём её к её стопке, и так далее. Пасьянс сходится, если открылись все 52 карты. Точно посчитать вероятность этого — задача для комбинаторики. Поступим, как Улам.
Игра кончается, когда мы приходим к пустой стопке, и пустой бывает лишь средняя. К любой другой стопке мы приходим только с картой её ранга, а таких карт четыре — столько же, сколько в стопке закрытых. Средней же стопке нужна лишняя карта: с неё мы начали, не придя ни с каким королём. Поэтому игра всегда обрывается на четвёртом короле, и вопрос лишь в том, остались ли к этому моменту закрытые карты.
Точный ответ здесь известен, $1/13$, и его можно доказать. Но машине хватило секунды, чтобы получить около 0,077, и ни одной формулы для этого не понадобилось. Для Canfield, где многое зависит ещё и от решений игрока, простой формулы не видно вовсе — остаётся раскладывать. Ниже — тот же опыт на нашем сервере, с картинкой. Второй пасьянс в виджете, «Досада», ещё проще: карты открывают по одной, приговаривая «туз, два, три, …, король, туз, …», и проигрывают, если карта совпала с названным рангом. Вероятность выигрыша в нём посчитали Питер Дойл, Чарльз Гринстед и Лори Снелл: примерно один раз из 61,6.
Сколько нужно раскладов
Каждый расклад — бросок нечестной монетки, которая выпадает «удачей» с вероятностью $p$. Доля удач после $n$ бросков в среднем равна $p$, а разброс — стандартное отклонение — равен $\sqrt{p(1-p)/n}$. По центральной предельной теореме с вероятностью около 95 % доля отклонится от $p$ не больше чем на два таких отклонения. Для «Часов» при тысяче раскладов это $2\sqrt{\frac{1}{13} \cdot \frac{12}{13} / 1000} \approx 0{,}017$: ответ «от 0,06 до 0,094» — грубовато. При ста тысячах — $\pm 0{,}0017$.
Ошибка метода Монте-Карло убывает как $1/\sqrt{n}$. Чтобы получить ещё один верный знак, опытов нужно в сто раз больше.
Это медленно. Но у закона $1/\sqrt{n}$ есть и сильная сторона: в нём нет ни сложности задачи, ни числа её измерений. Пасьянс из 52 карт или из тысячи, нейтрон в трёх измерениях или цена опциона, зависящая от ста акций, — ошибка убывает одинаково, как $1/\sqrt{n}$; от задачи зависит только множитель — разброс одного опыта. Проверим это на числе, которое знают все.
Стол второй: дротики
Повесим квадратную мишень со стороной 1 и впишем в неё четверть круга радиуса 1 с центром в углу. Площадь четверти круга — $\pi/4$, площадь квадрата — 1. Если бросать дротики наугад, так что каждая точка квадрата одинаково вероятна, в четверть круга попадёт доля бросков, близкая к $\pi/4$. Умножим долю на четыре — получим $\pi$. Точка $(x, y)$ лежит в четверти круга, если $x^2 + y^2 \le 1$.
Миллион дротиков — и всего два-три верных знака после запятой. Для числа $\pi$ это смешно: формулы дают триллионы знаков. В «Царице наук» есть история посмешнее — игла Бюффона и итальянец Лаццарини, который в 1901 году «случайными бросками» получил шесть верных знаков, подозрительно удачно выбрав, когда остановиться.
Для $\pi$ метод Монте-Карло не нужен, его сила — в задачах, где формул нет. Посчитать площадь фигуры можно и сеткой: проверить центры клеток, $\sqrt n$ на $\sqrt n$, и для гладкой фигуры на плоскости ошибка будет порядка $1/\sqrt n$, не хуже. Но в десяти измерениях сетка из миллиона точек — это меньше четырёх точек вдоль каждой оси: $4^{10} \approx 10^6$. Такая сетка не видит почти ничего. А у случайных точек ошибка по-прежнему $1/\sqrt n$. Поэтому Монте-Карло считает объёмы в многомерных пространствах, освещение в компьютерной графике (каждый луч света — случайная история, как нейтрон) и риски финансовых портфелей. В задаче «Площадь пятна» в конце главы вы посчитаете площадь фигуры, для которой формула неудобна.
Стол третий: рулетка
Пасьянс и дротики дают приблизительный ответ. Но монетка помогает и алгоритмам, которые должны отвечать точно. Тут есть два способа рисковать, и у них свои имена.
Алгоритм Лас-Вегаса всегда отвечает верно, а от монетки зависит только, сколько он проработает. Алгоритм Монте-Карло работает предсказуемое время, но может ошибиться — с маленькой вероятностью, которую мы контролируем. Название «Лас-Вегас» ввёл в 1979 году венгерский математик Ласло Бабаи, в пару к уже привычному «Монте-Карло»: одно казино против другого.
Случайная быстрая сортировка из главы 21 — алгоритм Лас-Вегаса. Список она сортирует всегда, а случайный выбор опорного влияет только на число сравнений. Там мы видели, что с первым элементом в роли опорного отсортированный список вызывает квадратичное время, и пообещали объяснить, откуда у случайной сортировки около $1{,}39\,n\log_2 n$ сравнений в среднем. Пора платить по счёту.
Быстрая сортировка $n$ различных чисел со случайным опорным элементом делает в среднем меньше $2n\ln n \approx 1{,}39\, n \log_2 n$ сравнений, каким бы ни был входной порядок.
Пусть $z_1 < z_2 < \ldots < z_n$ — числа списка по возрастанию. Каждое сравнение — это сравнение какого-то элемента с опорным, и два элемента сравниваются не больше одного раза: после разбиения опорный уходит на своё место и больше не участвует. Значит, общее число сравнений — сумма по всем парам $i < j$ величины «1, если $z_i$ и $z_j$ сравнили, и 0 иначе», а среднее значение суммы равно сумме средних — это линейность математического ожидания. Остаётся найти для каждой пары вероятность того, что её сравнят.
Посмотрим на отрезок значений $z_i, z_{i+1}, \ldots, z_j$ — в нём $j - i + 1$ чисел. Пока опорным выбирают числа вне отрезка, весь отрезок остаётся в одном подсписке: опорный меньше их всех или больше их всех. Рано или поздно опорным станет число из отрезка, и все числа отрезка в этот момент равновероятны. Если это $z_i$ или $z_j$, пару сравнят. Если любое число между ними, $z_i$ уйдёт налево, $z_j$ — направо, и встретиться им больше не придётся. Значит, пару сравнивают с вероятностью $\frac{2}{j - i + 1}$.
Пар с разностью $j - i = d$ ровно $n - d$, и среднее число сравнений равно
$$\sum_{d=1}^{n-1} (n - d)\,\frac{2}{d+1} < 2n \sum_{k=2}^{n} \frac{1}{k} < 2n \ln n.$$Последнее неравенство — потому что сумма $\frac12 + \frac13 + \ldots + \frac1n$ меньше площади под кривой $1/x$ от 1 до $n$, то есть $\ln n$. И $2 \ln n = 2 \ln 2 \cdot \log_2 n \approx 1{,}39 \log_2 n$.
В доказательстве нет ни слова о входе: среднее берётся по броскам монетки, а не по спискам. Злоумышленник, который знает наш код, не сможет подобрать плохой вход, — он не знает, какие опорные мы выберем. Это та же защита, что соль в хеш-таблице из главы 16. Проверим теорему подсчётом. Точное среднее известно: $2(n+1)H_n - 4n$, где $H_n = 1 + \frac12 + \ldots + \frac1n$.
Пять опытов из пяти ложатся в несколько процентов от ожидания. Отношение к $n \log_2 n$ пока меньше 1,39 — около 1,2 при ста тысячах, — потому что от $2n\ln n$ отнимается поправка примерно $2{,}8n$, и при скромных $n$ она заметна. Разброс при этом маленький, и можно доказать, что вероятность сделать хотя бы вдвое больше сравнений, чем в среднем, быстро стремится к нулю с ростом $n$.
А пример алгоритма Монте-Карло у нас уже был — в конце прошлой главы. Стягивание случайных рёбер находит минимальный разрез графа из $n$ вершин с вероятностью не меньше $\frac{2}{n(n-1)}$. Это немного, но если повторить опыт $n^2$ раз и взять лучший разрез, ошибка станет меньше $e^{-2}$, а при $n^2 \ln n$ повторах — меньше $1/n^2$. Повторение помогает с любым алгоритмом Монте-Карло: если каждый прогон ошибается с вероятностью $q$, независимо от других, то $k$ прогонов ошибутся все сразу с вероятностью $q^k$.
Алгоритм ошибается с вероятностью $1/3$ и только в одну сторону: если он ответил «нет», это точно «нет», а «да» бывает ложным. Сколько независимых прогонов нужно, чтобы вероятность ошибки стала меньше одной миллионной?
Ответ «да» верим, только если все $k$ прогонов сказали «да». Ошибутся все сразу с вероятностью $(1/3)^k$, а $3^{13} = 1\,594\,323$ — больше миллиона. Тринадцать прогонов — и ошибка меньше одной миллионной; ещё тринадцать — меньше одной триллионной.
Стол четвёртый: кости
За этим столом проверяют, простое ли число. Для небольших чисел хватает перебора делителей до $\sqrt n$, как в задаче из главы 5. Но ключ шифра RSA, о котором будет глава 60, строят из простых чисел в сотни знаков, а у трёхсотзначного числа до корня — $10^{150}$ кандидатов. Перебор отпадает.
Первую идею дала малая теорема Ферма из «Царицы наук»: если $n$ простое, то $a^{n-1} \equiv 1 \pmod n$ для любого $a$, не делящегося на $n$. Возведение в степень по модулю быстрое — функция pow(a, e, n) делает его за $O(\log e)$ умножений. Значит, выбираем случайное $a$ и смотрим: если $a^{n-1} \not\equiv 1$, число $n$ точно составное. Такое $a$ называют свидетелем составности. Беда в том, что существуют составные числа, у которых свидетелей Ферма почти нет: числа Кармайкла. Самое маленькое из них — $561 = 3 \cdot 11 \cdot 17$.
Тест Ферма с $a = 2$ видит единицу и готов признать 561 простым. Но в цепочке есть улика. Число $n - 1 = 560$ мы записали как $2^4 \cdot 35$ и возводили двойку сначала в нечётную степень 35, а потом четыре раза в квадрат; последнее число цепочки и есть $2^{560}$. Перед первой единицей стоит 67: $67^2 \equiv 1 \pmod{561}$, хотя $67 \not\equiv \pm 1$. По простому модулю так не бывает. Если $x^2 \equiv 1 \pmod p$, то $p$ делит $(x-1)(x+1)$, а простое число, делящее произведение, делит один из множителей — значит, $x \equiv 1$ или $x \equiv -1$. Найдя «лишний» корень из единицы, мы поймали 561 с поличным. Улика заодно выдаёт делители: $\text{НОД}(67 - 1, 561) = 33$ и $\text{НОД}(67 + 1, 561) = 17$.
На этом и построен тест Миллера — Рабина. Запишем $n - 1 = 2^s d$ с нечётным $d$ и посчитаем цепочку $a^d, a^{2d}, \ldots, a^{2^s d}$. Если $n$ простое, цепочка либо сразу начинается с 1, либо где-то встречает $-1$ (то есть $n - 1$), после чего идут одни единицы. Всё остальное — улика. В 1976 году Гэри Миллер предложил детерминированный тест, правильность которого доказана при условии недоказанной расширенной гипотезы Римана. В 1980 году Майкл Рабин сделал из него вероятностный тест без всяких гипотез. Он и независимо от него Луи Монье доказали то, на чём держится тест: у нечётного составного числа не больше четверти чисел $a$ от 1 до $n - 1$ «врут» — проходят проверку, не будучи свидетелями. Остальные три четверти — свидетели.
Это алгоритм Монте-Карло с односторонней ошибкой. Ответ «составное» всегда верен: свидетель — это доказательство. Ответ «простое» может быть ложным, но при двадцати случайных $a$ вероятность этого не больше $4^{-20} < 10^{-12}$. Число $2^{521} - 1$ проверено за миллисекунды. А в январе 1952 года Рафаэль Робинсон доказывал его простоту на машине SWAC другим тестом, Люка — Лемера, который годится только для чисел вида $2^p - 1$. Это было первое простое число Мерсенна, найденное компьютером.
Так ищут простые числа для ключей: берут случайное нечётное число нужной длины и проверяют, пока не попадётся простое. Простые числа встречаются достаточно часто — среди чисел около $N$ примерно каждое $\ln N$-е, — так что для трёхсотзначных хватает в среднем нескольких сотен попыток. В 2002 году Маниндра Агравал, Нирадж Каял и Нитин Саксена нашли детерминированный тест, который работает за полиномиальное время без всяких гипотез. Это был прорыв в теории, но на практике по-прежнему бросают кости: вероятностный тест намного быстрее.
Стол пятый: лотерейный барабан
Мимо стола едет лента с билетами, и нужно выбрать победителя так, чтобы у всех билетов были равные шансы. Сколько билетов будет, неизвестно, ленту нельзя отмотать назад, а в руках помещается один билет. Так выглядят и рабочие задачи: выбрать случайную строку из журнала сервера на сотню гигабайт, твит из потока, слово из романа, не загружая роман в память.
Решение помещается в три строки. Держим в руке билет. Когда подъезжает $i$-й билет, с вероятностью $1/i$ меняем свой на него. Первый билет мы берём наверняка, второй — с вероятностью ½, третий — ⅓ и так далее.
Если поток кончился после $n$ элементов, каждый из них оказывается выбранным с вероятностью $1/n$.
Элемент номер $i$ должен, во-первых, быть взят в руку — это вероятность $\frac1i$, — а во-вторых, не быть заменённым ни одним из следующих. Элемент $i+1$ его не заменит с вероятностью $1 - \frac{1}{i+1} = \frac{i}{i+1}$, элемент $i+2$ — с вероятностью $\frac{i+1}{i+2}$, и так до $\frac{n-1}{n}$. Все броски независимы, и произведение сокращается почти целиком: $\frac1i \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-1}{n} = \frac1n$.
Шесть букв в последней строке программы выбраны примерно по десять тысяч раз каждая, как и обещает теорема. Если нужно выбрать $k$ элементов, держат в руке $k$ билетов: первые $k$ берут все, а $i$-й билет с вероятностью $k/i$ заменяет случайный из тех, что в руке. Это выборка резервуаром. В книге Кнута она называется «алгоритм R», и Кнут приписывает её Алану Уотерману; в 1985 году Джеффри Виттер разобрал всё семейство таких алгоритмов и придумал, как пропускать сразу много элементов, не бросая монетку для каждого. Резервуар на $k$ мест вы соберёте в задаче «Резервуар».
Стол шестой: фейсконтроль
У входа в казино стоит охранник со списком из десяти миллионов нежелательных гостей. Помнить все лица он не может, и ему разрешили ошибаться, но только в одну сторону: иногда не пустить обычного гостя можно, пустить нежелательного — нельзя. Та же задача у браузера, который проверяет адрес по списку опасных сайтов, и у базы данных, которая перед дорогим чтением с диска хочет знать, есть ли там вообще такой ключ. Множество из главы 8 отвечает точно, но хранит сами элементы — десятки байт на каждый.
В 1970 году Бёртон Блум описал в журнале Communications of the ACM структуру, которая обходится примерно десятью битами на элемент. Его пример — перенос слов. Из полумиллиона английских слов девять десятых переносятся по простым правилам, а для остальных нужен словарь на медленном диске. Если в памяти держать компактный «список исключений», который иногда ошибается в сторону «да, это исключение», то лишнее обращение к диску случается редко, а пропусков не бывает вовсе.
Фильтр Блума — это массив из $m$ битов, вначале нулевых, и $k$ разных хеш-функций, каждая из которых отображает элемент в номер бита. Добавляя элемент, ставим в единицу все его $k$ битов. Проверяя, смотрим на те же $k$ битов: если хоть один ноль, элемента точно не было; если все единицы — «наверное, был». Единицы могли поставить другие элементы, и тогда фильтр ошибётся: это ложное срабатывание. Обратной ошибки не бывает: биты только ставятся, но никогда не стираются.
Сколько хеш-функций брать? Мало — каждое слово проверяется по одному-двум битам, и чужое слово легко проскакивает. Много — фильтр быстро заполняется единицами. Посчитаем. После $n$ добавлений конкретный бит остался нулём, если его не выбрала ни одна из $kn$ хеш-функций: вероятность $(1 - 1/m)^{kn} \approx e^{-kn/m}$. Чужое слово проходит, если все его $k$ битов — единицы:
$$p \approx \left(1 - e^{-kn/m}\right)^k.$$Минимум достигается при $k = \frac{m}{n}\ln 2$, когда единицы занимают половину битов, и тогда $p \approx 0{,}6185^{\,m/n}$. Для одного процента ошибок нужно около 9,6 бита на элемент, для одной тысячной — около 14,4, и это не зависит ни от числа элементов, ни от их длины. Проверим на «Войне и мире»: фильтр помнит слова первой половины романа, а мы спрашиваем у него слова, которые встречаются только во второй.
Опыт ложится на формулу, и минимум — при $k = 7$, как и обещано: $10 \ln 2 \approx 6{,}9$. Метод positions не вычисляет семь разных хешей: он берёт два числа из одного хеша SHA-256 и строит из них остальные как $h_1 + i\,h_2$. Адам Кирш и Майкл Митценмахер в 2006 году доказали, что такой приём почти не ухудшает фильтр. Специальный метод __contains__ — из тех, что с двумя подчёркиваниями, как в главе 12, — даёт писать w in bloom, как для обычного множества. А байт на бит мы тратим для простоты: в рабочем фильтре в каждый байт упаковано восемь битов, и как это делается, расскажет глава 28.
Фильтры Блума работают внутри баз данных Bigtable, Cassandra и HBase: прежде чем читать файл с диска, база спрашивает фильтр, может ли там быть ключ. Сеть доставки контента Akamai держала в фильтре адреса, которые уже запрашивали хотя бы раз, и сохраняла файл в кэш только при втором запросе: так в кэш не попадали страницы, которые смотрят единожды. Удалять из обычного фильтра нельзя — бит мог поставить и другой элемент; для этого придумали фильтры со счётчиками вместо битов.
Стол седьмой: счётчик у входа
Последний стол — у двери. Сколько разных людей зашло за день, если многие заходили по несколько раз? Для сайта это число уникальных посетителей, для поисковика — число разных запросов, для лингвиста — число разных слов в книге. Точный ответ требует помнить всех, кого видели, — множество размером с ответ. Можно ли обойтись килобайтом?
Снова хеш. Пропустим каждого посетителя через хорошую хеш-функцию: она превращает его в случайную на вид строку битов, причём один и тот же посетитель всегда даёт одну и ту же строку. Повторы, значит, ничего не меняют. Будем помнить только одно число — наибольшее количество нулей, с которых начиналась строка. Хеш, начинающийся с десяти нулей, попадается примерно у одного из $2^{10} = 1024$ разных посетителей. Если мы видели такой, разных было, скорее всего, порядка тысячи.
Одно такое число — очень грубая оценка: она прыгает в два раза от одного нуля. Поэтому посетителей раскладывают по $m$ ячейкам по первым битам хеша, в каждой ячейке помнят свой максимум, а потом аккуратно усредняют. Филипп Флажоле и Найджел Мартин предложили похожий «вероятностный подсчёт» в 1985 году, а в 2007 году Флажоле с соавторами — Эриком Фюзи, Оливье Гандуэ и Фредериком Мёнье — довёл его до алгоритма HyperLogLog с ошибкой около $1{,}04/\sqrt{m}$. Каждая ячейка хранит число до 64, это 6 битов. В базе Redis HyperLogLog держит 16 384 ячейки: 12 килобайт и ошибка около 0,8 %. Так же считают уникальных посетителей многие системы аналитики.
Тысяча ячеек — меньше килобайта — и число разных слов «Войны и мира» найдено с ошибкой в несколько процентов. Множество всех слов заняло бы мегабайты. Операции >> и & вырезают из числа нужные биты; подробно о них — в главе 28. Константа alpha и поправка для пустых ячеек взяты из статьи 2007 года. Усреднение максимумов немного завышает ответ, и константу подобрали так, чтобы это компенсировать.
Касса
Подсчитаем выигрыш. За каждым столом монетка давала что-то, чего не дал бы точный расчёт, и за каждый выигрыш мы платили понятную цену.
| Стол | Что дала монетка | Чем заплатили |
|---|---|---|
| Пасьянс, дротики | число, для которого нет формулы | ошибка порядка $1/\sqrt{n}$ |
| Рулетка | $n \log n$ на любом входе, даже подобранном врагом | время случайно, но долго — очень редко |
| Кости | простота стозначных чисел за миллисекунды | ошибка не больше $4^{-k}$ |
| Барабан | честная выборка из потока за один проход | одним броском на элемент |
| Фейсконтроль | десяток битов на элемент вместо десятков байт | редкие ложные «да» |
| Счётчик | килобайт вместо мегабайт | ошибка $1{,}04/\sqrt{m}$ |
Осталось признаться, что настоящей монетки у нас не было. Модуль random — это генератор псевдослучайных чисел: детерминированная программа, которая из начального числа, «зерна», выдаёт длинную последовательность, похожую на случайную. В Python это вихрь Мерсенна, который Макото Мацумото и Такудзи Нисимура опубликовали в 1998 году. Одно и то же зерно даёт одну и ту же последовательность, и для опытов это удобно: результат можно повторить.
Задачи
Четыре задачи — с четырёх столов из семи. В двух из них ответ случаен, и тесты проверяют его статистически: много запусков, и доли должны лечь туда, куда велит теория.
На плоскости лежат круги, каждый задан тройкой (x, y, r); они могут пересекаться и вкладываться друг в друга. Напишите union_area(circles, n=200_000) — оценку площади их объединения методом Монте-Карло по n случайным точкам. Ответ должен отличаться от точного не больше чем на 3 %, а на 200 000 точек уходить меньше четырёх секунд. Для пустого списка верните 0. Круги бывают где угодно, в том числе далеко от начала координат и с отрицательными координатами, а радиус бывает и нулевым.
Прямоугольник — от наименьшего $x - r$ до наибольшего $x + r$ и так же по $y$. Квадрат $[0, 1]^2$ из главы не годится: круги могут лежать где угодно.
Точку считаем один раз, даже если она попала в несколько кругов: проверяйте круги по очереди и выходите из цикла break на первом попадании.
Тесты сравнивают ответ с точной площадью, которую считают по-другому: для каждой вертикальной прямой находят длину её пересечения с кругами и складывают. Чем плотнее круги заполняют прямоугольник, тем точнее оценка: при доле попаданий $p$ относительная ошибка порядка $\sqrt{(1-p)/(pn)}$.
Напишите sample(stream, k) — список из $k$ элементов потока, выбранных равновероятно: каждый набор из $k$ элементов должен получаться с одинаковой вероятностью. Поток можно пройти только один раз, длина его неизвестна, и хранить весь поток нельзя — тесты следят за памятью. Если в потоке меньше $k$ элементов, верните их все.
Первые $k$ элементов просто кладите в список. Элемент с индексом $i \ge k$ (это $(i+1)$-й по счёту) должен попасть в выборку с вероятностью $k/(i+1)$.
Удобно бросить одно случайное число: j = random.randrange(i + 1). Если j < k — а это случается как раз с вероятностью $k/(i+1)$, — новый элемент занимает место номер j.
Почему наборы равновероятны, доказывается по индукции, как теорема в главе: пусть после $i$ элементов каждый $k$-набор из них равновероятен; новый элемент попадает с вероятностью $k/(i+1)$ и вытесняет случайного, и после подсчёта каждый $k$-набор из $i+1$ элементов снова получает одинаковую вероятность. Одно число j делает сразу два дела: решает, брать ли элемент, и выбирает, кого он заменит.
Напишите is_prime(n) для целых $n$ до $10^{24}$: True для простых и False для остальных, включая 0, 1 и отрицательные. Двадцать тысяч чисел до $10^{18}$ должны проверяться быстрее трёх секунд, так что перебор делителей не пройдёт. Среди тестов — числа Кармайкла и составные числа, которые обманывают тест Миллера — Рабина с несколькими фиксированными основаниями.
Возьмите функцию is_probable_prime из главы и разберитесь, почему она верна. Маленькие простые делители проверьте отдельно: тогда randrange(2, n - 1) не сломается на маленьких $n$.
Можно обойтись без случайности, если перебирать фиксированные основания, но их набор зависит от размера чисел. Первые двенадцать простых, от 2 до 37, гарантированно работают для $n < 3{,}18 \cdot 10^{23}$, а с основанием 41 — до $3{,}3 \cdot 10^{24}$. Одно из составных чисел в тестах проходит все основания до 37.
Это детерминированная версия: тринадцать оснований без пропусков проверены перебором на компьютерах для всех $n$ меньше $3{,}3 \cdot 10^{24}$, отсюда и граница в подсказке. Число $318\,665\,857\,834\,031\,151\,167\,461$ проходит все основания до 37 и ловится только на 41. Вариант со случайными основаниями, как в главе, тоже проходит тесты: шанс, что двадцать случайных $a$ окажутся лжецами, меньше $10^{-12}$.
Напишите класс BloomFilter(m, k) для строк: add(item) добавляет строку, а item in bf отвечает, могла ли она быть добавлена. Добавленные строки фильтр не забывает никогда. Ложные срабатывания должны быть такими, как велит формула: при $m = 200\,000$, $n = 20\,000$ и $k = 7$ — меньше 1,5 %. И фильтр не должен хранить сами строки — тесты посмотрят, сколько он занимает.
Нужна функция, которая выдаёт $k$ номеров битов для строки. Хеш hashlib.sha256(item.encode()).digest() — это 32 байта; из первых восьми и следующих восьми получите два числа $h_1$ и $h_2$.
Номера битов — $(h_1 + i\,h_2) \bmod m$ для $i = 0, \ldots, k-1$; сделайте $h_2$ нечётным. Не берите $k$ соседних битов $h, h+1, \ldots$: соседние биты заполняются вместе, и ложных срабатываний станет заметно больше.
Встроенный hash(item) тоже подойдёт как источник $h_1$, но помните: для строк он меняется от запуска к запуску (это соль из главы 16), так что сохранённый на диск фильтр после перезапуска перестанет узнавать свои слова. SHA-256 одинаков всегда.
Куда дальше
Майкл Рабин, чьё имя стоит в тесте на простоту, через семь лет вместе с Ричардом Карпом применил случайность ещё к одной задаче — поиску образца в тексте. Задача звучит скромно, пока не посмотришь на масштаб. Геном человека — около трёх миллиардов букв из алфавита A, C, G, T, и биологу нужно найти в нём короткий мотив, а потом ещё тысячи других. Перебор «приложить образец к каждой позиции» делает миллиарды сравнений на каждый образец. Справиться быстрее помогут автомат, который никогда не возвращается назад, скользящий хеш и дерево из букв. Об этом — следующая глава.