Есть ли способ получить IEqualityComparer от IComparer?

Question

TL; Я ищу способ получить IEqualityComparer<T> от IComparer<T>, независимо от того, какой тип данных T, включая варианты без учета регистра, если T is string. Или мне нужно другое решение для этой проблемы.

Полный текст статьи: Я реализую простой общий кэш с политикой LFU. Требование состоит в том, что должно быть возможно выбрать, будет ли кеш чувствителен к регистру или нечувствителен к регистру - если string является типом данных для ключей кеша (что необязательно). В решении я в первую очередь разрабатываю кэш, я ожидаю сотни миллиардов запросов кэш-памяти и размеры кэша не более 100 000 записей. Из-за этих чисел я сразу же отказался от использования любой строковой манипуляции, которая вызывает выделения (например, .ToLower().GetHashCode() и т. Д.), И вместо этого предпочла использовать IComparer и IEqualityComparer, поскольку они являются стандартными функциями BCL. Пользователь этого кеша может передавать сравнения с конструктором. Вот соответствующие фрагменты кода:

public class LFUCache<TKey,TValue> 
{ 
    private readonly Dictionary<TKey,CacheItem> entries; 
    private readonly SortedSet<CacheItem> lfuList; 

    private class CacheItem 
    { 
     public TKey Key; 
     public TValue Value; 
     public int UseCount; 
    } 

    private class CacheItemComparer : IComparer<CacheItem> 
    { 
     private readonly IComparer<TKey> cacheKeyComparer; 

     public CacheItemComparer(IComparer<TKey> cacheKeyComparer) 
     { 
      this.cacheKeyComparer = cacheKeyComparer; 
      if (cacheKeyComparer == null) 
       this.cacheKeyComparer = Comparer<TKey>.Default; 
     } 

     public int Compare(CacheItem x, CacheItem y) 
     { 
      int UseCount = x.UseCount - y.UseCount; 
      if (UseCount != 0) return UseCount; 
      return cacheKeyComparer.Compare(x.Key, y.Key); 
     } 
    } 

    public LFUCache(int capacity, IEqualityComparer<TKey> keyEqualityComparer, 
        IComparer<TKey> keyComparer) // <- here's my problem 
    { 
     // ... 
     entries = new Dictionary<TKey, CacheItem>(keyEqualityComparer); 
     lfuList = new SortedSet<CacheItem>(new CacheItemComparer(keyComparer)); 
    } 
    // ... 
} 

keyEqualityComparer используется для управления записью кэша (так, например, ключ «ABC» и «а» равен, если пользователь хочет). Код keyComparer используется для управления элементами кэша, отсортированными по UseCount, так что легко выбрать наименее часто используемый (реализованный в классе CacheItemComparer).

Пример правильное использование с пользовательскими сравнения:

var cache = new LFUCache<string, int>(10000, 
    StringComparer.InvariantCultureIgnoreCase, 
    StringComparer.InvariantCultureIgnoreCase); 

(Это выглядит глупо, но StringComparer реализует как IComparer<string> и IEqualityComparer<string>.) Проблема заключается в том, что если пользователь дает Несовместимые компараторов (т.е. без учета регистра keyEqualityComparer и Учитывать keyComparer), то наиболее вероятным результатом является недопустимая статистика LFU, и, таким образом, в лучшем случае будет снижаться кеш. Другой сценарий также меньше желаемого. Также, если ключ более изощрен (я буду иметь что-то похожее на Tuple<string,DateTime,DateTime>), его можно более серьезно испортить.

Вот почему я хотел бы иметь только один аргумент сравнения в конструкторе, но это не работает. Я могу создать IEqualityComparer<T>.Equals() с помощью IComparer<T>.Compare(), но я застрял в IEqualityComparer<T>.GetHashCode() - что очень важно, как вы знаете. Если бы я получил доступ к приватным свойствам компаратора, чтобы проверить, чувствителен ли он к регистру или нет, я бы использовал CompareInfo для получения хэш-кода.

Мне нравится этот подход с двумя различными структурами данных, поскольку он дает мне приемлемую производительность и контролируемое потребление памяти - на моем ноутбуке около 500 000 добавлений кеша/сек с размером кеша 10.000 элементов. Dictionary<TKey,TValue> используется только для поиска данных в O (1), а SortedSet<CacheItem> вставляет данные в O (log n), найдите элемент для удаления, вызывая lfuList.Min в O (log n), и найдите запись, чтобы увеличить счетчик использования также в O (log n).

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

