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

Question

Я пытаюсь отобразить фиксированное количество элементов на веб-странице в соответствии с их весом (представленным Integer). Список, в котором находятся эти предметы, может быть практически любого размера.

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

Answer 1

Просто пойти на Collections.sort(..), Это достаточно эффективно.

Этот алгоритм предлагает гарантированную производительность n log (n).

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

Answer 2

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

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

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

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

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

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

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

Answer 3

Или очередь приоритетов.

Answer 4

Используя доллар:

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

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

Answer 5

Вы могли бы использовать максимальную кучу.

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

Answer 6

Поскольку вы говорите, что список элементов, из которых можно извлечь эти верхние буквы 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());

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

Answer 7

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

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

Answer 8

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

Answer 9

Если сохранение отсортированного массива или использование другой структуры данных не вариант, вы можете попробовать что-то вроде следующего. Время 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[], и внутренний цикл может быть выполнен с заменой, вместо того, чтобы фактически удалять и вставлять в массив.

Answer 10

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

Извлечение предмета на вершине кучи (максимум предмета) занимает O (lg N) времени. Таким образом, ваше общее время будет:

O (N + k lg N)

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