Какой самый быстрый способ подсчета уникальных элементов в списке из миллиарда элементов?

Question

Моя проблема не обычная. Давайте представим несколько миллиардов строк. Строки обычно не более 15 символов. В этом списке мне нужно узнать количество уникальных элементов.

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

Вот почему я подумал, что Hashtable будет идеальным решением для этой задачи, потому что проверка списка в идеале - только log (1). К сожалению, один объект в .net может быть только 2 ГБ.

Следующим шагом будет реализация пользовательской хеш-таблицы, которая содержит список хеш-таблиц по 2 ГБ.

Мне интересно, может быть, некоторые из вас знают лучшее решение. (У компьютера очень высокая спецификация.)

Answer 1

Я согласен с другими авторами относительно решения для базы данных, но, кроме того, разумно разумное использование триггеров и потенциально симпатичная схема индексации (то есть числовое представление строк) будет самым быстрым подходом, ИМХО .

Answer 2

Вы пробовали хэш-карту (словарь в .Net)? Dictionary<String, byte> будет занимать только 5 байтов на запись в x86 (4 для указателя на пул строк, 1 для байта), что составляет около 400M элементов. Если дубликатов много, они должны соответствовать. С точки зрения реализации, он может быть очень медленным (или не работать), так как вам также нужно хранить все эти строки в памяти.

Если строки очень похожи, вы также можете написать свою собственную реализацию Trie .

В противном случае лучше всего отсортировать данные на месте (после чего подсчет уникальных элементов становится тривиальным) или использовать язык более низкого уровня памяти, такой как C ++.