SilentSokolov
@SilentSokolov

Подсчет уникальных значений с минимальной погрешностью?

Есть файлы в которых содержится данные почти о миллиарде деталей, у каждой детали есть характеристики. Нужно за относительно короткое время (10 сек), с минимальной погрешностью определить кол-во деталей с теми или иными (include/exclude) характеристиками. Характеристики можно представить в виде ID.

Есть какие-то кейсы для решения подобных задач?

Пытался решить задачу через Spark и его кеш, но по скорости такое решение не подходит.
  • Вопрос задан
  • 1076 просмотров
Пригласить эксперта
Ответы на вопрос 3
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Есть файлы
Нужно просто из них создать базу и проиндексировать все необходимые поля.
Раз уж заговорили про собственную базу: бинарный кортеж и затем, бинарное неполносвязное "дерево" из них.
Это позволит искать начиная с любых входных данных сразу весь список объектов.
Ответ написан
@nirvimel
Все зависит от формата хранения/представления этих данных. Должен быть свой кастомный формат, компактный (чтобы сократить доступ к памяти) и удобный исключительно для быстрого сканирования (прохода по всем записям), и ни для чего другого. Я бы написал это под Cython или Numba с компактным представлением данных в Numpy. При таком большом количестве мелких записей и, в общем то, тривиальном алгоритме их обработки основным bottleneck в плане производительности становится не CPU, а доступ к RAM, поэтому от "хитрости" самого алгоритма подсчета (какие тут могут быть хитрости?) тут мало что зависит, зато компактность структуры данных (даже за счет не очень удобного доступа к ней) будет играть решающую роль.
Ответ написан
@Vlad_Fedorenko
Гляньте в сторону HyperLogLog - можно считать приблизительное количество элементов в потоке.
https://m.habrahabr.ru/post/119852/
Реализация есть в Redis
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы