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

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

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

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

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

Answer 4

Или приоритетная очередь .

Answer 5

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

Если ваши данные происходят из базы данных, поместите индекс в этот столбец и используйте 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

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

Answer 8

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

Существуют умные способы получить наибольшее (или наименьшее) число элементов N из списка быстрее, чем операция O(n*log(n)), но для этого потребуется вручную написать это решение. Если количество предметов остается относительно небольшим (не более пары сотен), сортировка его с помощью Collections.sort() и последующий захват первых 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 может быть объектом [], и внутренний цикл можно выполнить с помощью подкачки, а не удаления и вставки в массив.

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.