SortedList обеспечивает последовательный доступ и поиск O(log n), что лучшее, что вы можете сделать с предоставленными коллекциями .NET.
Когда мне нужно было это сделать, я женил приоритетную очередь и словарь. Это выглядело примерно так:
var myqueue = new PriorityQueue<DataType>();
var myDictionary = new Dictionary<KeyType, PriorityQueueNode<DataType>>();
Всякий раз, когда я вставлял элемент, я вставлял его в очередь, которая возвращала PriorityQueueNode. Я вставил это в словарь.
Это дало мне O(1) поиск и O(log n) вставку. Вы можете получить амортизированную вставку O(1), если используете кучу сопряжения, а не приоритет двоичной кучи очередь, которую я использовал.
Извлечение первых k элементов — это O(n log k), где n — количество элементов в приоритетной очереди. Я использовал выборку кучи для этого. Я немного писал о выборе кучи в Когда теория встречается с практикой. Учитывая, что элементы уже находятся в куче, вы сможете сделать это за O(k), используя метод, основанный на Оптимальный алгоритм выбора в минимальной куче. Я думаю, что это возможно, но я этого не делал.
У меня есть приоритетная очередь на основе кучи, которая может вам помочь. Источник находится по адресу http://mischel.com/pubs/priqueue.zip. К сожалению, статья, которую я написал об этом, больше не доступна в Интернете. Но если вы напишите мне (jim AT mischel.com) и упомянете об этой публикации, я посмотрю, смогу ли я ее откопать.
Однако у меня больше нет кода для комбинированной очереди словаря/приоритета. Прости.
Ответы на вопросы в комментариях
Нужна ли вам приоритетная очередь или список/связанный список, зависит от того, как вы его используете и сколько элементов находится в коллекции. Если вы используете линейный список, приоритет добавления и изменения равен O(n). Удаление - O (1), если вы удаляете по ключу. Удаление по приоритету равно O(n), потому что вам нужно найти элемент, прежде чем вы сможете его удалить. Но найти лучшие k элементов тривиально: вы берете первые k элементов.
В очереди с приоритетом двоичной кучи вставка, удаление и изменение приоритета равны O(log n). Получение первых k элементов занимает O(k), но в реальном выражении медленнее, чем с линейным списком. Хотя, если вы знаете, что вам всегда нужны 10 лучших, вы можете найти и кэшировать их в отдельном списке. Таким образом, вы могли быстро вернуть их в большинстве случаев. Вы бы устанавливали грязный флаг всякий раз, когда добавляете, удаляете или меняете приоритет, чтобы вы знали, что нужно заново создавать список 10 лучших в следующий раз, когда кто-то попросит об этом.
куча сопряжения вполне может быть тем, что вы ищете. Он добавляет и удаляет за O (1) амортизированное время. Изменение приоритета не так уж плохо (см. связанную статью в Википедии и исходную статью [ссылка выше]). Удаление равно O(log n). В худшем случае для поиска первых 10 будет O (n log k), но опять же вы можете кэшировать элементы и регенерировать только первые 10, если куча изменится. Идея кэширования работает лучше всего, если k является константой или максимальное значение k составляет некоторый небольшой процент от общего числа элементов.
Вы можете взглянуть на Общую библиотеку коллекций C5, в которой есть несколько реализаций очередей с приоритетом. Я им не пользовался, но слышал о нем хорошие отзывы.
Это действительно сводится к тому, сколько элементов находится в коллекции и частоте изменений по сравнению с запросами на 10 лучших. Не требуется много элементов (я подозреваю, несколько тысяч) для стоимости операций в линейном списке. действительно убить тебя. А поскольку вы можете легко кэшировать список 10 лучших и воссоздавать его по мере необходимости, более низкая стоимость приоритетной очереди для других операций очень привлекательна при увеличении размера коллекции.
Если подумать, SortedList может быть тем, что вам нужно, учитывая ваш набор операций. Получение 10 лучших предметов происходит очень быстро. Его легко использовать. Почему бы не создать прототип и посмотреть, будет ли он работать достаточно хорошо?
person
Jim Mischel
schedule
12.09.2013
