Команда разработала простой алгоритм для оценки множества различных объектов в потоке данных, используя случайность.
Представьте, что вас отправили в девственный тропический лес, чтобы провести перепись дикой природы. Каждый раз, когда вы видите животное, вы делаете его фотографию. Ваша цифровая камера будет фиксировать общее количество снимков, но вас интересует только количество уникальных животных — тех, которых вы ещё не посчитали.
Как же получить это число? «Очевидное решение — запомнить всех животных, которых вы видели до сих пор, и сравнивать каждого нового зверя со списком», — сказал Лэнс Фортноу, специалист по информатике из Технологического института Иллинойса. Однако есть и более разумные способы, потому что если у вас тысячи записей, то очевидный подход далеко не прост.
Ситуация усложняется. Что, если вы работаете в Facebook и хотите узнать количество разных пользователей, которые входят в систему каждый день, даже если некоторые из них входят с нескольких устройств и несколько раз? В таком случае мы сравниваем каждый новый вход в систему со списком, который может насчитывать миллиарды записей.
В недавней статье специалисты по информатике представили новый метод для приблизительного определения количества уникальных элементов в большом списке. Этот метод требует запоминания лишь небольшого количества элементов, что делает его эффективным для использования в различных ситуациях.
Алгоритм CVM (названный в честь его создателей — Сурава Чакраборти из Индийского статистического института, Винодчандрана Варияма из Университета Небраски в Линкольне и Кулдипа Мила из Университета Торонто) позволяет отслеживать поток элементов, общее количество которых может быть больше доступной памяти. Затем он оценивает количество уникальных элементов в этом потоке.
Этот алгоритм является важным шагом на пути к решению проблемы отдельных элементов, над которой учёные-компьютерщики работают уже более 40 лет. Суть проблемы заключается в необходимости эффективного мониторинга потока элементов и оценки количества уникальных элементов в этом потоке, когда общее количество элементов может превышать доступную память.
Эндрю Макгрегор из Массачусетского университета в Амхерсте отмечает, что новый алгоритм удивительно прост и легко реализуем. Он также предполагает, что этот метод может стать стандартным способом решения проблемы отдельных элементов на практике.
Чтобы наглядно представить проблему и показать, как алгоритм CVM её решает, можно рассмотреть ситуацию, когда вы слушаете аудиокнигу «Гамлет». В пьесе 30 557 слов. Сколько из них уникальны?
Чтобы это выяснить, можно прослушать аудиозапись (при необходимости нажимая паузу), записывать каждое слово в блокнот в алфавитном порядке и не учитывать уже записанные слова. Когда вы дойдёте до конца, просто сосчитаете количество слов в вашем списке. Этот метод работает, но требует большого объёма памяти, примерно равного количеству уникальных слов.
В типичных ситуациях, когда данные поступают потоком, может потребоваться отслеживать миллионы элементов. Вариам сказал, что, возможно, вам не захочется хранить все эти данные. И здесь алгоритм CVM предлагает более простой способ. По словам Вариама, хитрость заключается в том, чтобы положиться на рандомизацию.
Давайте вернёмся к «Гамлету», но на этот раз у вас будет только 100 слов в памяти. Когда начнётся игра, вы запишете первые 100 услышанных слов, не включая повторы. Как только вы заполните пробел, нажмите паузу и бросайте монетку за каждое слово: орёл — слово остаётся в списке, решка — вы его удаляете. Таким образом, после предварительного раунда у вас останется около 50 отдельных слов.
Затем начинается первый раунд. Продолжайте читать «Гамлета», добавляя новые слова по ходу. Если вы наткнулись на слово, которое уже есть в списке, снова бросьте монетку. Если выпадет решка, удалите слово, если орёл — оставьте. Продолжайте так, пока на доске не будет 100 слов. Затем случайным образом удалите примерно половину слов, основываясь на результате предыдущих 100 бросков монетки.
Переходим ко второму раунду. Продолжайте так же, как в первом раунде, но теперь усложним задачу: когда вы дойдёте до повторяющегося слова, снова бросьте монетку. Если выпадет решка, удалите его, как и раньше. Но если выпадет орёл, вы бросите монету ещё раз. Слово останется в списке только если выпадет два орла подряд. После того, как вы заполните доску, раунд закончится очередной чисткой примерно половины слов на основе 100 бросков монетки.
В третьем раунде вам понадобятся три орла подряд, чтобы оставить слово в списке. В четвёртом раунде — четыре орла. И так далее.
В конце концов, в k-м раунде вы дойдёте до конца «Гамлета».
Цель этого упражнения — убедиться, что каждое слово имеет одинаковую вероятность попасть в список: 1/2k. Например, если в конце «Гамлета» в вашем списке было 61 слово, и вы прошли шесть раундов, то можно разделить 61 на вероятность 1/26, чтобы узнать количество отдельных слов. В этом случае получится примерно 3904 слова.
Как работает эта процедура? Представьте, что у вас есть 100 монет, и вы подбрасываете каждую по отдельности, оставляя только те, которые выпадают орлом. В итоге останется около 50 монет. Если кто-то разделит это число на вероятность 1/2, то может предположить, что изначально было примерно 100 монет.
Чакраборти, Вариам и Меел математически доказали, что эффективность этого метода зависит от объёма памяти.
У Гамлета в запасе ровно 3967 уникальных слов (по подсчётам учёных). В экспериментах с памятью на 100 слов средняя оценка после пяти запусков составила 3955 слов. Однако при увеличении объёма памяти до 1000 слов средний показатель вырос до 3964.
«Конечно, — сказал Вариам, — если объём памяти настолько велик, что в него помещаются все слова, то мы можем достичь 100% точности».
Уильям Кушмаул из Гарвардского университета отметил, что это отличный пример того, как даже для очень простых и хорошо изученных проблем иногда существуют очень простые, но неочевидные решения, которые всё ещё ждут своего открытия.
РАДИО 24/7:
✯ основной поток МР3 128 Кб/с https://myradio24.com/astrax
✯ ссылка для вашего плеера https://myradio24.org/astrax
✯ поток для экономии трафика и медленного интернета МР3 64 Кб/с (моно) https://astrax.radio12345.com/
✯ Источник увлекательных новостей - https://dzen.ru/radioastrax
✯ Астра-Х ДАЙДЖЕСТ - https://radioastrax.mave.digital/
✯ Научные теории и эксперименты - https://dzen.ru/fisicaonline
✯ Радиопрограмма РИТМЫ ПЛАНЕТЫ - https://vk.com/ritmidelpianeta
И ещё...
Ракета Falcon 9 выполняет штатный запуск партии спутников Starlink. Первая ступень ракеты должна совершить 21-й полёт с возвращением на плавучую платформу. Ранее ожидалось, что ступени смогут летать не более 20 раз и сейчас преодолевается важный психологический рубеж. В планах SpaceX поднять ресурс ступеней до 40 пусков.