Подсчет уникального элемента в большом массиве

Question

Один из моих коллег задал следующий вопрос в интервью.

Имеется огромный массив, в котором хранится беззнаковое целое.Длина массива 100000000. Найдите эффективный способ подсчета уникального количества элементов, присутствующих в массиве.
Например, arr = {2,34,5,6,7,2,2,5,1,34,5} O / p: счет 2 равен 3, счет 34 равен 2 и т. Д.

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

Спасибо, чота

Answer 1

Сортировка кучи O (nlogn) и на месте. На месте необходимо при работе с большими наборами данных. После сортировки вы можете сделать один проход по массиву вхождения каждого значения. Поскольку массив отсортирован, после изменения значения вы знаете, что видели все вхождения предыдущего значения.

Answer 2

Многие другие авторы предложили отсортировать данные и затем найти количество смежных значений, но никто еще не упомянул использование радикальной сортировки, чтобы получить время выполнения равным O (n lg U) (где U - максимальное значение в массив) вместо O (n lg n). Поскольку lg U = O (lg n), предполагая, что целые числа занимают одно машинное слово, этот подход асимптотически быстрее, чем heapsort.

Несопоставимые сорта всегда весело в интервью. : -)

Answer 3

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

Этот подход не требует дополнительного хранения и может быть выполнен за O (n log n) времени (для сортировки).

Answer 4

Как насчет использования BloomFilter impl: вроде http://code.google.com/p/java-bloomfilter/ сначала сделайте bloom.contains (element), если true, продолжите, если false bloom.add (element).

В конце подсчитать количество добавленных элементов. Блумфильтру нужно прибл. 250 Мб памяти для хранения 100000000 элементов по 10 бит на элемент.

Проблема в том, что ложные срабатывания возможны в BloomFilters и могут быть минимизированы только путем увеличения количества битов на элемент. Это может быть решено двумя BloomFilters с различным хэшированием, которые должны быть согласованы.

Answer 5

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

foreach x in huge_array {
   counter[x]++;
}

Таким образом, вы найдете решение за линейное время (O (n)), но за счет потребления памяти. То есть, если ваши целочисленные значения охватывают весь диапазон, разрешенный 32-битными целыми числами, вам необходимо выделить массив из 4G кратных значений, что непрактично ...

Answer 6

Сортировка это хорошая идея.Однако тип сортировки зависит от диапазона возможных значений.Для небольшого диапазона хорошо подойдет сортировка.Работая с таким большим массивом, было бы эффективно использовать несколько ядер - сортировка по основанию может быть хорошей.

Answer 7

Хеширование в этом случае не является недостатком.Стоимость будет приблизительно O(N) (O(N) для итерации по массиву и ~ O(N) для итерации по хеш-таблице).Поскольку вам нужно O(N) для проверки каждого элемента, сложность хорошая.