Большой файл, содержащий 1 миллион целых чисел. Какой самый быстрый способ найти наиболее часто встречающийся файл?

Question

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

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

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

Есть ли лучший и более эффективный способ сделать это?

Answer 1

Ну, миллион уже не так много, поэтому давайте предположим, что мы говорим о нескольких миллиардах целых чисел.

В этом случае я бы посоветовал вам их хешировать и разделить на 2 ^ N сегмента (отдельные файлы или предварительно выделенные части одного и того же файла) с использованием старших N битов их значений хеш-функции.

Вы бы выбрали N так что результирующие сегменты с большой вероятностью будут достаточно малы для обработки в памяти.

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

В маловероятном случае, когда в корзине слишком много уникальных значений, чтобы поместиться в ОЗУ, перераспределите, используя следующие N бит хеша, и повторите попытку.