Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Попробуйте сами ответить на этот вопрос. Каковы ваши действия? Поначалу все просто: 15 – это раз, 48 – два, 32 – три, 31 – четыре. Дальше снова 48, но эта та же карточка, поэтому мы ее не считаем. 27 – пять. В первом ряду всего 8 разных номеров. А вот во втором ряду уже начинаются затруднения. Попадался нам номер 02 до этого или нет? А 29? Или 45? Наша память не в состоянии это удержать! В результате до конца третьего ряда можно добраться только одним способом – сравнивать каждый номер со всеми предыдущими и ставить пометку, если он раньше не встречался. Ответ: 22 карты. Ниже мы выделили разные номера жирным шрифтом.

Теперь представьте, что эту задачу выполняет компьютер. Каким образом можно сравнить номер каждой карты со всеми предыдущими? Особенно если трансакций не тридцать, а три миллиона? И вот тут возникает проблема с памятью. Считывать все номера заново с жесткого диска – непозволительно долго. А оперативная память переполнится гораздо раньше, чем мы дойдем до середины.

Что же получается? При наличии полных данных и самых мощных компьютеров мы не в состоянии подсчитать, сколько человек воспользовалось кредитными картами?! В принципе да, не в состоянии. И конечно, кредитные карты – это всего лишь пример. На самом деле мы вообще не в состоянии ничего посчитать!

У вас на сайте есть счетчик уникальных посещений? Скорее всего, он считает приблизительно.

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

Общее количество заходов на сайт, кстати, можно сосчитать и точно, потому что в этом случае не нужно запоминать каждое посещение, достаточно помнить, сколько их было. Число друзей на «Фейсбуке» тоже подсчитывается точно, потому что они не повторяются. Приблизительное решение понадобится для подсчета количества разных объектов, когда один и тот же объект может появиться несколько раз.

Оговоримся, что в примере с кредитными картами проблему можно решить и по-другому, с абсолютной точностью. Например, если выстроить все номера в порядке возрастания, то сосчитать разные номера будет гораздо проще. Очевидный недостаток состоит в том, что обычно к нам поступают неупорядоченные данные и их сортировка представляет собой отдельную, непростую задачу, которой посвящена масса математической литературы.

Еще можно заранее создать такую структуру данных, где на каждого клиента было бы заведено электронное досье. Тогда совсем нетрудно пройтись по всем досье и посчитать, сколько из них содержит трансакции по кредитным картам. К каждому досье понадобится обратиться всего раз, и это много времени не займет. Но данный способ тоже работает не всегда. Например, как посчитать количество магазинов, в которых клиенты воспользовались кредитной картой? Наверняка у банка нет досье на каждый магазин.

Проблема подсчета очень актуальна, особенно в контексте больших данных. Сколько посетителей заходит на наш сайт из разных регионов России? Сколько школьников в этом году подали заявления в вузы? Сколько людей обсуждают в социальных сетях нашу партию? Сотрудники Google в своей статье{20} пишут, что в их систему хранения и обработки данных поступает свыше пяти миллионов подобных запросов в день! Регулярно встречаются запросы, предполагающие подсчет более миллиарда объектов. В этой статье также приводится цифра: в среднем около ста таких запросов в день. Из-за ограничений памяти получить точный ответ на подобный запрос абсолютно нереально.

Как найти хорошее приближение, практически ничего не запоминая? У задачи подсчета есть несколько решений. Сходу такое решение нельзя придумать, но понять основные идеи не так уж сложно.

Как решается задача подсчета

Мы воспользуемся блестящим блогом{21} и начнем с метода К-Minimum Values [K-минимальные величины]. Идея очень проста. Допустим, значения, которые надо посчитать, равномерно разбросаны в каком-то интервале. В нашем примере с номерами карточек от 01 до 50 и их непредсказуемым использованием это предположение вполне разумно. Теперь давайте не будем запоминать все увиденные значения, а запомним лишь несколько самых маленьких.

Возьмем снова пример с кредитными картами, где трансакций было 30, а разных карт – 22. Мы можем запомнить, скажем, всего пять самых маленьких значений. В данном случае это номера 01, 02, 05, 08 и 10. Пять значений в интервале от 1 до 10. Значит, сколько разных значений мы встретим в интервале от 1 до 50? Интервал в пять раз длиннее, значения разбросаны равномерно. Стало быть, всего значений будет

5 (значений) × 5 (интервалов) = 25 (значений)

примерно двадцать пять. Поскольку число 10 находится на самой границе интервала, делается коррекция. Для большей точности в данном случае пользуются формулой