有没有办法从 IComparer 派生 IEqualityComparer？

Question

TL;DR 我正在寻找一种从 IComparer<T> 获取 IEqualityComparer<T> 的方法，无论哪种数据类型是 T，包括不区分大小写的选项，如果 T 是 string。或者我需要一个不同的解决方案来解决这个问题。

全文如下：我正在使用 LFU 策略实现简单的通用缓存。要求是必须可以 select 缓存是区分大小写还是不区分大小写——如果 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 排序的缓存条目，因此很容易 select 最不常用的条目（在 CacheItemComparer class 中实现）。 =38=]

自定义比较的正确用法示例：

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 来获取哈希码。

我喜欢这种具有 2 种不同数据结构的方法，因为它为我提供了可接受的性能和可控的内存消耗——在我的笔记本电脑上大约有 500.000 个缓存 additions/sec，缓存大小为 10.000 个元素。 Dictionary<TKey,TValue>只是用来在O(1)中查找数据，而SortedSet<CacheItem>在O(log n)中插入数据，在O(log n)中调用lfuList.Min找到要删除的元素，并在 O(log n) 中找到增加使用计数的条目。

欢迎就如何解决这个问题提出任何建议。我将不胜感激任何想法，包括不同的设计。

Answer 1

无法从 IEqualityComparer 实现 IComparer，因为您无法知道不相等的项是大于还是小于另一项。

无法从 IComparer 实现 IEqualityComparer，因为您无法生成符合 IComparer 身份的哈希码。

也就是说，在您的情况下，您不需要同时拥有这两种类型的比较器。在计算 LRU 时，您正在比较自某个项目用作主要比较器以来的时间，然后根据传入的比较器作为决胜局进行比较。只需删除最后一部分； 没有决胜局。当最近最少使用的条目并列时，让哪个条目离开缓存是未定义的。当你这样做时，你只需要接受 IEqualityComparer，而不是 IComparer.

Answer 2

正如我在评论中提到的，您可以添加一个辅助方法，这可能会使基本用例的事情变得更简单：

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

好的，下次试试。这是 LFU 的 Add 和 Touch 的实现：

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 指针。

Answer 4

您可以尝试使用 IComparer 和定义 GetHashCode() 的 lambda，而不是在您的构造函数中使用 IEqualityComparer 和 IComparer。然后 build an IEqualityComparer 基于 if(IComparer==0) 和 GetHashCode() = lambda.

虽然我会说它很小，但是当 IComparer returns 0 时，你仍然有 HashCode 不匹配的风险。如果你想让代码的用户非常清楚，您始终可以通过在构造函数中采用两个 lambda 来扩展该策略：Func<T,T,int> 用于 IComparer 和 IEqualityComparer，Func<T,int> 用于 GetHashCode.

有没有办法从 IComparer 派生 IEqualityComparer？

Is there a way to derive IEqualityComparer from IComparer?

c#

iequalitycomparer

icomparer

memorycache