6

检查下面的更新 3 我发现我遇到的问题与 .Net 4.0、4.0 客户端和 4.5 的 c# 字符串比较器的已知严重问题有关，这将导致字符串列表的排序顺序不一致（导致输出依赖关于输入的顺序和使用的排序算法）。该问题已于 2012 年 12 月报告给 Microsoft，并以“无法修复”的形式关闭。可以使用一种变通方法，但是速度要慢得多，以至于对于大型集合几乎不实用。

在实现不可变的 PatriciaTrie 时，我想将其性能与 System.Collections.Generic.SortedList 进行比较。我使用以下文件https://github.com/rkapsi/patricia-trie/blob/master/src/test/resources/org/ardverk/collection/hamlet.txt来创建用于测试的输入词表。

在 c# SortedList 中插入每个单词时，使用Comparer<string>.Default或StringComparer.InvariantCulture作为键比较器，无法使用正常搜索方法检索成功插入的许多条目（例如ContainsKey返回 false），但键在列表中显示为通过迭代列表来观察。

更奇怪的是，比较器在将从排序列表中检索到的键与使用找不到的搜索键进行比较时返回值“0” ContainsKey。

下面的完整示例演示了我的系统上的这个问题。

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        // the problem is possibly related to comparison.
        var fail = true;
        var comparer = fail ? StringComparer.InvariantCulture : StringComparer.Ordinal;

        // read hamlet (contains duplicate words)
        var words = File
            .ReadAllLines("hamlet.txt")
            .SelectMany(l => l.Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries))
            .Select(w => w.Trim())
            .Where(w => !string.IsNullOrEmpty(w))
            .Distinct(comparer)
            .ToArray();

        // insert hamlet's words in the sorted list.
        var list = new SortedList<string, int>(comparer);
        var ndx = 0;
        foreach (var word in words)
            list[word] = ndx++;

        // search for each of the added words.
        foreach (var keyToSearch in words)
        {
            if (!list.ContainsKey(keyToSearch))
            {
                // was inserted, but cannot be retrieved.
                Console.WriteLine("Error - Key not found: \"{0}\"", keyToSearch);
                // however when we iterate over the list, we see that the entry is present
                var prefix = keyToSearch.Substring(0, Math.Min(keyToSearch.Length, 3));
                foreach (var wordCloseToSearchKey in list.Keys.Where(s => s.StartsWith(prefix)))
                {
                    // and using the SortedList's supplied comparison returns 0, signaling equality
                    var comparisonResult = list.Comparer.Compare(wordCloseToSearchKey, keyToSearch);
                    Console.WriteLine("{0} - comparison result = {1}", wordCloseToSearchKey, comparisonResult);
                }
            }
        }

        // Check that sort order of List.Keys is correct 
        var keys = list.Keys.ToArray();
        BinarySearchAll("list.Keys", keys, list.Comparer);
        CheckCorrectSortOrder("list.Keys", keys, list.Comparer);

        // Check that sort order of Array.Sort(List.Keys) is correct 
        var arraySortedKeys = CopySortSearchAndCheck("Array.Sort(List.Keys)", keys, list.Comparer);

        // Check that sort order of the Array.Sort(input words) is correct 
        var sortedInput = CopySortSearchAndCheck("Array.Sort(input words)", words, list.Comparer);

        Console.ReadLine();
    }

    static string[] CopySortSearchAndCheck(string arrayDesc, string[] input, IComparer<string> comparer)
    {
        // copy input
        var sortedInput = new string[input.Length];
        Array.Copy(input, sortedInput, sortedInput.Length);

        // sort it
        Array.Sort(sortedInput, comparer);

        // check that we can actually find the keys in the array using bin. search
        BinarySearchAll(arrayDesc, sortedInput, comparer);

        // check that sort order is correct
        CheckCorrectSortOrder(arrayDesc, sortedInput, comparer);

        return sortedInput;
    }

    static void BinarySearchAll(string arrayDesc, string[] sortedInput, IComparer<string> comparer)
    {
        // check that each key in the input can be found using bin. search
        foreach (var word in sortedInput)
        {
            var ix = Array.BinarySearch(sortedInput, word, comparer);
            if (ix < 0)
                // and it appears it cannot!
                Console.WriteLine("Error - {0} - Key not found: \"{1}\"", arrayDesc, word);
        }
    }

    static void CheckCorrectSortOrder(string arrayDesc, string[] sortedKeys, IComparer<string> comparer)
    {
        for (int n = 0; n < sortedKeys.Length; n++)
        {
            for (int up = n + 1; up < sortedKeys.Length; up++)
            {
                var cmp = comparer.Compare(sortedKeys[n], sortedKeys[up]);
                if (cmp >= 0)
                {
                    Console.WriteLine(
                        "{0}[{1}] = \"{2}\" not < than {0}[{3}] = \"{4}\"  - cmp = {5}",
                        arrayDesc, n, sortedKeys[n], up, sortedKeys[up], cmp);
                }
            }
            for (int down = n - 1; down > 0; down--)
            {
                var cmp = comparer.Compare(sortedKeys[n], sortedKeys[down]);
                if (cmp <= 0)
                {
                    Console.WriteLine(
                        "{0}[{1}] = \"{2}\" not > than {0}[{3}] = \"{4}\"  - cmp = {5}",
                        arrayDesc, n, sortedKeys[n], down, sortedKeys[down], cmp);
                }
            }
        }
    }
}

