Is there a way to get IEqualityComparer from IComparer?

Question

TL DR I'm looking for a way to get IEqualityComparer<T> from IComparer<T> , no matter what data type T , including case-insensitive options if T is a string . Or I need another solution for this problem.

Here's the full story: I implement a simple shared cache with LFU policy. The requirement is that it should be possible to choose whether the cache is case sensitive or case insensitive - if string is a data type for cache keys (which is optional). In the solution, I primarily develop the cache, I expect hundreds of billions of cache requests and cache sizes of not more than 100,000 entries. Because of these numbers, I immediately refused to use any string manipulation that causes the selection (e.g. .ToLower().GetHashCode() , etc.) and instead chose to use IComparer and IEqualityComparer , since they are standard BCL functions . The user of this cache can pass comparisons with the constructor. Here are the relevant code snippets:

 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 my problem { // ... entries = new Dictionary<TKey, CacheItem>(keyEqualityComparer); lfuList = new SortedSet<CacheItem>(new CacheItemComparer(keyComparer)); } // ... } 

keyEqualityComparer used to manage cache entries (for example, the "ABC" and "abc" keys are equal if the user wants). keyComparer used to manage cache items sorted by UseCount , so it’s easy to select the least frequently used (implemented in the CacheItemComparer class).

An example of proper use with custom mapping:

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

(This looks silly, but StringComparer implements both IComparer<string> and IEqualityComparer<string> ). The problem is that if the user gives incompatible mappings (i.e., case insensitivity keyEqualityComparer and case sensitivity keyComparer ), then the most likely result is invalid LFU statistics and, as a result, lower cache level. Another scenario is also less than desired. In addition, if the key is more complex (I will have something similar to Tuple<string,DateTime,DateTime> ), you can spoil it more seriously.

This is why I would like to have only one comparison argument in the constructor, but this does not seem to work. I can create IEqualityComparer<T>.Equals() using IComparer<T>.Compare() , but I'm stuck in IEqualityComparer<T>.GetHashCode() - this is very important, as you know. If I had access to private comparison properties to check if it is case sensitive or not, I would use CompareInfo to get the hash code.

I like this approach with two different data structures because it gives me acceptable performance and controlled memory consumption - on my laptop about 500,000 cache additions / sec with a cache size of 10.000. Dictionary<TKey,TValue> used only to search for data in O (1), and SortedSet<CacheItem> inserts data into O (log n), finds the element to delete, calling lfuList.Min in O (log n), and finds the entry to increase use count also in O (log n).

Any suggestions on how to solve this problem are welcome. I will be grateful for any ideas, including various projects.

Answer 1

It is not possible to implement IComparer from IEqualityComparer because you have no way of knowing more or less unequal element than another element.

It is not possible to implement IEqualityComparer from IComparer , since you cannot generate a hash code that matches the value of IComparer .

However, you do not need to have both types of comparisons in your case. When calculating the LRU, you compare the time elapsed since the element was used as the primary comparison, and then compared on the basis of the one passed in the comparator as a tie-break. Just delete this last part; do not have a tie-break. Let it be undefined, whose element goes out of the cache when there is a connection for the last use. When you do this, you need to accept IEqualityComparer , not IComparer .

Answer 2

As I mentioned in my comment, you can add a helper method that can make things a little easier for the basic use case:

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

and you will use it as follows:

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

Answer 3

OK, give it a try. The following is the implementation for Add and Touch for 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; } } } 

In my opinion, Add and Touch seem to be in O (1), right?

Currently, I don't see any use case for _first , but maybe someone else needs it. To remove the _last element should be enough.

EDIT One linked list will also work if you do not need the MoveDown operation. EDIT No linked list will work because MoveUp needs a Next pointer to change the Prev pointer.