Наиболее часто повторяющиеся цифры в огромном списке номеров

Question

У меня есть файл, в котором много случайных целых чисел (около миллиона), каждое из которых разделено пробелом. Мне нужно найти топ-10 наиболее часто встречающихся номеров в этом файле. Каков наиболее эффективный способ сделать это в Java? Я могу думать о 1. Создайте хэш-карту, ключом является целое число из файла, а значением - количество. Для каждого числа в файле проверьте, существует ли этот ключ в хэш-карте, если да, значение ++, в противном случае введите новую запись в хеш 2. Сделайте BST, каждый узел является целым числом из файла. Для каждого целого числа из файла посмотрите, есть ли в BST узел, если да, укажите значение ++, значение является частью узла.

Я чувствую, что хэш-карта - лучший вариант, если я могу придумать хорошую функцию хеширования, Может кто-нибудь подскажет мне, как лучше всего это сделать? Есть ли еще какой-нибудь эффективный алгоритм, который я могу использовать?

Answer 1

Редактировать # 2:

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

И я ВСЕГДА сделаю ДРУГОЕ примечание о скорости тестирования, прежде чем беспокоиться о хитрых реализациях.

(Ниже приведен более старый устаревший пост, который все еще мог бы быть действительным, если бы кто-то имел НАМНОГО больше очков, чем миллион)

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

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

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

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

Редактировать: RE комментарий

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

Обычно это будет оптимизация (зло), но когда вы начинаете получать около сотен тысяч узлов, вам иногда приходится обеспечивать эффективность, поэтому встроенный TreeMap будет неэффективным по тем же причинам, что и встроенный -в HashSet будет.

Answer 2

Java обрабатывает хеширование. Вам не нужно писать хеш-функцию. Просто начните помещать вещи в хэш-карту.

Кроме того, если это то, что нужно запускать только один раз (или только иногда), не оптимизируйте оба. Это будет достаточно быстро. Только беспокойтесь, если это что-то, что будет работать в приложении.

Answer 3

HashMap

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

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

Answer 4

Зачем использовать хеш-таблицу? Просто используйте массив, размер которого совпадает с диапазоном ваших чисел. Тогда вы не тратите время на выполнение функции хеширования. Затем отсортируйте значения после того, как вы закончите. O (N log N)

Answer 5

На самом деле, существует алгоритм O (n) для того, чтобы делать именно то, что вы хотите. Ваш вариант использования аналогичен кэш-памяти LFU, где счетчик доступа к элементу определяет, находится ли он в кеше или исключен из него.

http://dhruvbird.blogspot.com/2009/11/o1-approach-to-lfu-page-replacement.html

Answer 6

Используйте HashMap, чтобы создать набор данных (пары значений-счетчиков) в памяти при прохождении файла. HashMap должен предоставить вам почти O (1) доступ к элементам при создании набора данных (технически в худшем случае HashMap - O (n)). Как только вы закончите поиск файла, используйте Collections.sort () для значения Collection, возвращаемого HashMap.values ​​(), чтобы создать отсортированный список пар счетчик значений. Использование Collections.sort () гарантировано O (nLogn). Например:

public static class Count implements Comparable<Count> {
    int value;
    int count;
    public Count(int value) {
        this.value = value;
        this.count = 1;
    }
    public void increment() {
        count++;
    }
    public int compareTo(Count other) {
        return other.count - count;
    }
}

public static void main(String args[]) throws Exception {
    Scanner input = new Scanner(new FileInputStream(new File("...")));
    HashMap<Integer, Count> dataset = new HashMap<Integer, Count>();
    while (input.hasNextInt()) {
        int tempInt = input.nextInt();
        Count tempCount = dataset.get(tempInt);
        if (tempCount != null) {
            tempCount.increment();
        } else {
            dataset.put(tempInt, new Count(tempInt));
        }
    }

    List<Count> counts = new ArrayList<Count>(dataset.values());
    Collections.sort(counts);

Answer 7

Если диапазон чисел небольшой (например, 0-1000), используйте массив. В противном случае используйте HashMap<Integer, int[]>, где все значения являются массивами длины 1. Это должно быть намного быстрее увеличивать значение в массиве примитивов, чем создавать новое целое число каждый раз, когда вы хотите увеличить значение. Вы по-прежнему создаете целочисленные объекты для ключей, но этого трудно избежать. В конце концов, невозможно создать массив из 2 ^ 31-1 целых.

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

Answer 8

Если вы хотите сделать его максимально эффективным, используйте массив целых чисел, где позиция представляет значение, а содержимое - количество. Таким образом вы избежите автобоксирования и распаковки, наиболее вероятного убийцы стандартной коллекции Java.

Если диапазон чисел слишком велик, взгляните на PJC и его IntKeyIntMap реализации. Это также позволит избежать автобокса. Я не знаю, будет ли это достаточно быстро для вас.

Answer 9

1. Выделите массив / вектор того же размера, что и количество элементов ввода, которые у вас есть
2. Заполните массив из вашего файла числами, по одному на элемент
3. Привести список в порядок
4. Выполняйте итерацию по списку и отслеживайте 10 самых популярных серий чисел, с которыми вы столкнулись.
5. Выведите десятку прогонов в конце.

В качестве уточнения на шаге 4 вам нужно только шагать вперед по массиву в шагах, эквивалентных вашему 10-му самому длинному пробегу. Любой пробег дольше, чем это будет перекрываться с вашей выборкой. Если десятый самый длинный прогон имеет длину 100 элементов, вам нужно только отобрать элемент 100, 200, 300 и в каждой точке отсчитать прогон целого числа, которое вы там найдете (и вперед, и назад). Любая пробежка, превышающая ваш 10-й самый длинный, наверняка пересекается с вашей выборкой.

Эту оптимизацию следует применять после того, как длина 10-го цикла очень велика по сравнению с другими сериями в массиве.

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

NB: похоже на ответ гшаугера, но конкретизировано

Answer 10

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

Для ваших методов вы делаете n вставок, а затем сортируете по O (n * log (n)), поэтому ваш коэффициент сложности выше.