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

Вы можете взглянуть на 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... выполняют бинарный поиск, находят первый элемент, больший или равный вашему аргументу, который возвращает итератор из этой позиции

Answer 3

BinarySearch() имеет перегрузку, которая принимает IComparer<T> имеет второй параметр, реализует пользовательский компаратор и возвращает 0, когда у вас есть совпадение в строке - вы можете использовать тот же IndexOf() метод там.

Редактировать:

Имеет ли смысл двоичный поиск в вашем сценарии? Как вы определяете, что определенный предмет "меньше" или "больше", чем другой предмет? Прямо сейчас вы предоставляете только то, что будет соответствовать. Только если вы можете ответить на этот вопрос, бинарный поиск применяется в первую очередь.