Мне нужен CircularBuffer IDictionary. Может ли кто-нибудь указать мне хорошую реализацию с открытым исходным кодом.
Таким образом, IDictionary с максимальной емкостью, скажем, настроен на 100 элементов, при добавлении элемента 101 исходный первый элемент извлекается/удаляется из словаря, что гарантирует, что количество элементов никогда не превысит 100.
Спасибо
Чтобы сохранить вставку O(1) (с удалением самого старого элемента после 100) и поиск O(1), вам понадобится класс, который реализует IDictionary и поддерживает внутренний упорядоченный список. Если память больше беспокоит, реализация BST, такая как SortedList, может быть более подходящей. В любом случае, ваш класс будет содержать как T[], так и Dictionary<T,K> (или SortedList<T,K>). Сделайте свою собственную циклическую индексацию буфера (легко) и поддерживайте актуальность обеих коллекций в методах добавления, удаления и т. д. У вас будет:
Сделайте его универсальным и реализуйте IDictionary<T,K> и IDictionary, поскольку нет причин не делать этого, и вы получите преимущество в производительности.
Одно важное соображение: что делать с дубликатами ключей? Я предполагаю, что вы не можете сохранить дубликаты, поэтому:
Count словаря, затем вставьте ключ с помощью индексатора this[key]. если размер увеличивается, то проверьте, имеет ли список уже максимальную емкость, удалите передний элемент из списка и словаря и добавьте новый элемент в конец. Если словарь не увеличился в размере, переместите элемент с существующего места в списке в конец списка.Наконец, обратите внимание, что внутренний список содержит ключи, а не значения. Это делается для того, чтобы исключить O(1) из очереди при превышении емкости списка.
Нашел два после пяти минут гугления:
Я не знаю таких реализаций, но это не сложно реализовать самостоятельно. Поскольку словари не имеют внутреннего порядка, либо ключ, либо тип значения в словаре должны иметь некоторое свойство, представляющее порядок, в котором они были вставлены в словарь. Затем, при переопределении метода Add, он мог бы проверить, был ли счет максимальным. Если это так, просмотрите существующие пары ключ-значение, чтобы найти тот, чье свойство порядка вставки является самым низким, и замените его новой парой ключ-значение. В противном случае вставьте новую пару ключ-значение, как обычно.
Не так давно я написал полную реализацию циклического буфера на C# 3.0 и опубликовал исходный код на CodePlex. . Он следует рекомендациям по проектированию BCL и реализует все соответствующие интерфейсы из System.Collections.
Я считаю, что должно быть очень легко адаптироваться к использованию Dictionary<TKey, TValue> в качестве резервной коллекции вместо List<T>.
Как насчет этого:
public class CircularDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
private Queue<TKey> m_ItemInsertList = new Queue<TKey>();
private int m_ItemsToHold = 100;
public int ItemsToHold
{
get { return m_ItemsToHold; }
set {
if (value < 1)
throw new ArgumentException("Items to hold must be at least 1");
m_ItemsToHold = value;
}
}
public new void Add(TKey key, TValue value)
{
base.Add(key, value);
if (m_ItemInsertList.Count == m_ItemsToHold)
base.Remove(m_ItemInsertList.Dequeue());
m_ItemInsertList.Enqueue(key);
}
}
Dictionary<T,K>, поскольку его методы не являются виртуальными. Возможно, но это неэффективное использование памяти и ненужная виртуальная диспетчеризация, чтобы получить от Collection<T>, поэтому я не рекомендую это.
- person Sam Harwell; 06.08.2009
Я реализовал что-то похожее на это, используя таблицу базы данных SQLite через System.Data.Sqlite (http://sqlite.phxsoftware.com/). Вы можете хранить его на диске или в виде базы данных в оперативной памяти. Вы можете выбрать, иметь или нет уникальные ключи, и позволить механизму базы данных выполнять индексацию за вас. Вы даже можете иметь несколько значений для каждого ключа.
Когда вы записываете в таблицу, проверьте, не достигли ли вы предела в 100 записей, и если да, то удалите перед вставкой. SQLite поддерживает команду «вставить или заменить», если вы хотите сохранить уникальные ключи. Возможно, это не так элегантно, как собственное производное от IDictionary, но оно работает, оно гибкое и легко распределяется между потоками.
