Java - Поиск чего-то быстрее, чем PriorityQueue

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

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

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

Решение 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 раз, вы сможете получить топ-m объектов в своем наборе за время O (нм), которое будет строго меньше, чем n log n для достаточно больших n и достаточно малых m. Например, получение топ-10 из миллиона элементов займет вдвое меньше времени, чем использование очереди с приоритетом двоичной кучи, при прочих равных условиях.

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

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

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

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

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

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

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

Из документы Java :

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

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