Мне нужен словарь (или любая другая коллекция), который всегда остается отсортированным по значению и может быть проиндексирован по ключу. Моя цель — реализовать кеш, в котором объекты имеют уникальный ключ и связанную с ними метрику. При необходимости замены кеша объекты с наименьшей метрикой удаляются. Это должно быть как можно быстрее, поэтому делать полный заказ каждый раз, когда производится замена, — не лучший вариант. Есть идеи? Спасибо
Словарь‹› всегда сортируется по значению, индекс поиска по ключу
Ответы (5)
Что-то вроде этого должно работать нормально (не очень тестировалось):
person
digEmAll
schedule
17.08.2011
Похоже, приоритетная очередь — это то, что вы ищете. Существуют хорошие реализации этого класса с использованием двоичной кучи. Пример: http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx
person
alexm
schedule
17.08.2011
Вы можете комбинировать любую очередь с быстрым приоритетом (см. здесь: очередь с приоритетом в .Net) с стандартный словарь к новой коллекции. При вставке нового элемента вставьте ссылку на элемент в оба контейнера. При поиске элемента по «ключу» используйте словарь. Когда вы собираетесь удалить элемент с наименьшей «метрикой», используйте приоритетную очередь, чтобы найти его, получите ключ из самого элемента, тогда легко удалить ссылки на элементы из обоих контейнеров.
person
Doc Brown
schedule
17.08.2011
Спасибо @Doc, это хорошая идея. Однако когда пользователь запрашивает объект, который уже хранится в кеше, его необходимо обновить, поэтому его метрика меняется, а порядок в очереди также должен обновляться. Например, если используется стратегия LFU (наименее часто используемая), каждый раз, когда объект запрашивается, его счетчик частоты, который используется в качестве метрики, увеличивается на единицу.
- person Ricardo; 18.08.2011
@Ricardo: используйте общую библиотеку C5 (itu.dk/research/c5) ваша приоритетная очередь, в ней есть операции по удалению элементов где-то в середине очереди, что дает вам возможность удалять и повторно вставлять элементы при изменении их метрик. Чтобы это работало, вам придется хранить в словаре элементы IPriorityQueueHandle, а не сами элементы, но это не должно стать слишком сложным.
- person Doc Brown; 18.08.2011
Почему бы вам просто не сохранить обычный словарь. Теперь, всякий раз, когда вам нужно выполнить эту замену кеша, вы выбираете элемент с «минимальным» значением и заменяете его.
Изменить - вот как вы получаете KeyPair с минимальным значением. Просто используйте свойства Key и Value после этого:
var minValuePair = myDictionary.OrderBy(p => p .Value).First();
person
Vladimir
schedule
17.08.2011
Спасибо за Ваш ответ. Сейчас я делаю что-то вроде этого:
myDictionary.Min(x => x.Value) но это очень медленно. Хотелось бы, чтобы словарь всегда был отсортирован, то есть при вставке нового объекта в словарь он должен располагаться в правильном для своей метрики положении.
- person Ricardo; 17.08.2011
@Ricardo Да, на самом деле я предложил альтернативное решение. Вы сказали, что вам нужен словарь, отсортированный с целью удаления минимальной пары значений, когда вам нужно обновить кеш. Это означало бы, что вам не нужно постоянно сортировать словарь, вам просто иногда нужно минимальное значение.
- person Vladimir; 17.08.2011
Вам нужен словарь, отсортированный по значению, но также имеющий индексацию по ключу. Вы не можете организовать свои данные двумя способами одновременно, поэтому вам нужно будет иметь две коллекции, ваш базовый словарь ключ-значение и словарь обратного просмотра. Ваш первый — стандартный словарь, второй — SortedDictionary с теми же данными, а ключи и значения поменялись местами. Вам придется синхронизировать их.
Вы также можете написать свою собственную реализацию словаря, чтобы объединить эти две коллекции в одну.
person
Tim Rogers
schedule
17.08.2011
Спасибо. Проблема в том, что может быть несколько объектов с одинаковым значением (метрикой).
- person Ricardo; 17.08.2011
Ссылка digEmAll - это решение, о котором я думал. Исследуйте это.
- person Tim Rogers; 17.08.2011
KeyedCollection<TKey TItem>? msdn.microsoft.com/en-us/library/ms132438.aspx является ключевой частью предмета? - person Russ Cam schedule 17.08.2011