Java - Ищете что-то быстрее, чем PriorityQueue

Question

Я использую Java на большом количестве данных.

[я стараюсь максимально упростить проблему]

На самом деле у меня есть небольшой класс (Элемент), содержащий INT KEY и двойной вес (с геттерами и сеттерами).

Я прочитал многие из этих объектов из файла, и мне нужно получить лучшие (наиболее весомые) объекты М.

На самом деле я использую PriorityQueue с Comparator, написанным для сравнения двух Элементов, и это работает, но это слишком медленно.

Вы знаете (я знаю, что вы знаете) какой-нибудь более быстрый способ сделать это?

Спасибо

Answer 1

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

Если вы хотите предметы с наибольшим весом, используйте min -queue & mdash; где верхняя часть кучи - самый маленький элемент. Добавление каждого элемента в максимальную очередь и проверка лучших элементов M, когда они выполнены, неэффективны.

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

В некоторых кучах есть API-интерфейсы быстрого доступа для замены вершины кучи, а в Java Queue - нет. Несмотря на это, сложность big-O одинакова.

Answer 2

В дополнение к предлагаемому алгоритму «заглянуть на вершину кучи», который дает вам O (n log m) сложность для получения top-m из n элементов, вот еще два решения.

Решение 1. Используйте кучу Фибоначчи.

Реализация PriorityQueue в JDK представляет собой сбалансированную двоичную кучу. Вы должны иметь возможность повысить производительность из реализации кучи Фибоначчи . Он будет иметь амортизированную вставку с постоянным временем, тогда как вставка в двоичную кучу имеет сложность Ω (log n) в размере кучи. Если вы делаете это для каждого элемента, то вы на Ω (n log n). Поиск топ-m из n элементов с использованием кучи Fib имеет сложность O (n + m log n). Объедините это с предложением вставлять только m элементов в кучу, и у вас будет O (n + m log m), которое настолько близко к линейному времени, сколько вы собираетесь получить.

Решение 2: Пройдите по списку M раз.

Вы должны быть в состоянии получить k-й по величине элемент в наборе за O (n) времени. Просто прочитайте все в список и сделайте следующее:

kthLargest(k, xs)
  Pick a random pivot element p from the list
    (the first one will do if your list is already random).
  Go over the set once and group it into two lists.
     Left: smaller than p. 
     Right: Larger or equal to p.
  If the Right list is shorter than k, return kthLargest(k - right.size, Left)
  If the Right list is longer than k, return kthLargest(k, right)
  Otherwise, return p.

Это дает вам O (n) время. Выполнив это m раз, вы сможете получить объекты top-m в вашем наборе за время O (nm), которое будет строго меньше, чем n log n для достаточно большого n и достаточно малого m. Например, получение топ-10 более миллиона элементов займет вдвое меньше времени, чем при использовании очереди с приоритетами двоичной кучи, при прочих равных условиях.

Answer 3

Если M достаточно мало, то сортировка всех элементов может потратить много вычислительного времени. Вы можете поместить только первые M объектов в приоритетную очередь (например, кучу, минимальный элемент сверху), а затем выполнить итерации по остальным элементам: каждый раз, когда элемент больше, чем верх кучи, удалите top и нажмите new элемент в кучу.

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

Answer 4

@ Tnay: у вас есть точка зрения о том, что вы не должны сравнивать. К сожалению, ваш пример кода все еще выполняет один. Это решает проблему:

public int compare(ListElement i, ListElement j) {
    return i.getValue() - j.getValue();
}

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

С Документация Java :

Разработчик должен убедиться, что sgn (сравнить (x, y)) == -sgn (сравнить (y, x)) для всех x и y.

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