VPF::Dictionary с ограничением - Форум программистов

fessko

Дата 2.7.2006, 13:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 15
Регистрация: 25.6.2006
Где: Минск, Беларусь

Репутация: нет
Всего: нет

Есть такая задачаю Необходимо расширить Dictionaty<T,U> так, чтобы в нем хранилось только 10 записей. Но, если мы хотим добавить 11-ую запись, то самая старая запись удаляется. Самой старой является запись которую раньше других добавили, модифицировали, получали доступ к ней. Все операции должны выполняться за О(1). В этом и проблема. Как сделать так, чтобы добавление, доступ выполнядись за О(1). Если для каждой записи хранить время последнего доступа, мне все равно надо работать со всеми элементами - а это уже не О(1)

ivashkanet

Дата 2.7.2006, 14:20 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 47
Всего: 149

Цитата(fessko @ 2.7.2006, 13:15

)

О(1)

Что то я не понимаю что это smile

А по делу: что мешает наследоваться от Dictionary. В новом классе можно хранить время доступа к каждой записи, переписать метод Add (и другие), позволяя им удалять старую запись и добавлять на ее место новую.

--------------------

design, simplicity, and experience with a technology focus

Void

Дата 2.7.2006, 18:35 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 25
Всего: 173

Цитата(ivashkanet @ 2.7.2006, 16:20

)

О(1)

Что то я не понимаю что это

Срочно читать о Big O нотации.

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

Вот примерная реализация:

Код

using System;
using System.Collections.Generic;


class LruDictionary<Key, Value> : IDictionary<Key, Value>
{
    #region Private Members

    private int _maxCount;

    private LinkedList<KeyValuePair<Key, Value>> _lruList =
        new LinkedList<KeyValuePair<Key, Value>>();

    private Dictionary<Key, LinkedListNode<KeyValuePair<Key, Value>>> _dict;

    #endregion

    #region Public Constructor

    public LruDictionary(int maxCount)
    {
        _maxCount = Math.Max(1, maxCount);
        _dict = new Dictionary<Key, LinkedListNode<KeyValuePair<Key, Value>>>(MaxCount);
    }

    #endregion

    #region Public Properties

    public int MaxCount
    {
        get { return _maxCount; }
    }

    #endregion

    #region Private Methods

    private void Promote(Key key)
    {
        LinkedListNode<KeyValuePair<Key, Value>> node = _dict[key];
        _lruList.Remove(node);
        _lruList.AddLast(node);
    }

    #endregion

    #region IDictionary<Key,Value> Members

    public void Add(Key key, Value value)
    {
        Remove(key);
        if (Count >= MaxCount)
        {
            _dict.Remove(_lruList.First.Value.Key);
            _lruList.RemoveFirst();
        }
        _dict.Add(key, _lruList.AddLast(new KeyValuePair<Key, Value>(key, value)));
    }

    public bool ContainsKey(Key key)
    {
        return _dict.ContainsKey(key);
    }

    public ICollection<Key> Keys
    {
        get { return _dict.Keys; }
    }

    public bool Remove(Key key)
    {
        if (_dict.ContainsKey(key))
        {
            _lruList.Remove(_dict[key]);
            _dict.Remove(key);
            return true;
        }
        return false;
    }

    public bool TryGetValue(Key key, out Value value)
    {
        if (!ContainsKey(key))
        {
            value = default(Value);
            return false;
        }
        Promote(key);
        value = _dict[key].Value.Value;
        return true;
    }

    public ICollection<Value> Values
    {
        get { throw new NotSupportedException(); }
    }

    public Value this[Key key]
    {
        get
        {
            if (!ContainsKey(key))
                throw new KeyNotFoundException();
            Promote(key);
            return _dict[key].Value.Value;
        }
        set
        {
            Add(key, value);
        }
    }

    #endregion

    #region ICollection<KeyValuePair<Key,Value>> Members

    public void Add(KeyValuePair<Key, Value> item)
    {
        Add(item.Key, item.Value);
    }

    public void Clear()
    {
        _lruList.Clear();
        _dict.Clear();
    }

    public bool Contains(KeyValuePair<Key, Value> item)
    {
        if (!ContainsKey(item.Key))
            return false;
        return _dict[item.Key].Value.Value.Equals(item.Value);
    }

