आईसीओएमपीएयर से आईक्वालिटी कॉम्पियर प्राप्त करने का कोई तरीका है?

Question

टी एल; डॉ मैं एक तरह से IComparer<T> से IEqualityComparer<T> प्राप्त करने के लिए के लिए देख रहा हूँ, कोई फर्क नहीं पड़ता जो डेटाप्रकार T, केस-संवेदी विकल्प अगर Tstring है भी शामिल है। या मुझे इस समस्या के लिए एक अलग समाधान की जरूरत है।

यहां पूरी कहानी है: मैं एलएफयू नीति के साथ सरल, सामान्य कैश लागू कर रहा हूं। आवश्यकता यह है कि यह चुनना संभव है कि कैश केस संवेदनशील हो या केस असंवेदनशील हो - यदि string कैश कुंजी के लिए डेटाटाइप होता है (जो आवश्यक नहीं है)। समाधान में मैं मुख्य रूप से कैश विकसित करता हूं, मुझे उम्मीद है कि सैकड़ों अरब कैश लुकअप, और अधिकतम 100,000 प्रविष्टियों के कैश आकार। उन संख्याओं के कारण मैंने तुरंत किसी स्ट्रिंग मैनिपुलेशन का उपयोग करने से इस्तीफा दे दिया जो आवंटन (जैसे .ToLower().GetHashCode() इत्यादि) का कारण बनता है और इसके बजाय IComparer और IEqualityComparer का उपयोग करने का विकल्प चुना गया है, क्योंकि वे मानक बीसीएल विशेषताएं हैं। इस कैश का उपयोगकर्ता तुलनाकर्ताओं को कन्स्ट्रक्टर को पास कर सकता है। यहाँ कोड के प्रासंगिक टुकड़े कर रहे हैं:

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> लागू करता है।) समस्या यह है कि उपयोगकर्ता असंगत comparers देता है (यानी केस संवेदी keyEqualityComparer और केस संवेदी keyComparer), तो सबसे संभावित परिणाम अमान्य एलएफयू आंकड़े हैं, और इस प्रकार कम कैश हिट सबसे अच्छा है। अन्य परिदृश्य वांछित से भी कम है। इसके अलावा यदि कुंजी अधिक परिष्कृत है (मेरे पास Tuple<string,DateTime,DateTime> जैसा कुछ होगा), तो इसे अधिक गंभीरता से गड़बड़ करना संभव है।

यही कारण है कि मैं केवल निर्माता में एक तुलनात्मक तर्क करना चाहता हूं, लेकिन ऐसा लगता है कि यह काम नहीं करता है। मैं IComparer<T>.Compare() की सहायता से IEqualityComparer<T>.Equals() बनाने में सक्षम हूं, लेकिन मैं IEqualityComparer<T>.GetHashCode() पर फंस गया हूं - जो आपको पता है, यह बहुत महत्वपूर्ण है। अगर मुझे तुलनात्मक के निजी गुणों तक पहुंच प्राप्त हो, तो यह जांचने के लिए कि क्या यह केस संवेदनशील है या नहीं, तो मैंने हैश कोड प्राप्त करने के लिए CompareInfo का उपयोग किया होगा।

मुझे 2 अलग-अलग डेटा संरचनाओं के साथ इस दृष्टिकोण को पसंद है, क्योंकि यह मुझे अपने लैपटॉप पर 500,000 कैश जोड़/सेकंड कैश आकार 10.000 तत्वों के साथ स्वीकार्य प्रदर्शन और नियंत्रित मेमोरी खपत देता है। Dictionary<TKey,TValue> का उपयोग ओ (1), और SortedSet<CacheItem> में डेटा खोजने के लिए किया जाता है ओ (लॉग एन) में डेटा सम्मिलित करता है, ओ (लॉग एन) में lfuList.Min पर कॉल करके निकालने के लिए तत्व ढूंढें, और ओ में वृद्धि वृद्धि गणना में प्रवेश प्राप्त करें (लॉग एन)।

इसका समाधान करने के तरीके पर कोई सुझाव स्वागत है। मैं विभिन्न डिजाइनों सहित किसी भी विचार की सराहना करूंगा।

Answer 1

को IEqualityComparer से लागू करना संभव नहीं है क्योंकि आपके पास यह जानने का कोई तरीका नहीं है कि असमान आइटम अन्य आइटम से अधिक या उससे कम है या नहीं।

यह वहाँ आप एक हैश कोड IComparer की पहचान के साथ कतार में है कि उत्पन्न करने के लिए के लिए कोई रास्ता नहीं है के रूप में एक IComparer से एक IEqualityComparer लागू करने के लिए संभव नहीं है।

उस ने कहा, आपके मामले में दोनों प्रकार के तुलनाकर्ता होने की आवश्यकता नहीं है। एलआरयू की गणना करते समय आप उस समय की तुलना कर रहे हैं जब किसी आइटम को प्राथमिक तुलनाकर्ता के रूप में उपयोग किया गया था और फिर एक टिब्रेकर के रूप में तुलना में पारित होने के आधार पर तुलना करना। बस उस अंतिम भाग को हटा दें; में कोई tiebreaker नहीं है। कम से कम हाल ही में उपयोग किए जाने के लिए टाई होने पर यह आइटम कैश छोड़ देता है। जब आप ऐसा करते हैं तो आपको केवल IEqualityComparer स्वीकार करना होगा, IComparer नहीं।

Answer 2

जैसा कि मैंने मेरी टिप्पणी में alluded, आप एक सहायक विधि है कि एक बुनियादी उपयोग के मामले के लिए चीजों को एक छोटे से सरल बना सकता है जोड़ सकते हैं:

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

ठीक है अगला प्रयास करें।

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 की तरह लग रहा हे (1) में है, हैं ना: यहाँ LFU के लिए Add और Touch के लिए एक कार्यान्वयन है?

वर्तमान में मुझे _first के लिए कोई उपयोग केस नहीं दिख रहा है लेकिन शायद किसी और को इसकी आवश्यकता है। किसी आइटम को हटाने के लिए _last पर्याप्त होना चाहिए।

EDIT यदि आपको मूवडाउन ऑपरेशन की आवश्यकता नहीं है तो एक सिंगल लिंक्ड सूची भी होगी। EDIT कोई एकल लिंक नहीं की गई सूची काम नहीं करेगी क्योंकि MoveUp को Prev पॉइंटर बदलने के लिए Next सूचक की आवश्यकता है।