Linq ThenBy 运行无限时间

Question

我有一个函数，目的是以易于理解的方式打印出频繁项集的字典。目标是首先按照字典键的大小排序，然后按数字列表的词典顺序排序。问题在于ThenBy语句中的注释"hello"会无限打印。如果我更改ThenBy以不使用比较器而仅使用另一个int或string值，则可以正常工作，因此我显然做错了什么。

public static void printItemSets(Dictionary<List<int>, int> freqItemSet)
{
    List<KeyValuePair<List<int>, int>> printList = freqItemSet.ToList();
    printList = printList.OrderBy(x => x.Key.Count)
                         .ThenBy(x => x.Key, new ListComparer())
                         .ToList();
}

的代码如下：

public class ListComparer: IEqualityComparer<List<int>>, IComparer<List<int>>
{
    public int Compare(List<int> a, List<int> b)
    {
        int larger = a.Count > b.Count ? 1: -1;
        for (int i = 0; i < a.Count && i < b.Count; i++)
        {
            if (a[i] < b[i])
            {
                return -1;
            }
            else if (a[i] > b[i])
            {
                return 1;
            }
            else { }
        }
        return larger;
    }
}

非常简单的测试案例：

int[] a = {1, 3, 5};
int[] b = { 2, 3, 5 };
int[] c = { 1, 2, 3, 5 };
int[] d = { 2, 5 };
int[] e = { 1, 3, 4 };
List<int> aL = a.ToList<int>();
List<int> bL = b.ToList<int>();
List<int> cL = c.ToList<int>();
List<int> dL = d.ToList<int>();
List<int> eL = e.ToList<int>();
Dictionary<List<int>, int> test = new Dictionary<List<int>, int>(new ListComparer());
test.Add(aL, 1);
test.Add(bL, 1);
test.Add(cL, 1);
test.Add(dL, 1);
test.Add(eL, 1);

- Daniel Cappuccio

---

看起来它应该最终终止。但是它似乎有可能特别慢。你尝试过将其作为单元测试运行吗？你尝试过使用只有几个元素的模拟字典来确保代码按预期工作吗？ - Yuck

我目前正在使用仅有4个项目的字典进行测试，所以应该足够小。由于它只是一个打印函数，而且我不期望有异常大的列表，所以可能还可以。我主要处于“草稿”模式，只是试图编写出能够正确工作的东西。 - Daniel Cappuccio

你的比较器没有处理相等的项。如果这些项是相等的，那么它们的顺序决定哪个被认为是“更大”的，因此比较器不是“自反”的。这是排序算法所依赖的一个属性。第一行应该是var larger = a.Count.CompareTo(b.Count);。话虽如此，这并不会导致你看到的问题。 - Servy

由于项目来自字典，因此不可能存在两个相等的列表。尽管如此，我可以将该检查放入比较函数中。 - Daniel Cappuccio

@DanielCappuccio 如果相等的语义不同，列表可能是相等的，而它们很可能确实不同。不能保证字典使用与您的方法相同的相等比较器。实际上，排序将使用IComparer，而Dictionary将使用IEqualityComparer。由于这些方法不同，它们将被不同地实现。您不能同时使用单个方法来处理两者。 - Servy

Answer 1

问题在于ListComparer没有检查数组是否相同。 相同的数组被传入两次作为x和y。 检查x和y是否相等将解决您的问题。

- TyCobb

Answer 2

您的比较器不能处理相等的项。如果这些项相等，则两个项的顺序决定哪个被视为“更大”。因此，比较器不是“自反”的。排序算法依赖于自反性质。

第一行应该改为var larger = a.Count.CompareTo(b.Count);，这样真正相等的列表将返回0，而不是-1或1。

- Servy