Gibt es eine Möglichkeit, IEqualityComparer von IComparer abzuleiten?

Question

TL; DR Ich bin auf der Suche nach einer Möglichkeit, IEqualityComparer<T> von IComparer<T>, egal welcher Datentyp ist T, einschließlich der Groß- und Kleinschreibung Optionen, wenn T ist string. Oder ich brauche eine andere Lösung für dieses Problem.

Hier ist die ganze Geschichte: Ich implementiere einfachen, generischen Cache mit LFU-Richtlinie. Voraussetzung ist, dass ausgewählt werden kann, ob im Cache die Groß-/Kleinschreibung beachtet wird oder ob die Groß-/Kleinschreibung nicht beachtet wird - wenn string der Datentyp für Cache-Schlüssel ist (was nicht notwendig ist). In der Lösung, für die ich hauptsächlich den Cache entwickle, erwarte ich Hunderte von Milliarden Cache-Lookups und Cachegrößen von maximal 100.000 Einträgen. Wegen dieser Zahlen habe ich sofort auf die Verwendung von String-Manipulationen verzichtet, die Zuweisungen verursachen (wie .ToLower().GetHashCode() usw.) und stattdessen die Verwendung von IComparer und IEqualityComparer als Standard-BCL-Funktionen gewählt. Der Benutzer dieses Caches kann die Vergleiche an den Konstruktor übergeben. Hier relevante Fragmente des Codes sind:

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

Die keyEqualityComparer verwendet wird Cache-Einträge zu verwalten (so beispielsweise die Taste „ABC“ und „abc“ gleich ist, wenn der Benutzer möge). Die keyComparer wird verwendet, um Cache-Einträge zu verwalten, die nach UseCount sortiert sind, so dass es einfach ist, die am wenigsten häufig verwendeten auszuwählen (implementiert in der Klasse CacheItemComparer).

Beispiel korrekte Verwendung mit benutzerdefinierten Vergleich:

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

(Das sieht blöd, aber StringComparer implementiert sowohl IComparer<string> und IEqualityComparer<string>.) Das Problem ist, dass, wenn der Benutzer gibt unvereinbar comparers (dh Groß- und Kleinschreibung keyEqualityComparer und Groß- und Kleinschreibung keyComparer), dann ist das wahrscheinlichste Ergebnis eine ungültige LFU-Statistik und somit niedrigere Cache-Treffer im besten Fall. Das andere Szenario ist auch weniger als gewünscht. Auch wenn der Schlüssel ausgefeilter ist (ich werde etwas haben, das an Tuple<string,DateTime,DateTime> erinnert), ist es möglich, es schwerer durcheinander zu bringen.

Deshalb möchte ich nur ein einziges Vergleichsargument im Konstruktor haben, aber das scheint nicht zu funktionieren. Ich kann IEqualityComparer<T>.Equals() mit Hilfe von IComparer<T>.Compare() erstellen, aber ich bin bei IEqualityComparer<T>.GetHashCode() stecken - das ist sehr wichtig, wie Sie wissen. Wenn ich Zugriff auf private Eigenschaften des Vergleichers hatte, um zu prüfen, ob die Groß-/Kleinschreibung beachtet wird oder nicht, hätte ich CompareInfo verwendet, um Hash-Code zu erhalten.

Ich mag diesen Ansatz mit 2 verschiedenen Datenstrukturen, weil er mir akzeptable Leistung und kontrollierbaren Speicherverbrauch bietet - auf meinem Laptop rund 500.000 Cache-Ergänzungen/Sek. Mit Cache-Größe 10.000 Elemente. Dictionary<TKey,TValue> wird nur verwendet, um Daten in O (1) zu finden, und SortedSet<CacheItem> fügt Daten in O (log n) ein, finde zu entfernendes Element durch Aufrufen von lfuList.Min in O (log n) und findet den Eintrag zum Inkrementieren der Verwendungszählung auch in O (log n).

Alle Vorschläge zur Lösung dieses Problems sind willkommen. Ich werde alle Ideen, einschließlich verschiedener Designs, zu schätzen wissen.

Answer 1

Es ist nicht möglich, einen IComparer von einem IEqualityComparer zu implementieren, da Sie nicht wissen können, ob ein ungleicher Artikel größer oder kleiner als der andere Artikel ist.

Es ist nicht möglich, ein IEqualityComparer von einem IComparer zu implementieren, da es keine Möglichkeit für Sie, einen Hash-Code zu erzeugen, die mit den IComparer eigenen Identität entspricht.

Das heißt, Sie brauchen nicht beide Arten von Vergleichern in Ihrem Fall zu haben. Wenn Sie LRU berechnen, vergleichen Sie die Zeit, seit ein Artikel als primärer Vergleich verwendet wurde, und vergleichen dann anhand eines übergebenen Vergleichs als Tiebreaker. Einfach den letzten Teil entfernen; haben keinen Tiebreaker. Lass es undefiniert sein, welches Element den Cache verlässt, wenn ein Gleichstand für den zuletzt verwendeten Knoten vorliegt. Wenn Sie das tun, müssen Sie nur eine IEqualityComparer, nicht eine IComparer akzeptieren.

Answer 2

Wie ich in meinem Kommentar erwähnt, könnten Sie eine Hilfsmethode hinzufügen, die für die Dinge ein wenig einfacher Basisanwendungsfall machen könnte:

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

und Sie würden es wie folgt verwenden:

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

Answer 3

Okay nächsten Versuch. Hier ist eine Implementierung für Add und Touch für 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; } 
    } 
} 

Meiner Meinung nach sieht es so aus, dass Add und Touch in O (1), ist es nicht?

Momentan sehe ich keinen Anwendungsfall für _first, aber vielleicht braucht es noch jemand. Um einen Artikel zu entfernen, sollte _last ausreichen.

BEARBEITEN Eine einzelne verknüpfte Liste wird auch ausgeführt, wenn Sie keine MoveDown-Operation benötigen. BEARBEITEN Keine einzelne verknüpfte Liste wird nicht funktionieren, da MoveUp den Zeiger Next benötigt, um seinen Zeiger zu ändern.