CODEWITHSUNDEEP
c#searchtstringlist
M Krane
M Krane

Reputation: 169

c# - BinarySearch StringList with wildcard

I have a sorted StringList and wanted to replace

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

with a binarySearch, since the cardList ist rather large(~18k) and this search takes up around 80% of the time.

So I found the List.BinarySearch-Methode, but my problem is that the lines in the cardList look like this:

Brindle_Boar_(Magic_2012).c1p247924.prod

But I have no way to generate the c1p... , which is a problem cause the List.BinarySearch only finds exact matches.

How do I modify List.BinarySearch so that it finds a match if only a part of the string matches?

e. g. searching for Brindle_Boar_(Magic_2012) should return the position of Brindle_Boar_(Magic_2012).c1p247924.prod

Upvotes: 2

Views: 1441

Answers (3)

Vasea
Vasea

Reputation: 5333

You can take a look at the C5 Generic Collection Library (you can install it via NuGet also). Use the SortedArray(T) type for your collection. It provides a handful of methods that could prove useful. You can even query for ranges of items very efficiently.

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"));

The RageFrom... methods perform a binary search, find the first element greater than or equal to your argument, that returns an iterator from that position

Upvotes: 0

Stephen Cleary
Stephen Cleary

Reputation: 456457

List.BinarySearch will return the ones complement of the index of the next item larger than the request if an exact match is not found.

So, you can do it like this (assuming you'll never get an exact match):

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

var index = ~list.BinarySearch(key);
return index != list.Count && list[index].StartsWith(key);

Upvotes: 3

BrokenGlass
BrokenGlass

Reputation: 160882

BinarySearch() has an overload that takes an IComparer<T> has second parameter, implement a custom comparer and return 0 when you have a match within the string - you can use the same IndexOf() method there.

Edit:

Does a binary search make sense in your scenario? How do you determine that a certain item is "less" or "greater" than another item? Right now you only provide what would constitute a match. Only if you can answer this question, binary search applies in the first place.

Upvotes: 0

Related Questions