2

我有一个排序的 StringList 并想替换

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

使用 binarySearch，因为 cardList 相当大（~18k），这个搜索占用了大约 80% 的时间。

所以我找到了 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如果未找到完全匹配，将返回比请求大的下一个项目的索引的补码。

所以，你可以这样做（假设你永远不会得到完全匹配）：

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()有一个IComparer<T>带有第二个参数的重载，实现一个自定义比较器并在字符串中有匹配项时返回 0 - 您可以在IndexOf()那里使用相同的方法。

编辑：

二进制搜索在您的场景中有意义吗？您如何确定某个项目比另一个项目“小”或“大”？现在，您只提供构成匹配的内容。只有你能回答这个问题，二分搜索才适用。

于 2011-07-29T17:52:49.750 回答
0

您可以查看C5 通用集合库（您也可以通过 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 回答