CircularBuffer IDictionary в C #? - PullRequest
Новая
       71

CircularBuffer IDictionary в C #?

3 голосов
/ 06 августа 2009

Мне нужен IDictionary CircularBuffer. Может кто-нибудь указать мне на хорошую реализацию с открытым исходным кодом.

Таким образом, IDictionary, имеющий максимальную емкость, скажем, настроен на 100 элементов, который при добавлении элемента 101 извлекает / удаляет исходный первый элемент из словаря, таким образом гарантируя, что количество элементов никогда не превышает 100.

Спасибо

Ответы [ 6 ]

12 голосов
/ 06 августа 2009

Чтобы сохранить вставки O (1) (с удалением самого старого элемента после 100) и O (1), вам понадобится класс, который реализует IDictionary , а хранит внутренний упорядоченный список. Если память больше беспокоит, реализация BST, такая как SortedList, может быть более подходящей. В любом случае, ваш класс будет содержать T[] и Dictionary<T,K> (или SortedList<T,K>). Сделайте свою собственную кольцевую буферизацию (легко), и сохраняйте обе коллекции текущими в методах добавления, удаления и т. Д. Вы получите:

  • O (1) в очередь (назад)
  • O (n) вставка, которая нарушает порядок добавления (так как вы должны поддерживать массив в актуальном состоянии); вам, скорее всего, это никогда не понадобится
  • O (1) dequeue (спереди)
  • Поиск по O (1) или O (log n)

Сделайте его универсальным и внедрите IDictionary<T,K> и IDictionary, так как нет причин не делать этого, и вы получите преимущество в производительности.

Одно важное соображение : что вы делаете с дубликатами ключей? Я предполагаю, что вы не можете сохранить дубликаты, поэтому:

  • Бросить исключение (если никогда не бывает дубликатов ключей, поэтому просто вставить что-то дважды)
  • Переместиться назад: проверьте Count словаря, затем вставьте ключ с помощью индексатора this[key]. если размер увеличивается, то проверьте, имеет ли список максимальную емкость, удалите передний элемент из списка и словаря и добавьте новый элемент в конец. Если размер словаря не увеличился, переместите элемент из его существующего места в списке в конец списка.
  • Перезаписать без перемещения: тоже самое, что и предыдущий элемент, но вам не нужно возиться со списком.

Наконец, обратите внимание, что во внутреннем списке хранятся ключи, а не значения. Это необходимо для обеспечения удаления O (1) при превышении емкости списка.

4 голосов
/ 06 августа 2009

Нашли два после пяти минут поиска в Google:

3 голосов
/ 06 августа 2009

Я не знаю ни одной из таких реализаций, но не сложно реализовать себя. Поскольку словари не имеют собственного порядка, ключ или тип значения в словаре должны иметь некоторое свойство, представляющее порядок, в котором они были вставлены в словарь. Затем, в вашем переопределении метода Add, он может проверить, было ли число макс. Если так, то просмотрите существующие пары ключ-значение, чтобы найти ту, чье свойство insert-order является наименьшим, и замените ее новой парой ключ-значение. В противном случае вставьте новую пару ключ-значение как обычно.

2 голосов
/ 12 августа 2009

Не так давно я написал полную реализацию кольцевого буфера в C # 3.0 и выпустил исходный код на CodePlex . Он следует руководящим указаниям по проектированию BCL и реализует все соответствующие интерфейсы System.Collections.

Я считаю, что должно быть очень легко адаптироваться для использования Dictionary<TKey, TValue> в качестве резервного набора вместо List<T>.

0 голосов
/ 19 августа 2009

Я реализовал нечто похожее на это, используя таблицу базы данных SQLite через оболочку System.Data.Sqlite (http://sqlite.phxsoftware.com/). Вы можете сохранить ее на диске или в базе данных в памяти. Вы можете выбрать иметь или не иметь уникальные ключи и позволить ядру базы данных обрабатывать индексацию для вас. Вы можете даже иметь несколько значений на ключ.

Когда вы пишете в таблицу, проверьте, не превышен ли лимит в 100 записей, и если да, то удалите перед вставкой. SQLite поддерживает команду «вставить или заменить», если вы хотите сохранить уникальные ключи. Возможно, это не так элегантно, как создание собственного IDictionary, но оно работает, оно гибкое и легко распределяется между потоками.

0 голосов
/ 06 августа 2009

Как насчет этого: 

    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);
        }
    }
...