有没有办法从IComparer派生IEqualityComparer？
TL; DR我正在寻找一种方法从IComparer<T>获取IEqualityComparer<T> ，无论哪个数据类型都是T ，如果T是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”和“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>类似的东西），它可能会更加严重。
这就是为什么我想在构造函数中只有一个比较参数，但这似乎不起作用。 我可以在IComparer<T>.Compare()帮助下创建IEqualityComparer<T>.Equals() ，但我坚持在IEqualityComparer<T>.GetHashCode() - 这是非常重要的，正如你所知。 如果我有权访问比较器的私有属性以检查它是否区分大小写，我将使用CompareInfo来获取哈希码。
我喜欢这种采用两种不同数据结构的方法，因为它给了我可接受的性能和可控制的内存消耗 - 在我的笔记本电脑中，缓存大小为10.000个元素，每秒增加500.000个缓存。 Dictionary<TKey,TValue>仅用于查找O（1）中的数据，并且SortedSet<CacheItem>在O（log n）中插入数据，通过调用O（log n）中的lfuList.Min找到要删除的元素，并查找在O（log n）中也增加使用计数的条目。
欢迎任何关于如何解决这个问题的建议。 我会欣赏任何想法，包括不同的设计。
从IEqualityComparer实现IComparer是不可能的，因为您无法知道不等项目是否大于或小于其他项目。
从IComparer实现IEqualityComparer是不可能的，因为您无法生成符合IComparer身份的哈希代码。
也就是说，你没有必要在你的情况下拥有两种类型的比较器。 计算LRU时，您将比较项目用作主要比较器的时间，然后根据传入的比较器作为决胜因素进行比较。 只要删除最后一部分; 没有决胜盘。 当最近最少使用的是一条平局时，让它定义哪个项目离开缓存。 当你这样做时，你只需要接受一个IEqualityComparer ，而不是一个IComparer 。
正如我在我的评论中暗示的那样，您可以添加一个帮助器方法，它可能会使一些基本用例变得更简单：
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);
好的，下次尝试。 这里是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应该足够了。
编辑如果你不需要MoveDown操作，单链表也会执行。 编辑没有一个单一的链表不会工作，因为MoveUp需要Next指针来改变它的Prev指针。
上一篇: Is there a way to derive IEqualityComparer from IComparer?