2

ソートされた StringList があり、置き換えたい

foreach (string line3 in CardBase.cardList)
            if (line3.ToLower().IndexOf((cardName + Config.EditionShortToLong(edition)).ToLower()) >= 0)
            {
                return true;
            }

cardList はかなり大きく (~18k)、この検索は時間の約 80% を占めるため、binarySearch を使用します。

だから私は List.BinarySearch-Methode を見つけましたが、私の問題は cardList の行が次のようになっていることです:

Brindle_Boar_(Magic_2012).c1p247924.prod

しかし、私は c1p... を生成する方法がありません。これは List.BinarySearch が正確な一致しか見つけられない原因となる問題です。

文字列の一部のみが一致する場合に一致を見つけるように List.BinarySearch を変更するにはどうすればよいですか?

たとえば、Brindle_Boar_(Magic_2012) を検索すると、Brindle_Boar_(Magic_2012).c1p247924.prod の位置が返されます。

4

3 に答える 3

3

List.BinarySearch完全一致が見つからない場合、リクエストよりも大きい次のアイテムのインデックスの 1 の補数を返します。

したがって、次のようにすることができます (完全に一致することはないと仮定します) 。

var key = (cardName + Config.EditionShortToLong(edition)).ToLower();
var list = CardBase.cardList;

var index = ~list.BinarySearch(key);
return index != list.Count && list[index].StartsWith(key);
于 2011-07-29T17:52:50.380 に答える
0

BinarySearch()has 2 番目のパラメーターを取り、IComparer<T>カスタム比較子を実装し、文字列内で一致する場合は 0 を返すオーバーロードがIndexOf()あります。そこで同じメソッドを使用できます。

編集：

あなたのシナリオでは二分探索は理にかなっていますか? 特定のアイテムが別のアイテムよりも「小さい」または「大きい」と判断するにはどうすればよいでしょうか? 現在、一致を構成するもののみを提供しています。この質問に答えることができる場合にのみ、二分探索が最初に適用されます。

于 2011-07-29T17:52:49.750 に答える
0

C5 Generic Collection Libraryを見ることができます (NuGet 経由でもインストールできます)。コレクションには SortedArray(T) 型を使用します。これは、有用であると証明できるいくつかのメソッドを提供します。アイテムの範囲を非常に効率的に照会することもできます。

var data = new SortedArray<string>();

// query for first string greater than "Brindle_Boar_(Magic_2012)" an check if it starts 
// with "Brindle_Boar_(Magic_2012)"
var a = data.RangeFrom("Brindle_Boar_(Magic_2012)").FirstOrDefault();
return a.StartsWith("Brindle_Boar_(Magic_2012)");

// query for first 5 items that start with "Brindle_Boar"
var b = data.RangeFrom("string").Take(5).Where(s => s.StartsWith("Brindle_Boar"));

// query for all items that start with "Brindle_Boar" (provided only ascii chars)
var c = data.RangeFromTo("Brindle_Boar", "Brindle_Boar~").ToList()

// query for all items that start with "Brindle_Boar", iterates until first non-match
var d = data.RangeFrom("Brindle_Boar").TakeWhile(s => s.StartsWith("Brindle_Boar"));

RageFrom... メソッドはバイナリ検索を実行し、引数以上の最初の要素を見つけ、その位置から反復子を返します。

于 2011-07-29T20:01:02.887 に答える