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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

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

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

Ответ 11

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

Ответ 12

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

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

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

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

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

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

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

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

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

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

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