Коллекция фиксированного размера, которая хранит верхние (N) значения

Question

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

Для этого я собираю коллекцию фиксированного размера N, чтобы верхние (N) значения сортировались в порядке убывания.Метод Add(T value) отсортированной коллекции добавит значение в коллекцию, если значение больше, чем любое из существующих значений (в этом случае последний элемент удаляется) или если коллекция не заполнена.

Я смог реализовать то, что хотел, используя двукратную LinkedList<T>, поскольку он быстро вставлялся и удалялся, но мне было интересно, будет ли лучше использовать SortedDictionary<TKey, TValue> или приоритетную очередь?

Спасибо.

Answer 1

Я бы просто использовал кучу с ограниченной глубиной. Я не знаю, существует ли уже библиотека для этого, но это должно быть легко реализовать.

Answer 2

Основное преимущество использования SortedDictionary или SortedList состоит в том, что вы можете пропустить интеллектуальные функции сортировки, потому что они обрабатывают их для вас (например, вы просто должны удалять (n + 1) -й элемент каждый раз, когда добавляете значение).Но с другой стороны, принять такую ​​сложную структуру для 10 элементов похоже на использование ядерной бомбы для уничтожения мухи ...

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

Answer 3

Производительность может действительно измениться.

Для N <10 любая слишком сложная структура данных, вероятно, значительно снизит производительность (хотя, возможно, и не катастрофически), поэтому я бы использовал массив для хранения элементов.</p>

Тогда есть 3 основных способа размещения элементов в массиве:

1. сортировка, вероятно, лучший выбор для простоты:
   • постоянное времяопределить, нужно ли вставлять новый элемент (сравните с самым низким)
   • O (N) время для вставки - но это происходит только для элементов, которые находятся в N лучших на данный момент. И , если ваш ввод достаточно случайный, среднее время будет еще ниже, потому что большинство вставок будут перемещать только несколько элементов внизу вершины.
2. несортировано:
   • O (N) время для каждого элемента ввода, это слишком много по сравнению с "отсортированной"
3. двоичной кучей, которая реализует очередь с приоритетами: более сложная для реализации, новозможно, даже быстрее, чем «отсортированное»
   • постоянное время, чтобы определить, нужно ли вставлять новый элемент (сравните с самым низким)
   • O (log N) время для вставки - и это происходит только для элементов, которыев N лучших пока что

Answer 4

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

Answer 5

Если у вас нет веской причины поступить иначе, я бы использовал очередь с приоритетами.

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

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

Хотя очередь приоритетов, вероятно, излишня для только 10 элементов, она сохраняетлогика проста и эффективна как с точки зрения пространства, так и времени, поэтому, если вам когда-нибудь понадобится N = 10000 (или что-то еще), она все равно будет работать хорошо.

Answer 6

Если у вас фиксированный размер 10, почему бы просто не использовать отсортированный массив длины 10 и двоичный поиск?Но я не уверен, что при таком размере бинарный поиск не является огромной победой над тупым поиском по массиву из-за некоторых издержек.

Answer 7

Редактировать:

Если нужны только первые N значений, а остальные не представляют интереса, простой старый массив выполнит работу дешево.

Держите его отсортированным и проверьте на предмет наибольшего.И только , если нужно сохранить, вставьте его правильно и сдвиньте остальные элементы.С небольшими размерами это дешевая операция, и я предполагаю, что это будет выполняться не часто.

Answer 8

Использовать двоичную сортировку вставки для необработанного массива, выдвигая наименьшее значение с конца.Обычно это самый быстрый метод, используемый для поддержки небольших отсортированных массивов, и, например, он обычно используется как особый случай для различных алгоритмов сортировки (например, MergeSort).