Эффективное моделирование MruList в C # или Java - PullRequest
Новая
       20

Эффективное моделирование MruList в C # или Java

3 голосов
/ 11 мая 2009

Как бы вы реализовали общий MruList с ограниченным объемом в C # или Java?

Я хочу иметь класс, который представляет последний использованный кеш или список (= MruList). Он должен быть общим и ограничен емкостью (числом), указанным при создании экземпляра. Я хотел бы, чтобы интерфейс был что-то вроде: 

public interface IMruList<T>
{
    public T Store(T item);
    public void Clear();
    public void StoreRange(T[] range);
    public List<T> GetList();
    public T GetNext(); // cursor-based retrieval
}

Каждый магазин () должен поместить элемент в верхнюю (переднюю часть?) Списка. GetList () должен вернуть все элементы в упорядоченном списке, упорядоченном по последнему store . Если я вызову Store () 20 раз, а мой список будет состоять из 10 элементов, я хочу сохранить только 10 последних сохраненных элементов. GetList и StoreRange предназначены для поддержки поиска / сохранения MruList при запуске и завершении работы приложения.

Это для поддержки приложения с графическим интерфейсом. Я думаю, что я мог бы также хотеть знать метку времени на сохраненном элементе. Может быть. Не уверен.

Внутренне, как бы вы это реализовали и почему?

(нет, это не задание курса)

Ответы [ 7 ]

3 голосов
/ 11 мая 2009

Вот класс Cache, который хранит объекты к моменту обращения к ним. Более поздние пункты всплывают в конце списка. Кэш работает со свойством индексатора, которое принимает ключ объекта. Вы можете легко заменить внутренний словарь на список и ссылаться на список из индексатора.

Кстати, вы также должны переименовать класс в MRU:) 

class Cache
    {
        Dictionary<object, object> cache = new Dictionary<object, object>();

        /// <summary>
        /// Keeps up with the most recently read items.
        /// Items at the end of the list were read last. 
        /// Items at the front of the list have been the most idle.
        /// Items at the front are removed if the cache capacity is reached.
        /// </summary>
        List<object> priority = new List<object>();
        public Type Type { get; set; }
        public Cache(Type type)
        {
            this.Type = type;

            //TODO: register this cache with the manager 

        }
        public object this[object key]
        { 
            get 
            {
                lock (this)
                {
                    if (!cache.ContainsKey(key)) return null;
                    //move the item to the end of the list                    
                    priority.Remove(key);
                    priority.Add(key);
                    return cache[key];
                }
            }
            set 
            {
                lock (this)
                {
                    if (Capacity > 0 && cache.Count == Capacity)
                    {
                        cache.Remove(priority[0]);
                        priority.RemoveAt(0);
                    }
                    cache[key] = value;
                    priority.Remove(key);
                    priority.Add(key);

                    if (priority.Count != cache.Count)
                        throw new Exception("Capacity mismatch.");
                }
            }
        }
        public int Count { get { return cache.Count; } }
        public int Capacity { get; set; }

        public void Clear()
        {
            lock (this)
            {
                priority.Clear();
                cache.Clear();
            }
        }
    }
3 голосов
/ 11 мая 2009

Пара комментариев о вашем подходе

  • Почему Store возвращает T? Я знаю, что я только что добавил, возвращать его мне не нужно, если вы явно не хотите цепочку методов
  • Рефакторинг GetNext () в новый класс. Он представляет другой набор функций (хранение и обход курсора) и должен быть представлен отдельным интерфейсом. Он также имеет проблемы с юзабилити: что происходит, когда два разных метода, работающих в одном стеке, хотят пересечь структуру?
  • GetList () должен возвращать IEnumerable<T>. Возвращение List<T> либо вызывает явное копирование, либо возвращает указатель на базовую реализацию. Ни один не является отличным выбором.

Что касается того, что является лучшей структурой для поддержки интерфейса. Кажется, что лучше всего реализовать структуру данных, которая эффективна при добавлении на одном конце и удалении с другого. Двойной связанный список подойдет для этого.

1 голос
/ 12 мая 2009

Каждый любит катать свои собственные классы контейнеров.

