c# - 使用 IComparer<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

当比较任意项时，比如 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);
  }