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

Question

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

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

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

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

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

Answer 1

Я бы пропустил упражнение со структурами данных и просто использовал базу данных SQL. Зачем писать другую пользовательскую структуру данных, которую вы должны анализировать и отлаживать, просто используйте базу данных. Они действительно хорошо отвечают на подобные вопросы.

Answer 2

Я бы рассмотрел Trie или Направленный ациклический граф слов , который должен быть более экономичным, чем хеш-таблица. Проверкой на принадлежность строки будет O (len), где len - длина входной строки, которая, вероятно, совпадает с функцией хеширования строки.

Answer 3

Это можно решить в наихудшем случае за O ( n ), используя radix sort со счетной сортировкой в ​​качестве стабильной сортировки для каждой позиции символа. Это теоретически лучше, чем использование хеш-таблицы (O ( n ) ожидаемой, но не гарантированной) или сортировки слиянием (O ( n log n )). Использование trie также приведет к наихудшему решению O ( n ) - времени (поиск в постоянном времени по ключам n , поскольку все строки имеют ограниченную длину, которая является небольшой константой ), так что это сопоставимо. Я не уверен, как они сравниваются на практике. Radix-сортировка также довольно проста в реализации, и существует множество существующих реализаций.

Если все строки d символов или короче, а количество различных символов k , тогда радикальная сортировка занимает O ( d () n + k )) время на сортировку n ключей. После сортировки вы можете просмотреть отсортированный список за O ( n ) и увеличивать счетчик каждый раз, когда переходите к новой строке. Это будет количество отдельных строк. Поскольку d составляет ~ 15 и k относительно мало по сравнению с n (миллиард), время работы не так уж и плохо.

При этом используется пространство O ( dn ) (для хранения каждой строки), поэтому оно менее эффективно, чем пытается.

Answer 4

Если элементы являются строками, которые сопоставимы ... тогда я бы предложил отказаться от идеи Hashtable и перейти к чему-то более похожему на двоичное дерево поиска. В C # есть несколько реализаций (ни одна из которых не встроена в Framework). Обязательно приобретите сбалансированный, например, красное черное дерево или дерево AVL.

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

Кроме того, поскольку оно отсортировано, время поиска и вставки равно O log (n).

Answer 5

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

Answer 6

При наличии нескольких миллиардов строк, если даже несколько процентов являются уникальными, вероятность коллизии хеш-функции довольно высока (хэш-коды .NET имеют 32-битное целое число, что дает примерно 4 миллиарда уникальных хеш-значений. Если у вас всего несколькокак 100 миллионов уникальных строк, риск столкновения хеша может быть недопустимо высоким).Статистика - не моя сильная сторона, но некоторые исследования Google показывают, что вероятность коллизии для идеально распределенного 32-битного хэша равна (N - 1) / 2 ^ 32, где N - количество уникальных хэшируемых вещей..

Вы выполняете НАМНОГО меньшую вероятность коллизии хэшей, используя алгоритм, который использует значительно больше битов, , такой как SHA-1 .

Предполагая адекватный алгоритм хэширования,один простой подход, близкий к тому, что вы уже пробовали, - создать массив хеш-таблиц.Разделите возможные значения хеш-функции на достаточное количество числовых диапазонов, чтобы любой заданный блок не превышал ограничение 2 ГБ на объект.Выберите правильную хеш-таблицу на основе значения хеш-таблицы, затем выполните поиск в этой хеш-таблице.Например, вы можете создать 256 хеш-таблиц и использовать (HashValue)% 256, чтобы получить номер хеш-таблицы от 0..255.Используйте тот же алгоритм при назначении строки в корзину и при ее проверке / получении.

Answer 7

Словарь <> внутренне организован как список списков. Вы не приблизитесь к пределу (2GB / 8) ^ 2 на 64-битной машине.

Answer 8

Я бы использовал базу данных, подойдет любая база данных.

Вероятно, самый быстрый, потому что современные базы данных оптимизированы для скорости и использования памяти.

Вам нужен только один столбец с индексом, а затем вы можете подсчитать количество записей.

Answer 9

разделяй и властвуй - разделяй данные на первые 2 буквы (скажем)

словарь xx => словарь строк => count

Answer 10

+ 1 для решений SQL / Db упрощает работу - позволит вам сосредоточиться на реальной задаче.

Но только для академических целей я хотел бы добавить свои 2 цента.

-1 для хеш-таблиц. (Пока не могу проголосовать) Поскольку они реализованы с использованием сегментов, во многих практических реализациях стоимость хранения может быть огромной. Кроме того, я согласен с Эриком Дж. Вероятность столкновения подорвет преимущества эффективности времени.

Ли, создание дерева или DAWG займет место, а также некоторое дополнительное время (задержка инициализации). Если это не проблема (это будет иметь место, когда вам может понадобиться выполнить операции поиска с набором строк в будущем, и у вас будет достаточно памяти), попытки могут быть хорошим выбором.

Пространство будет проблемой с сортировкой Radix или подобными реализациями (как упомянуто KirarinSnow), потому что набор данных огромен.

Ниже приведено мое решение для однократного подсчета дубликатов с ограничениями на то, сколько места можно использовать.

Если у нас есть хранилище для хранения 1 миллиарда элементов в моей памяти, мы можем отсортировать их на месте к сортировке кучи за время Θ (n log n), а затем просто обойти собираем один раз за O (n) время и делаем это:

if (a[i] == a[i+1])
    dupCount++;

Если у нас не так много доступной памяти, мы можем разделить входной файл на диске на более мелкие файлы (пока размер не станет достаточно маленьким для хранения коллекции в памяти); затем отсортируйте каждый такой маленький файл, используя описанную выше технику; затем объединить их вместе. Это требует много проходов в основном входном файле.

Я хотел бы держаться подальше от быстрой сортировки , потому что набор данных огромен. Если бы я мог втиснуть немного памяти для второго случая, я бы лучше использовал его, чтобы уменьшить количество проходов, а не тратить его на сортировку слиянием / быструю сортировку (на самом деле, это сильно зависит от типа ввода, который у нас есть) ).

Редактировать: Решения SQl / DB хороши только тогда, когда вам нужно хранить эти данные в течение длительного времени.