Но в .NET BCL есть маленькая жемчужина SortedList<T>. Вы можете использовать это для реализации своего списка MRU или любого другого списка типов приоритетных очередей. Для эффективного добавления используется эффективная древовидная структура.

С SortedList на MSDN :

Элементы объекта SortedList сортируются по ключам либо в соответствии с конкретным IComparer реализация указана, когда SortedList создан или в соответствии с Сравнимая реализация предоставлены сами ключи. В в любом случае, SortedList не разрешить дублирование ключей.

Последовательность индекса основана на последовательность сортировки Когда элемент добавлено, оно вставлено в SortedList в правильном порядке сортировки, и индексирование корректируется соответственно. Когда элемент удален, индексация также корректируется соответственно. Следовательно индекс конкретной пары ключ / значение может измениться при добавлении элементов или удалено из объекта SortedList.

Операции над объектом SortedList имеют тенденцию быть медленнее, чем операции на Hashtable объект из-за сортировка. Тем не менее, SortedList предлагает больше гибкости, позволяя доступ к значениям либо через связанные ключи или через индексы.

Элементы в этой коллекции могут быть доступ с использованием целочисленного индекса. Индексы в этой коллекции нуль.

1 голос
/ 11 мая 2009

Вы можете создать это с Collections.Generic.LinkedList<T>. Когда вы помещаете элемент в полный список, удалите последний и вставьте новый спереди. Большинство операций должно быть в O (1), что лучше, чем реализация на основе массива.

1 голос
/ 11 мая 2009

Я бы использовал внутренний ArrayList, а Store () удалил последний элемент, если его размер превышает емкость, установленную в конструкторе. Я думаю, что стандартная терминология, как ни странно, называет это списком "LRU", потому что наименее использованный элемент - это то, что отбрасывается. См. запись в Википедии .

0 голосов
/ 12 мая 2009

Java 6 добавила новый тип коллекции с именем Deque ... для двусторонней очереди.

В частности, один из них может иметь ограниченную емкость: LinkedBlockingDeque . 

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;

public class DequeMruList<T> implements IMruList<T> {

    private LinkedBlockingDeque<T> store;

    public DequeMruList(int capacity) {
        store = new LinkedBlockingDeque<T>(capacity);
    }

    @Override
    public void Clear() {
        store.clear();
    }

    @Override
    public List<T> GetList() {
        return new ArrayList<T>(store);
    }

    @Override
    public T GetNext() {
    // Get the item, but don't remove it
        return store.peek();
    }

    @Override
    public T Store(T item) {
        boolean stored = false;
        // Keep looping until the item is added
        while (!stored) {
            // Add if there's room
            if (store.offerFirst(item)) {
                stored = true;
            } else {
                // No room, remove the last item
                store.removeLast();
            }
        }
        return item;
    }

    @Override
    public void StoreRange(T[] range) {
        for (T item : range) {
            Store(item);
        }
    }

}
0 голосов
/ 12 мая 2009

В Java я бы использовал LinkedHashMap, который создан для такого рода вещей. 

public class MRUList<E> implements Iterable<E> {
    private final LinkedHashMap<E, Void> backing;

    public MRUList() {
        this(10);
    }

    public MRUList(final int maxSize) {
        this.backing = new LinkedHashMap<E,Void>(maxSize, maxSize, true){
           private final int MAX_SIZE = maxSize;
           @Override
           protected boolean removeEldestEntry(Map.Entry<E,Void> eldest){
               return size() > MAX_SIZE;
           }
        };
    }

    public void store(E item) {
        backing.put(item, null);
    }

    public void clear() {
        backing.clear();
    }

    public void storeRange(E[] range) {
        for (E e : range) {
            backing.put(e, null);
        }
    }

    public List<E> getList() {
        return new ArrayList<E>(backing.keySet());
    }

    public Iterator<E> iterator() {
        return backing.keySet().iterator();
    }
}

Однако, это происходит в обратном порядке (т.е. сначала LRU, затем MRU). Создание этого MRU-first потребует в основном переопределения LinkedHashMap, но с добавлением новых элементов в начале списка поддержки, а не в конце.

...