C＃ - 二分查找的StringList通配符

我有一個排序的StringList，想用的binarySearch更換C＃ - 二分查找的StringList通配符

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

，因爲cardList IST相當大的（〜18K）和本次搜索佔據了大約80％的時間。

所以我找到了List.BinarySearch-了Methode，但我的問題是，在cardList的線條看起來像這樣：

Brindle_Boar_(Magic_2012).c1p247924.prod

但是我沒有辦法生成C1P ......，這是導致List.BinarySearch只能找到完全匹配的問題。

如何修改List.BinarySearch，以便在只匹配部分字符串時找到匹配項？

e。 G。搜索Brindle_Boar_（Magic_2012）應返回Brindle_Boar_（Magic_2012）的位置.c1p247924.prod

來源

2011-07-29 M Krane

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-29 17:52:50

謝謝，這完美的作品。 –

這對於StartsWith搜索大字符串（或甚至數據，如果您在某些類上實現IComparable）集合絕對完美。只要做'var from = list.BinarySearch（str）; var to = list.BinarySearch（str + char.MaxValue）;'然後如果index小於零，則應用'〜'（並且爲'to'索引減1）。不知道'BinarySearch'這樣酷炫的功能。 – steavy

BinarySearch()有一個重載接受一個IComparer<T>有第二個參數，實現自定義比較，並返回0，當你有內匹配字符串 - 您可以在那裏使用相同的IndexOf()方法。

編輯：

做一個二進制搜索道理在你的情況？你如何確定某個項目比另一個項目「更少」或「更大」？現在你只能提供構成比賽的東西。只有您可以回答這個問題，二進制搜索才適用。

來源

2011-07-29 17:52:49 BrokenGlass

我想知道是否原始排序如果可能被打破你爲了比較的目的而丟棄了cp1部分，也就是說，你可以在取出cp1之後得到不同的順序嗎？在這種情況下，你可能會得到錯誤的否定。 –

@chibacity：再次查看問題，我認爲字符串匹配只有在匹配從索引0開始時纔有意義 - 否則您是正確的，它會導致不同的隱式順序，從而破壞二進制搜索。話雖如此，我會使用'StartsWith（）'而不是'IndexOf（）' – BrokenGlass

你可以看看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-29 20:01:02 Vasea

C＃ - 二分查找的StringList通配符

回答

相關問題