使用 Comparer<string> 对 16 个元素进行排序至少进行 100000 次比较

Question

当我尝试使用 IComparer<string> 排序时，至少需要 100000 次比较。

为什么？

public class PeriodComparer: IComparer<string>
{
  int num = 0;

  public int Compare(string x, string y)
  {
    var year1 = int.Parse(x.Substring(2));
    var year2 = int.Parse(y.Substring(2));

    if (year1 < year2)
        return -1;

    if (year1 > year2)
        return 1;

    var season1 = x.Substring(0, 2);

    return season1 == "VT" ? -1 : 1;
  }
}

我试着用它对字符串数组进行排序

var strings = new []
    {"VT2010", "HT2010",
    "VT2011", "HT2011",
    "VT2012", "HT2012",
    "VT2013", "HT2013",
    "VT2014", "HT2014",
    "VT2015", "HT2015",
    "VT2016", "HT2016",
    "VT2017", "HT2017"};


var comparer = new PeriodComparer();
var orderedPeriodNames = strings.OrderBy(x => x, comparer).ToList();

期望字符串首先根据年份排序，然后根据 VT 和 HT 排序。（这意味着此特定情况下的输入已经排序）。

但是，执行停滞了，所以我在那个比较函数中放了一个计数器，比如

public class PeriodComparer: IComparer<string>
{
  int num = 0;

  public int Compare(string x, string y)
  {
    if (++num >= 100000)
    {
      // setting a breakpoint here
    }

    var year1 = int.Parse(x.Substring(2));
    var year2 = int.Parse(y.Substring(2));

    if (year1 < year2)
        return -1;

    if (year1 > year2)
        return 1;

    var season1 = x.Substring(0, 2);

    return season1 == "VT" ? -1 : 1;
  }
}

已命中断点，因此似乎至少需要 100000 次比较。

Answer 1

您不适合 'tie-breaker' 比较（子字符串 "VT" 与 "HT"）相同的情况。

Answer 2

如果您向比较器添加调试语句并仅在两个字符串上调用它，您就可以看到发生了什么。

你得到这个输出：

Comparing VT2010 to VT2010
Comparing VT2010 to HT2010
Comparing VT2010 to VT2010

一遍又一遍地重复。显然它无法弄清楚 VT2010 在结果中应该放在哪里，因为每次它认为它找到了正确的位置并进行了最后的比较，结果证明它太靠右了，因为仍然 VT2010 < VT2010.

正确 ,

Note that the comparer can be called for two equal items.

如果添加行

if(x == y) { return 0; }

在 Compare 方法的顶部，排序算法将能够计算出 VT2010 与 VT2010 和 HT2010 相比的正确相对顺序。

Answer 3

您的季节比较可能需要一些调整。类似于：

public class PeriodComparer : IComparer<string>
{
    int num = 0;

    public int Compare(string x, string y)
    {
        if (++num >= 100000)
        {
            Console.WriteLine(num);
        }

        var year1 = int.Parse(x.Substring(2));
        var year2 = int.Parse(y.Substring(2));

        if (year1 < year2)
            return -1;

        if (year1 > year2)
            return 1;

        var season1 = x.Substring(0, 2);
        var season2 = y.Substring(0, 2);

        if (season1 == "VT" && season2 != "VT")
            return -1;
        if (season2 == "VT" && season1 != "VT")
            return 1;

        return StringComparer.InvariantCulture.Compare(season1, season2);
    }
}

这将确保排序结果一致。

要进行比较，请使用 "HJ2014" 和 "HT2014" 的输入调用现有代码。它将 return 1. 现在用 "HT2014" 和 "HJ2014" 调用它 - 现在它将 still return 1. 这是出乎意料的。

你基本上说：

"HJ2014" is greater than "HT2014"

和

"HJ2014" is less than "HT2014"

显然，两者都不可能是真的。因此这个 "confuses" 排序算法，并使其旋转它的轮子。

同样，您的代码也会声明：

"VT2014" is less than "VT2014"

这显然是错误的。这会导致问题，因为 OrderBy 在幕后使用 QuickSort，从而可以将条目与其自身进行比较。

Answer 4

当比较任意项目时，说 A 和 B 我们必须确保

  A == A
  ...
  whenever A > B then B < A

请注意，在您的情况下，这些规则已被破坏；此外，你从不威胁字符串相等；简单的例子

  var A = "VT2018";

  // Expected 0, Actual -1
  int result = (new PeriodComparer()).Compare(A, A);

正确准确（处理public 类时我们必须期待任何输入）实现：

  public int Compare(string x, string y) {
    // Special cases: equal strings, nulls
    if (string.Equals(x, y))
      return 0;
    else if (string.Equals(null, x))  // null is smaller than any string
      return -1;
    else if (string.Equals(null, y)) 
      return 1;

    // Suffixes
    // TrimStart('0'): we want "0003" == "3" < "10":  
    string suffixX = x.Length <= 2 ? "" : x.Substring(2).TrimStart('0');
    string suffixY = y.Length <= 2 ? "" : y.Substring(2).TrimStart('0');

    // Natural order: Length first (2000 > 900)...
    if (suffixX.Length > suffixY.Length)
      return 1;
    else if (suffixX.Length < suffixY.Length)
      return -1;

    // ...Lexicograhical next: 2040 > 2030
    int result = string.Compare(suffixX, suffixY);

    if (result != 0)
      return result;

    // Equal Suffixes; compare prefixes
    string prefixX = x.Length <= 2 ? x : x.Substring(0, 2);
    string prefixY = y.Length <= 2 ? y : y.Substring(0, 2);

    if (prefixX == "VT" && prefixY != "VT")
      return -1;
    else if (prefixY == "VT" && prefixX != "VT")
      return 1;

    return string.Compare(prefixX, prefixY);
  }

使用 Comparer<string> 对 16 个元素进行排序至少进行 100000 次比较

Sorting 16 elements with IComparer<string> does at least 100000 comparisions

c#

sorting

icomparer