Оценка количества уникальных элементов в большом списке
Сегодня у нас локальный день программиста (на этом блоге), — в начале недели, пока мозги ещё относительно свежие, разомнем-ка свои извилины, поскрипим нейронами и всё в таком духе...
Попробуйте решить задачу — дан список, содержащий 100 триллионов элементов. Элементы в списке могут повторяться. Необходимо оценить количество уникальных элементов в этом списке. Методы точного подсчета уникальных элементов не подходят, т.к. они требуют слишком много дополнительной памяти — ее количество должно быть пропорционально количеству уникальных элементов в списке.
Вначале рассмотрим основные методы точного подсчета уникальных элементов, чтобы понять, зачем им нужно столько много дополнительной памяти. Затем рассмотрим один из простейших методов оценки количества уникальных элементов, который требует существенно меньше дополнительной памяти.
Обсудить