    public void CopyTo(KeyValuePair<Key, Value>[] array, int arrayIndex)
    {
        _lruList.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return _dict.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(KeyValuePair<Key, Value> item)
    {
        if (!Contains(item))
            return false;
        Remove(item.Key);
        return true;
    }

    #endregion

    #region IEnumerable<KeyValuePair<Key,Value>> Members

    public IEnumerator<KeyValuePair<Key, Value>> GetEnumerator()
    {
        foreach (LinkedListNode<KeyValuePair<Key, Value>> node in _dict.Values)
            yield return node.Value;
    }

    #endregion

    #region IEnumerable Members

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion
}

Это сообщение отредактировал(а) Void - 2.7.2006, 18:44

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

ivashkanet

Дата 2.7.2006, 19:02 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 47
Всего: 149

Void, спасибо за cсылку. Насколько я понял, О(1) означает, что операции добавления, удаления, ... должны выполнятся за заранее определенное число комманд и это число не зависело бы от числа элементов в Dictionary. Я прав?

--------------------

design, simplicity, and experience with a technology focus

fessko

Дата 2.7.2006, 22:25 (ссылка)

(нет голосов)

Загрузка ...

Void, cпасибо. Я для себя открыл, что в List<> все основные операции над элементами выполняются за O(1). smile

ivashkanet

Цитата

Насколько я понял, О(1) означает, что операции добавления, удаления, ... должны выполнятся за заранее определенное число комманд и это число не зависело бы от числа элементов в Dictionary.

Абсолютно верно.

Это сообщение отредактировал(а) fessko - 2.7.2006, 22:33

Void

Дата 2.7.2006, 22:28 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 25
Всего: 173

fessko, в List<> — нет, в LinkedList<> — да. Любые сомнения решаются Reflector'ом smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

fessko

Дата 2.7.2006, 22:38 (ссылка)

(нет голосов)

Загрузка ...

Void. Точно! Забыл помотреть удаление у List<>, а оно оказалось за О(n).
Но у LinkedList поиск за О(n) операций. Т.е. доступ к элементу в этом случае у меня будет не константный.

Это сообщение отредактировал(а) fessko - 2.7.2006, 22:42

mr.DUDA

Дата 3.7.2006, 01:53 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 110
Всего: 232

Цитата(fessko @ 2.7.2006, 22:38

)

Но у LinkedList поиск за О(n) операций. Т.е. доступ к элементу в этом случае у меня будет не константный.

Но ведь, LinkedList служит не для поиска, а для статистики по операциям чтения/добавления/удаления !

--------------------

fessko

Дата 3.7.2006, 20:18 (ссылка)

(нет голосов)

Загрузка ...

А как получить thread-safe версию. Что-то я немного недопонимаю.

mr.DUDA

Дата 3.7.2006, 21:33 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 110
Всего: 232

Цитата(fessko @ 3.7.2006, 20:18

)

А как получить thread-safe версию. Что-то я немного недопонимаю.

Ставим lock-и на все операции поиска и модификации Dictionary. Всё.

--------------------

ivashkanet

Дата 4.7.2006, 10:13 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 47
Всего: 149

У меня вопрос. А что метод

Цитата(Void @ 2.7.2006, 18:35

)

_lruList.Remove(node);

в коде

Код

    private void Promote(Key key)    
    {    
        LinkedListNode<KeyValuePair<Key, Value>> node = _dict[key];    
        _lruList.Remove(node);    
        _lruList.AddLast(node);    
    }

будет выполняться за O(1). ИМХО, врятли. Тут будет сильно завязано на количестве элементов в ... Стопп.
...
Глянул в Рефлекторе на LinkedList и убедился что все пучком smile

P.S. Решил всетки запостить smile

, вдруг у кого-нибудь такая же мысль возникнет smile

Добавлено @ 10:26

Цитата(ivashkanet @ 4.7.2006, 10:13

)

_dict[key]

Кстати эта инструкция выполняется не за O(1). Это нормально?

--------------------

design, simplicity, and experience with a technology focus

ivashkanet

Дата 4.7.2006, 10:28 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 47
Всего: 149

Думаю да. Невозможно ( smile

) создать Dictionary с доступом O(1).
Как минимум тогда бы это было реализовано в .Net smile

--------------------

design, simplicity, and experience with a technology focus

fessko

Дата 4.7.2006, 12:30 (ссылка)

(нет голосов)

Загрузка ...

Цитата из MSDN:

Цитата

The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

The speed of retrieval depends on the quality of the hashing algorithm of the type specified for TKey.

Т.о. доступ к элементу почти О(1).

ivashkanet

Дата 4.7.2006, 12:53 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 47
Всего: 149

В том то и дело что почти
Можно посмотреть код поиска в рефлекторе

Добавлено @ 12:54
Там поиск ведется For-ом. Правда довольно хитрым способом

--------------------

design, simplicity, and experience with a technology focus

Void

Дата 4.7.2006, 16:20 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 25
Всего: 173

ivashkanet, Dictionary<,> — это хэш-таблица. Среднее время доступа к элементу хэш-таблицы O(1), но в худшем случае (при большом числе коллизий из-за неудачной хэш-функции) будет O(N).

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »