以下の更新 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を使用して、テスト用の入力単語リストを作成しました。
Comparer<string>.Defaultキー比較子としてまたはを使用して c# SortedList に各単語を挿入する場合、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)、問題はなくなります。これは比較の問題を示しているようですが、その理由はよくわかりません。
更新 セバスチャンが指摘したように、ここで説明されている問題は、.Net 3.5 および 3.5 クライアント プロファイルには現れません。.Net 4.0、4.0 クライアント、および 4.5 で実行されます。
さらに掘り下げた後、リストからソートされたキーを取得しArray.BinarySearchてそれらのキーを実行すると、 を使用して見つからない同じキーに対して負の (見つからない) 値も返されることに気付きましSortedList.ContainsKeyた。したがって、これはキーのソート順が正しくないことを示唆しています。
リストから既に並べ替えられたキーを取得しArray.Sort、出力の並べ替え順序を使用してそれらを並べ替えると、問題のあるキーとは異なります。
そのため、特定の配列のソート順が正しいかどうか (リストの比較演算子を使用して) をチェックする関数を追加し (つまり、前のキーは常に小さく、後続のキーは常に大きい)、次のように異なる単語への入力を制限しました。比較者。この関数を 3 つの異なる入力に適用しました (すべて同じ比較子を使用)。
- SortedList の Keys コレクション。
- これらのキーに対する Array.Sort の出力。
- ファイルからの入力に対する Array.Sort の出力。
(2) と (3) の出力は同一であり、(1) とは異なります。ただし、(2) と (3) の Array.Sort 出力で Array.BinarySearch を実行すると、同じキーが見つかりません (< 0 が返されます)。また、正しい並べ替え順序をチェックする関数は、3 つのケースすべてで、関連する問題のあるキーの並べ替え順序が正しくないことを示しています。
この時点で、信じられないほど愚かなことをしたことを願っています。簡単な説明があります。うまくいけば、誰かが私にそれを指摘することができます.
サンプル コードは、私の追加のトラブルシューティング実験で更新されています。出力のスクリーンショットはhttp://imgur.com/DU8SCsAにあります。
更新 2 OK、.Net 4.0 で導入された c# 文字列比較器に関する非常に深刻な問題のように思われる問題に絞り込みました。
要約すると、a1、a2、a3 の 3 つの値があるとします。あらゆる種類の並べ替えが正しく機能するためには、 ifa1 < a2とa2 < a3that が比較の一貫性を維持するために、結果として次のことも成り立つことが期待されますa1 < a3。
ただし、これは c# 文字列比較子には当てはまりません (少なくともComparer<string>.Defaultとの場合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);
}
}
この回避策の問題点は、たとえばStringComparer.InvariantCulture.
両方の比較子を使用して、指定された単語リストを 1000 回並べ替えるときにかかった時間:
StringComparer.InvariantCulture : 00:00:15.3120013
WorkAroundStringComparer : 00:01:35.8322409
したがって、マイクロソフトが再考するか、誰かが実行可能な代替案を知っていることを願っています. それ以外の場合、残っている唯一のオプションは、を使用してフォールバックすることStringComparer.Ordinalです。