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

Question

Как реализовать универсальный 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() 20 раз, и мой список длится 10, я хочу сохранить только 10 самых недавно сохраненных предметов. GetList и StoreRange предназначены для поддержки поиска/сохранения MruList при запуске и завершении работы приложения.

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

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

(нет, это не уступка, конечно)

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

Вот класс 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(); 
      } 
     } 
    } 

Answer 5

В 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(); 
    } 
} 

Однако это итерацию точно в обратном порядке (т.е. первый НДИ, СРМ в прошлом). Для этого MRU-first потребует в основном переопределения LinkedHashMap, но вставка новых элементов в начало списка поддержки, а не в конце.

Answer 6

В Java 6 добавлен новый тип коллекции с именем Deque ... для Double-End Queue.

Существует, в частности, тот, который может быть предоставлен ограниченной емкостью: 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); 
     } 
    } 

} 

Answer 7

Все любят кататься на собственных классах контейнеров.

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

От SortedList on MSDN:

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

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

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

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