c# - 带通配符的 BinarySearch StringList

Question

我有一个排序的 StringList 并想

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

用二进制搜索替换，因为 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 的位置

Answer 1

如果未找到精确匹配，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);

Answer 2

BinarySearch() 具有一个重载，它采用具有第二个参数的 IComparer，实现自定义比较器并在字符串中有匹配项时返回 0 - 您可以使用那里有相同的 IndexOf() 方法。

编辑：

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

Answer 3

您可以查看 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... 方法执行二分搜索，找到第一个大于或等于您的参数的元素，该元素从该位置返回一个迭代器