Answer 1

Невозможно реализовать IComparer от IEqualityComparer, так как вы не можете узнать, больше или меньше предмета неравного.

Это невозможно реализовать IEqualityComparer из IComparer, поскольку нет никакого способа для вас, чтобы сгенерировать хеш-код, в соответствии с единицей IComparer «s.

Это не нужно, чтобы у вас были оба типа сравнения в вашем случае. При вычислении LRU вы сравниваете время, прошедшее с того момента, как элемент был использован в качестве первичного сравнения, а затем сравнивался на основе переданного в компараторе в качестве тай-брейка. Просто удалите эту последнюю часть; не имеют тай-брейка. Пусть он не определен, какой элемент выходит из кеша, когда есть связь для последнего использования. Когда вы это делаете, вам нужно принять только IEqualityComparer, а не IComparer.

Answer 2

Как я упоминал в своем комментарии, можно добавить вспомогательный метод, который мог бы сделать вещи немного проще для базового варианта использования:

public class LFUCache<TKey,TValue> 
{ 
    public static LFUCache<TKey, TValue> Create<TComp>(int capacity, TComp comparer) where TComp : IEqualityComparer<TKey>, IComparer<TKey> 
    { 
     return new LFUCache<TKey, TValue>(capacity, comparer, comparer); 
    } 
} 

и вы бы использовать его как это:

var cache = LFUCache<string, int>.Create(10000, StringComparer.InvariantCultureIgnoreCase); 

Answer 3

Хорошо повторите попытку. Вот реализация для Add и Touch для LFU:

public class LfuCache<TKey, TValue> 
{ 
    private readonly Dictionary<TKey, LfuItem> _items; 

    private readonly int _limit; 

    private LfuItem _first, _last; 

    public LfuCache(int limit, IEqualityComparer<TKey> keyComparer = null) 
    { 
     this._limit = limit; 
     this._items = new Dictionary<TKey,LfuItem>(keyComparer); 
    } 

    public void Add(TKey key, TValue value) 
    { 
     if (this._items.Count == this._limit) 
     { 
      this.RemoveLast(); 
     } 

     var lfuItem = new LfuItem { Key = key, Value = value, Prev = this._last }; 
     this._items.Add(key, lfuItem); 

     if (this._last != null) 
     { 
      this._last.Next = lfuItem; 
      lfuItem.Prev = this._last; 
     } 

     this._last = lfuItem; 

     if (this._first == null) 
     { 
      this._first = lfuItem; 
     } 
    } 

    public TValue this[TKey key] 
    { 
     get 
     { 
      var lfuItem = this._items[key]; 
      ++lfuItem.UseCount; 

      this.TryMoveUp(lfuItem); 

      return lfuItem.Value; 
     } 
    } 

    private void TryMoveUp(LfuItem lfuItem) 
    { 
     if (lfuItem.Prev == null || lfuItem.Prev.UseCount >= lfuItem.UseCount) // maybe > if you want LRU and LFU 
     { 
      return; 
     } 

     var prev = lfuItem.Prev; 
     prev.Next = lfuItem.Next; 
     lfuItem.Prev = prev.Prev; 
     prev.Prev = lfuItem; 

     if (lfuItem.Prev == null) 
     { 
      this._first = lfuItem; 
     } 
    } 

    private void RemoveLast() 
    { 
     if (this._items.Remove(this._last.Key)) 
     { 
      this._last = this._last.Prev; 
      if (this._last != null) 
      { 
       this._last.Next = null; 
      } 
     } 
    } 

    private class LfuItem 
    { 
     public TKey Key { get; set; } 

     public TValue Value { get; set; } 

     public long UseCount { get; set; } 

     public LfuItem Prev { get; set; } 

     public LfuItem Next { get; set; } 
    } 
} 

На мой взгляд, это выглядит, что Add и Touch находится в O (1), не так ли?

В настоящее время я не вижу никакого варианта использования для _first, но, возможно, ему это еще нужно. Для удаления предмета _last должно быть достаточно.

EDIT Один связанный список также будет работать, если вам не нужна операция MoveDown. EDIT Ни один связанный список не будет работать, потому что MoveUp нужен указатель Next, чтобы изменить его. Prev Указатель.