Используя случайность, команда учёных создала простой алгоритм для подсчёта большого количества отдельных объектов в потоке данных.
Представьте, что вас отправили в девственный тропический лес, чтобы провести перепись диких животных. Каждый раз, когда вы видите животное, вы делаете снимок. Ваша цифровая камера будет фиксировать общее количество снимков, но вас интересует только количество уникальных животных — всех тех, которых вы ещё не посчитали. Как лучше всего получить это число? «Очевидное решение — запомнить всех животных, которых вы уже видели, и сравнивать каждое новое животное с этим списком», — говорит Лэнс Фортноу, специалист по информатике из Иллинойского технологического института. Но есть и более умные способы, добавил он, потому что если у вас тысячи записей, то очевидный подход далеко не так прост.
Всё становится ещё хуже. Что, если вы — Facebook, и вам нужно подсчитать количество отдельных пользователей, которые заходят на сайт каждый день, даже если некоторые из них заходят с нескольких устройств и в разное время? Теперь мы сравниваем каждый новый вход со списком, который может исчисляться миллиардами.
В недавней статье учёные описали новый способ приблизительного определения количества отдельных записей в длинном списке, который требует запоминания лишь небольшого числа записей. Алгоритм работает для любого списка, в который элементы поступают по одному — как слова в речи, товары на конвейере или автомобили на шоссе.
Алгоритм CVM, названный так по имени его создателей — Сурава Чакраборти из Индийского статистического института, Винодчандрана Варияма из Университета Небраски в Линкольне и Кулдипа Мила из Университета Торонто, — это значительный шаг к решению так называемой проблемы отдельных элементов, над которой компьютерные учёные бьются уже более 40 лет. Она заключается в том, чтобы найти способ эффективно отслеживать поток элементов, общее количество которых может превышать объём доступной памяти, а затем оценить количество уникальных элементов.
"Новый алгоритм поразительно прост и лёгок в реализации", — говорит Эндрю Макгрегор из Массачусетского университета в Амхерсте. "Я не удивлюсь, если на практике это станет стандартным подходом к проблеме [отдельных элементов]".
Чтобы проиллюстрировать проблему и то, как алгоритм CVM её решает, представьте, что вы слушаете аудиокнигу "Гамлет". В пьесе 30 557 слов. Сколько из них являются уникальными? Чтобы узнать это, вы можете прослушать пьесу (часто пользуясь кнопкой паузы), записать каждое слово в алфавитном порядке в блокнот и пропускать слова, которые уже есть в вашем списке. Когда вы дойдёте до конца, вы просто посчитаете количество слов в списке. Этот подход работает, но он требует объёма памяти, примерно равного количеству уникальных слов.
В типичных ситуациях потоковой передачи данных могут быть миллионы элементов, которые необходимо отслеживать. «Возможно, вы не захотите хранить всё», — говорит Вариям. И именно здесь алгоритм CVM может предложить более простой путь. Хитрость, по его словам, заключается в том, чтобы полагаться на рандомизацию.
Вернёмся к "Гамлету", но на этот раз в вашей рабочей памяти, состоящей из доски, есть место всего для 100 слов. Как только пьеса начнётся, вы запишете первые 100 слов, которые услышите, снова пропуская все повторы. Когда место будет заполнено, нажмите на паузу и подбросьте монетку для каждого слова. Орёл — слово остаётся в списке; решка — вы его удаляете. После этого предварительного раунда у вас останется около 50 разных слов.
Теперь вы переходите к тому, что команда называет раундом 1. Продолжайте читать "Гамлета", добавляя новые слова по ходу дела. Если вы встретите слово, которое уже есть в вашем списке, снова подбросьте монетку. Если выпадет орёл, вычеркните слово; если решка — слово останется в списке. Продолжайте в том же духе, пока на доске не останется 100 слов. Затем снова удалите в случайном порядке примерно половину, основываясь на результатах 100 подбрасываний монетки. На этом первый раунд завершён.
Далее переходите ко второму раунду. Продолжайте, как в первом раунде, только теперь мы усложним задачу. Когда вы дойдёте до повторяющегося слова, снова подбросьте монетку. Если выпадет орёл, вы удалите его, как и раньше. Но если выпадет решка, подбросьте монету второй раз. Оставляйте слово, только если выпала вторая решка. Как только вы заполните доску, раунд закончится ещё одной очисткой примерно половины слов, основанной на 100 бросках монеты.
В третьем раунде, чтобы оставить слово, вам потребуется три решки подряд. В четвёртом раунде вам понадобится четыре решки подряд. И так далее.
В конце концов, в k-м раунде вы дойдёте до конца "Гамлета". Смысл упражнения заключается в том, чтобы убедиться, что каждое слово, в силу случайного выбора, имеет одинаковую вероятность оказаться там: 1/2^k. Если, например, в конце "Гамлета" в вашем списке оказалось 61 слово, а процесс занял шесть раундов, вы можете разделить 61 на вероятность, 1/2^6, чтобы оценить количество отдельных слов — в данном случае это 3 904. (Легко понять, как работает эта процедура: предположим, у вас есть 100 монет, и вы подбрасываете каждую по отдельности, сохраняя только те, что выпали решками. В итоге у вас будет около 50 монет, и если кто-то разделит это число на вероятность ½, то сможет догадаться, что изначально монет было около 100.)
Вариям и его коллеги математически доказали, что точность этой техники зависит от объёма памяти. В "Гамлете" ровно 3 967 уникальных слов. (В экспериментах с памятью на 100 слов средняя оценка после пяти запусков составила 3 955 слов. При памяти в 1 000 слов среднее значение улучшилось до 3 964. "Конечно, — говорит Вариям, — если память настолько велика, что в ней помещаются все слова, то мы можем добиться 100-процентной точности".
"Это отличный пример того, что даже для базовых и хорошо изученных проблем иногда находятся очень простые, но неочевидные решения, которые ещё предстоит найти", — сказал Уильям Кушмаул из Гарвардского университета.
Автор: Вячеслав Голованов