有人对这种意外和奇怪的行为有解释吗？

当将 SortedList 使用的比较器更改为StringComparer.Ordinal（例如通过在上面的示例中更改fail为false）时，问题消失了，这似乎指向一个比较问题，但我不太明白为什么。

已更新 正如 Sébastien 所指出的，此处描述的问题并未出现在 .Net 3.5 和 3.5 客户端配置文件中。它适用于 .Net 4.0、4.0 客户端和 4.5。

经过更多的挖掘，我注意到如果我从列表中获取排序的键并Array.BinarySearch在这些键上运行，它还会为使用SortedList.ContainsKey. 因此，这表明键的排序顺序不正确。

如果我从列表中取出已经排序的键并使用Array.Sort输出的排序顺序对它们进行排序，那么对于有问题的键来说是不同的。

所以我添加了一个函数来检查（使用列表的比较器）给定数组的排序顺序是否正确（即前面的键总是较小，后面的键总是较大）并将输入限制为根据不同的单词比较器。我将此函数应用于 3 个不同的输入（全部使用相同的比较器）：

  1. SortedList 的 Keys 集合。
  2. Array.Sort 在这些键上的输出。
  3. Array.Sort 对文件输入的输出。

(2) 和 (3) 的输出与 (1) 相同但不同。但是，在 (2) 和 (3) 的 Array.Sort 输出上再次执行 Array.BinarySearch 无法找到相同的键（返回 < 0）。此外，检查正确排序顺序的功能表明，对于所有 3 种情况，所涉及的有问题键的排序顺序都不正确。

在这一点上，我只是希望我做了一些非常愚蠢的事情，并且有一个简单的解释。希望有人可以向我指出这一点。

示例代码通过我的其他故障排除实验进行了更新，输出的屏幕截图可以在这里找到http://imgur.com/DU8SCsA。

更新 2 好的，我已将问题缩小到对我来说似乎是从 .Net 4.0 开始引入的 c# 字符串比较器的一个非常严重的问题。

总之，假设我们有 3 个值：a1、a2 和 a3。为了使任何类型的排序正常工作，我们希望 ifa1 < a2和a2 < a3that 为了比较一致，因此以下也成立a1 < a3：

然而，c# 字符串比较器并非如此（至少对于Comparer<string>.Defaultand而言StringComparer.InvariantCulture）。

下面的小程序说明了这个确切的问题：

class Program
{
    static void Main(string[] args)
    {
        var comparer = StringComparer.InvariantCulture;
        var a1 = "A";
        var a2 = "a\'";
        var a3 = "\'a";
        PrintComparison("a1", a1, "a2", a2, comparer);
        PrintComparison("a2", a2, "a3", a3, comparer);
        PrintComparison("a1", a1, "a3", a3, comparer);
        Console.ReadLine();
    }
    public static void PrintComparison(string firstSymbol, string first, string secondSymbol, string second, IComparer<string> comparer)
    {
        var cmp = comparer.Compare(first, second);
        var result = cmp == 0 ? "=" : cmp < 0 ? "<" : ">";
        Console.WriteLine("{0} {1} {2}   ({3} {1} {4})", firstSymbol, result, secondSymbol, first, second);
    }
}

这是它的输出：

