Наиболее часто повторные числа в огромном списке чисел

Правка №2:

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

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

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

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

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

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

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

Изменить: RE комментарий

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

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

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

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

HashMap

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

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

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

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

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

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

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

NB: Подобно ответу Гшаугера, но уточнено

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

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

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

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

Это источник для java.lang.Integer.hashCode () , хеш-функции, которая будет использоваться, если вы сохраните свои записи как HashMap :

public int hashCode() {
return value;
}

Другими словами, хеш-значение (по умолчанию) для java.lang.Integer является само целым числом.

Что более эффективно, чем что?

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

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

Используйте 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);