有没有一种方法可以从IComparer派生出IEqualityComparer？

Question

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

我喜欢这种使用2个不同数据结构的方法，因为它给我可接受的性能和可控的内存消耗——在我的笔记本电脑上，缓存大小为10,000个元素时，每秒大约可以添加约500,000个缓存。 Dictionary<TKey,TValue>仅用于以O（1）找到数据，而SortedSet<CacheItem>则以O（log n）插入数据，通过调用lfuList.Min在O（log n）中查找要删除的元素，并在O（log n）中找到要增加使用计数的条目。

欢迎任何解决此问题的建议。我会赞赏任何想法，包括不同的设计。

- Endrju

---

一种可能性是使用通用约束来定义一个静态工厂方法，该方法接受一个实现了 IEqualityComparer<T> 和 IComparer<T> 的单个比较器参数。这样，至少您不必将同一对象传递给两个不同的参数。 - Mike Zboray

当然。请看我的回答。 - Mike Zboray

我认为值得检查一下是否可以自己实现SortedSet。如果你增加了UseCount，那么这个集合中只会向上改变一个位置。也许有O(1)的触摸实现。插入应该是O(1)，因为它被添加到列表的末尾（也许SortedSet会这样做）。我将尝试一个新的示例实现。 - Sebastian Schumann

@Verarind 是的，内置的SortedSet是基于红黑树的野兽，非常强大，所有操作都是O(log n)。但正如我在下面指出的那样，在我的使用情况下，LFU的效果比LRU还要差（这是违反直觉的）。因此，我可能会将其留下来，稍微有些不完美，但是实现起来可行，并按照您建议的使用链表进行LRU操作。 - Endrju

有一个看起来很有趣的 - http://dhruvbird.com/lfu.pdf - Endrju

Answer 1

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

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

也就是说，在您的情况下不需要同时具有这两种类型的比较器。在计算 LRU 时，您将时间自上次使用以来作为主要比较器进行比较，并根据传入的比较器作为淘汰者进行比较。只需删除最后一部分；没有淘汰者。当最近使用的项目并列时，让它未定义哪个项目离开缓存即可。这样做，您只需要接受一个 IEqualityComparer，而不是一个 IComparer。

- Servy

---

@Verarind 我并不建议 OP 改变他的解决方案。他似乎已经有了一个工作的解决方案，其中他有一个并排的字典和排序集合，使用字典进行查找，使用排序集合确定要删除的项目。排序集合中的项具有一个键作为属性，可以用来在字典中查找该项，如果这是你所问的。 - Servy

@Servy 我了解。他有一个需要 IComparer 的解决方案。你告诉他改变并使用 TimeStamp 作为排序集合。是的，你没有要求他完全更改。他的解决方案还需要 O(log n) 来触碰一个元素。为什么不完全改为在每种情况下都可以在 O(1) 中工作且不需要任何 UseCount 的解决方案呢？他还说不同的设计也受欢迎。 - Sebastian Schumann

@Verarind 不，我告诉他的只是不要使用实际对象的比较来决定应该删除哪个项目的平局解决方法，并且他应该让平局发生。如果他的解决方案在这个改变后是好的，那太好了；在这里没有其他事情要做。如果他的整个解决方案除了有这个问题之外，还太慢，那么这是一个完全不同的问题，与所提出的问题完全无关。他似乎觉得代码的其余部分工作得很好，所以如果确实如此，我认为没有必要重新编写整个代码。 - Servy

哦，是的。我也误读了LFU中的F。我的回答只针对LRU。抱歉。 - Sebastian Schumann

@Servy 我不需要落下物体的绑定，我只需要完全比较来能够将所有项存储在SortedSet中。 - Endrju

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

- Mike Zboray

---

即使在这种特定情况下比较器恰好实现了 IEqualityComparer 和 IComparer 接口，也并不意味着这将始终如此。针对所有其他情况，他都需要创建一个新类来包装他拥有的两个比较器，然后该类需要确保这两个比较器共享一个唯一标识符。这或多或少只是把问题推到其他地方，而不是解决它。 - Servy

@Servy OP要求与我的评论相关的代码，但是评论区太长了。我同意，这只是让OP更简单地完成任务而已。对于这种情况，我可能会保留具有两个比较器的构造函数。一般来说，甚至不能保证GetHashCode和Equals在IEqualityComparer<T>中实现的一致性，更不用说与某些IComparer<T>一致了。这就是为什么我们需要代码审查和自动化测试的原因。 - Mike Zboray

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

- Sebastian Schumann

---

好的，我更新了Add并添加了RemoveLast。这将说明它是如何工作的。 - Sebastian Schumann

看了一下TryMoveUp()，我觉得里面肯定有个循环。比如说，如果我们有这样的条目：使用次数分别为3、2、2、2、2、2、1，而最右边的“2”被触碰，所以它的使用次数变成了3，那么它应该向左移动4次。否则，列表中最常用的项就不会靠近顶部。因此，这是唯一一个时间复杂度为O(n)的地方。 - Endrju

是的，我几分钟前意识到了。我的假设有误。可能会有多个MoveUp！如果所有“n”条目具有相同的“UseCount”，则最后一个项目必须向上移动到第一个位置，这是O（n）操作。抱歉。这种实现在最好的情况下为O（1），但在最坏的情况下为O（n）。不知道使用最坏情况下为O（log n）的SortedSet还是您找到的文档会更好。对此我感到很抱歉。 - Sebastian Schumann

我认为最好的方法是我提供链接的那篇论文中的方法。无论我们现在是否能够做出完美的解决方案，我认为这个案例非常有趣。我学到了LFU缓存有自己的问题，并且它很难被正确地实现。对于我目前的用例，我将回归LRU。感谢您在此方面的帮助。 - Endrju

我读了你提供的那篇论文，非常有趣。基本思想可能与我所想的相同。他们使用了两个双向链表——一个用于UseCount，另一个用于相同UseCount的项目。使用这种方法，在UseCount列表中只有一个“MoveUp”，旧列表中有一个删除操作和新列表中的一个添加操作。听起来非常简单和直接。非常好的论文。我为找到它给予了赞誉。也许有时我会需要它（希望我能记得这个主题）。 - Sebastian Schumann

Answer 4

在构造函数中，你可以尝试使用一个 IComparer 和一个定义了 GetHashCode() 的 lambda 表达式代替一个 IEqualityComparer 和一个 IComparer。然后基于 IComparer==0 和 GetHashCode() = lambda 构建一个 IEqualityComparer。

虽然我认为这是微不足道的，但当 IComparer 返回 0 时，仍然存在获取 HashCode 不匹配的风险。如果你想让你的代码的用户更加清晰明了，你可以通过在构造函数中使用两个 lambda 表达式来扩展该策略：Func<T,T,int> 用于 IComparer 和 IEqualityComparer，以及 Func<T,int> 用于 GetHashCode。

- Ama