a1 < a2   (A < a')
a2 < a3   (a' < 'a)
a1 > a3   (A > 'a)

结论似乎是依赖使用 c# 字符串比较器确定的排序顺序是不安全的，还是我遗漏了什么？

更新 3 这个问题似乎已于 2012 年 12 月向 MS 报告，并以“不会修复”状态关闭，这相当令人失望；请参阅下面评论中发布的链接（由于我的声誉点有限，我似乎无法在此处发布）。这还列出了一个解决方法，我已经实现并使用它来验证这确实解决了使用标准比较器观察到的问题。

public class WorkAroundStringComparer : StringComparer
{
    private static readonly Func<CompareInfo, string, CompareOptions, int> _getHashCodeOfString;
    private readonly CompareInfo _compareInfo;
    private readonly CompareOptions _compareOptions;

    static WorkAroundStringComparer()
    {
        // Need this internal method to compute hashcode
        // as an IEqualityComparer implementation.
        _getHashCodeOfString = BuildGetHashCodeOfStringDelegate();
    }

    static Func<CompareInfo, string, CompareOptions, int> BuildGetHashCodeOfStringDelegate()
    {
        var compareInfoType = typeof(CompareInfo);
        var argTypes = new[] { typeof(string), typeof(CompareOptions) };
        var flags = BindingFlags.NonPublic | BindingFlags.Instance;
        var methods = compareInfoType.GetMethods(flags).ToArray(); ;
        var method = compareInfoType.GetMethod("GetHashCodeOfString", flags, null, argTypes, null);

        var instance = Expression.Parameter(compareInfoType, "instance");
        var stringArg = Expression.Parameter(typeof(string), "string");
        var optionsArg = Expression.Parameter(typeof(CompareOptions), "options");
        var methodCall = Expression.Call(instance, method, stringArg, optionsArg);
        var expr = Expression.Lambda<Func<CompareInfo, string, CompareOptions, int>>(methodCall, instance, stringArg, optionsArg);
        return expr.Compile();
    }

    public WorkAroundStringComparer()
        : this(CultureInfo.InvariantCulture)
    {
    }

    public WorkAroundStringComparer(CultureInfo cultureInfo, CompareOptions compareOptions = CompareOptions.None)
    {
        if (cultureInfo == null)
            throw new ArgumentNullException("cultureInfo");
        this._compareInfo = cultureInfo.CompareInfo;
        this._compareOptions = compareOptions;
    }

    public override int Compare(string x, string y)
    {
        if (ReferenceEquals(x, y))
            return 0;
        if (ReferenceEquals(x, null))
            return -1;
        if (ReferenceEquals(y, null))
            return 1;

        var sortKeyFor_x = _compareInfo.GetSortKey(x, _compareOptions);
        var sortKeyFor_y = _compareInfo.GetSortKey(y, _compareOptions);
        return SortKey.Compare(sortKeyFor_x, sortKeyFor_y);
    }

    public override bool Equals(string x, string y)
    {
        return Compare(x, y) == 0;
    }

    public override int GetHashCode(string obj)
    {
        return _getHashCodeOfString(_compareInfo, obj, _compareOptions);
    }
}

这种解决方法的问题在于，它对于相当大的集合几乎不实用，因为它比 eg 慢一个数量级StringComparer.InvariantCulture。

使用两个比较器对给定单词列表进行 1000 次排序所花费的时间：

StringComparer.InvariantCulture : 00:00:15.3120013
WorkAroundStringComparer        : 00:01:35.8322409

所以我仍然希望微软重新考虑或有人知道一个可行的替代方案。否则，剩下的唯一选择就是重新使用StringComparer.Ordinal.

4

1 回答 1

3

它可能与.Net Framework 4/4.5有关吗？我已经将您的示例改编为 .Net 3.5，如下所示：

var words = ReadFile("hamlet.txt");

//...

private static string[] ReadFile(string path)
{
    List<string> lines = new List<string>();
    using (StreamReader sr = new StreamReader(path))
    {
        string text = sr.ReadToEnd();
        lines.Add(text);
    }

    return lines.SelectMany(l => l.Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).Select(w => w.Trim()))
        .Where(w => !(w.ToCharArray().All(c => c == ' ')))
        .ToArray();
}

并且两个比较器都可以在使用 .Net 3.5 的 XP 上正常工作。

于 2013-07-11T18:09:00.297 回答