IComparer'dan IEqualityComparer türetmenin bir yolu var mı?

Question

TL; Tstring ise TT, hangi veri türü olursa olsun, IComparer<T> gelen IEqualityComparer<T> elde etmek için bir yöntem arıyorum. Ya da bu sorun için farklı bir çözüme ihtiyacım var.

İşte tam hikaye: LFU ilkesiyle basit, genel önbellek yapıyorum. Önkoşul, önbelleklerin büyük/küçük harfe duyarlı veya büyük/küçük harfe duyarlı olup olmadığını seçmek için mümkün olmalıdır - eğer string önbellek anahtarları için veri türü ise (ki bu gerekli değildir). Öncelikle önbellek için geliştirdiğim çözümde, yüz milyarlarca önbellek araması ve maksimum 100.000 giriş önbellek boyutu bekliyorum. Bu sayılar nedeniyle hemen ayırmalara neden olan (.ToLower().GetHashCode() vb.) Herhangi bir dize manipülasyonu kullanmaktan vazgeçtim ve bunun yerine standart BCL özellikleri oldukları için IComparer ve IEqualityComparer kullanmayı tercih ettim. Bu önbelleğin kullanıcısı, karşılaştırıcıları yapıcıya iletebilir. İşte kod alakalı fragmanları şunlardır:

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 önbellek girdilerini yönetmek için kullanılır (kullanıcı isterse bu yüzden örneğin anahtar "ABC" ve "abc" eşittir). keyComparer, UseCount tarafından sıralanmış önbellek girdilerini yönetmek için kullanılır, böylece en az sıklıkla kullanılanı (CacheItemComparer sınıfında uygulanır) seçmek kolaydır. özel karşılaştırma ile

Örnek Doğru kullanım:

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

(O aptal görünüyor, ama StringComparer hem IComparer<string> ve IEqualityComparer<string> uygular.) sorun olduğunu kullanıcı uyumsuz comparers keyComparer duyarlı (yani harf duyarsız keyEqualityComparer ve davayı verirse), o zaman en olası sonuç geçersiz LFU istatistikleridir ve bu nedenle en düşük düzeyde önbellek isabetleri olur. Diğer senaryo da istenenden daha azdır. Ayrıca anahtar daha sofistike ise (Tuple<string,DateTime,DateTime> benzeyen bir şey var), daha da ciddiye almak mümkündür.

Bu nedenle, kurucuda yalnızca tek bir karşılaştırma argümanı kullanmak istiyorum, ancak bu işe yaramaz. yardımı ile IEqualityComparer<T>.Equals()'u oluşturabiliyorum, ama ben IEqualityComparer<T>.GetHashCode()'da sıkışıp kaldım - bildiğiniz gibi çok önemlidir. Vakaya duyarlı olup olmadığını kontrol etmek için karşılaştırıcının özel özelliklerine erişebilseydim, hash kodunu almak için CompareInfo kullanmış olurdum. bana kabul edilebilir performans ve kontrol edilebilir bir bellek tüketimini verir çünkü

Ben 2 farklı veri yapıları bu yaklaşımı gibi - benim laptop etrafında 500.000 önbellek eklemeler/önbellek boyutu 10.000 elemanları ile sn. Dictionary<TKey,TValue> sadece O verileri bulmak için kullanılan (1) ve O'da SortedSet<CacheItem> uçlar verileri (n günlük), O içinde lfuList.Min arayarak kaldırma elemanı bulmak (log n) ve (O de kullanımı sayımını artırmak için bir giriş bulmak log n). çözmek için nasıl

herhangi bir öneriniz bu açıktır. Farklı tasarımlar dahil olmak üzere herhangi bir fikri takdir edeceğim.

Answer 1

IEqualityComparer numaralı telefondan IComparer uygulamak, eşit olmayan bir öğenin diğer öğeden daha büyük veya daha küçük olup olmadığını bilmenin bir yolu yoktur.

Size IComparer 'ın kimlik doğrultusunda bir karma kodu oluşturmak için hiçbir yolu yoktur gibi bir IComparer bir IEqualityComparer uygulamak mümkün değildir.

Bu durumda, sizin durumunuzda her iki türdeki karşılaştırmaya sahip olmanıza gerek yoktur. LRU hesaplanırken, bir öğenin birincil karşılaştırıcı olarak kullanılmasından beri geçen süreyi karşılaştırıyorsunuz ve daha sonra karşılaştırma yapıcıya dayalı olarak bir karşılaştırıcı olarak karşılaştırıyorsunuz. Sadece son parçayı kaldır; , numaralı bir izleme aracına sahip değil. En son kullanılanlar için bir kravat olduğunda önbelleğin hangi öğenin kaldırılacağını tanımlayalım. Bunu yaptığınızda, sadece, IComparer'u kabul etmeniz gerekir.

benim yorumunda değinildiği üzere

Answer 2

, temel kullanım durumu için işler biraz daha basit hale getirebileceğini bir yardımcı yöntemini ekleyebilirsiniz:

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

ve bu gibi kullanabilirsiniz istiyorum:

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

Answer 3

Tamam, şimdi deneyin.

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

Bence o Add ve Touch benziyor, değil mi O (1) 'de olduğu: İşte LFU için Add ve Touch için bir uygulamasıdır?

Şu anda _first için herhangi bir kullanım durumu göremiyorum, ancak başka birinin buna ihtiyacı olabilir. Bir öğeyi kaldırmak için _last yeterli olmalıdır.

EDIT Bir MoveDown işlemine ihtiyacınız yoksa, tek bir bağlantılı liste de yapılacaktır. EDIT Tek bir bağlantılı liste işe yaramaz çünkü MoveUp, Prev işaretçisini değiştirmek için Next işaretçisine ihtiyaç duyuyor.