Извлечение данного количества самых высоких значений в Списке

Ваши варианты:

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

   ОБНОВЛЕНИЕ: Я исправлюсь, что линейный поиск обязательно лучше сортировки. См. Статью Википедии « Selection_algorithm - Выбор k наименьших или наибольших элементов » для получения более точных алгоритмов выбора.

2. Вести вручную Список (исходный или параллельный), отсортированный по весу. Вы можете использовать такие методы, как Collections.binarySearch () , чтобы определить, куда вставлять каждый новый элемент.

3. Поддерживайте список (исходный или параллельный), отсортированный по весу, вызывая Collections.sort () после каждого изменения, пакетного изменения или непосредственно перед отображением ( возможно сохранение флага модификации, чтобы избежать сортировки уже отсортированного списка).

4. Используйте структуру данных, которая поддерживает отсортированный весовой порядок: очередь приоритетов , древовидный набор и т. Д. Вы также можете создать свою собственную структуру данных.

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

Вы можете использовать max-heap .

Если ваши данные происходят из базы данных, поместите индекс в этот столбец и используйте ORDER BY и TOP или LIMIT, чтобы получить только те записи, которые вам нужно отобразить.

Поскольку вы говорите, что список элементов, из которых следует извлечь эти верхние N, может быть любого размера, и поэтому я предполагаю, что он может быть большим, я бы добавил простые ответы sort () выше (которые полностью подходят для ввода разумного размера), предполагая, что большая часть работы здесь заключается в поиске верхних N - тогда сортировка этих N тривиальна. То есть:

Queue<Integer> topN = new PriorityQueue<Integer>(n);
for (Integer item : input) {
  if (topN.size() < n) {
    topN.add(item);        
  } else if (item > topN.peek()) {
    topN.add(item);          
    topN.poll();
  }
}

List<Integer> result = new ArrayList<Integer>(n);
result.addAll(topN);
Collections.sort(result, Collections.reverseOrder());

Куча здесь (минимальная куча), по крайней мере, ограничена по размеру. Нет никакой необходимости делать кучу из всех ваших вещей.

Или приоритетную очередь.

Нет, не совсем. По крайней мере, не используя встроенные методы Java.

Есть хитроумные способы получить наибольшее (или наименьшее) количество N элементов из списка быстрее, чем операция O (n * log (n)) , но для этого вам потребуется кодировать это решение вручную. Если количество элементов остается относительно низким (не более пары сотен), сортировка его с помощью Collections.sort () , а затем захват первых N номеров - это путь для ИМО.

Если размер списка равен N, а количество элементов, которые нужно получить, равно K, вам необходимо вызвать Heapify для списка, который преобразует список (который должен быть индексируемым, например, массив) в очередь приоритета. (См. Функцию heapify в http://en.wikipedia.org/wiki/Heapsort )

Получение элемента из верхней части кучи (максимального элемента) занимает время O (lg N). Таким образом, ваше общее время будет:

O (N + k lg N)

, что лучше, чем O (N lg N), если k намного меньше, чем N.

с использованием доллара :

List<Integer> topTen = $(list).sort().slice(10).toList();

без использования доллара вы должны sort () использовать Collections.sort () , затем получите первые n элементов, используя list.sublist (0, n) .

Зависит от их количества. Давайте определим n как общее число клавиш, а m - как число, которое вы хотите отобразить.
Сортировка всего массива: O(nlogn)
Сканирование массива каждый раз для следующего наибольшего числа: O(n*m)
Итак, вопрос в том, каково отношение между n и m?
Если m < log n, то сканирование будет более эффективным.
В противном случае, m >= log n, что означает, что сортировка будет лучше. (Поскольку для крайнего случая m = log n это не имеет значения, но сортировка также даст вам преимущество в том, что вы отсортируете массив, что всегда приятно.

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

small_array = big_array.slice( number_of_items_to_find );
small_array.sort();
least_found_value = small_array.get(0).value;

for ( item in big_array ) {  // needs to skip first few items
  if ( item.value > least_found_value ) {
    small_array.remove(0);
    small_array.insert_sorted(item);
    least_found_value = small_array.get(0).value;
  }
}

small_array может быть Object [], а внутренний цикл может быть выполнен с заменой вместо фактического удаления и вставки в массив.