在C中搜索數組中的字符串的開始＃

我有一個包含很多路徑的列表。我有我要覈對這份清單，看看是否有任何路徑有使用此路徑的具體路徑，即：在C中搜索數組中的字符串的開始＃

f.StartsWith(r.FILENAME) && f != r.FILENAME

什麼是這樣做的最快的方法？

編輯：從下面的答案功能齊全：

static bool ContainsFragment(string[] paths, string fragment) 
{ 
    // paths **must** be pre-sorted via Array.Sort(paths); 
    if (paths.Length == 0) return false; 
    int index = Array.BinarySearch(paths, fragment); 
    if (index >= 0 && index+1 < paths.Length) 
    { //we found it 
     if (paths[index + 1].StartsWith(fragment) && 
      paths[index + 1].EndsWith(".manifest")) 
     { 
      return true; 
     } 
    } 
    return false; 
}

來源

2009-02-12 devzero

（注意我更新了您的意見） – 2009-02-12 12:45:53

的最快方式可能是與二進制搜索：

static bool ContainsFragment(string[] paths, string fragment) 
{ 
    // paths **must** be pre-sorted via Array.Sort(paths); 
    if (paths.Length == 0) return false; 
    int index = Array.BinarySearch(paths, fragment); 
    // we want the index of the *next highest* path 
    if (index < 0) { // no match 
     index = ~index; 
    } else { // exact match 
     index++; // for strict substring (non-equal) 
    } 
    return index < paths.Length && paths[index].StartsWith(fragment); 
}

但排序陣列的成本將超過任何好處，如果你只做了幾次;在這種情況下，只需掃描陣列 - 無論是使用LINQ等等，或者只是：

bool found = false; 
for(int i = 0 ; i < paths.Length ; i++) { 
    if(paths[i].StartsWith(fragment) && 
      paths[i].Length != fragment.Length) 
    { 
     found = true; 
     break; 
    } 
}

來源

2009-02-12 11:45:55

支票將從50000到幾十萬次完成，所以這種支付方式是有益的。我想要的是，如果有任何不匹配的匹配（總會有一個完全匹配），但是匹配始於相同但不完全相同。 – devzero 2009-02-12 12:34:40

我仍然覺得這不是最快的方式，因爲我相信我們仍然在循環陣列，直到我們找到我們想要的比賽。 – devzero 2009-02-12 12:39:43

不，二進制搜索不會循環 - 它減半。所以它會以15個步驟搜索50000。我懷疑（因爲總會有一個完全匹配），您還需要在比賽結束後檢查* next *項目... – 2009-02-12 12:41:32

var matches = list.Where(f => f.StartsWith(r.FILENAME) && f != r.FILENAME);

或者，如果你只關心是否存在：

bool any = list.Any(f => f.StartsWith(r.FILENAME) && f != r.FILENAME);

這是你使用的假設。毫無疑問，NET 3.5是這樣的 - 否則在List<T>中有類似的方法，你可以使用匿名方法。

來源

2009-02-12 11:45:56

我對這個相對簡單的問題感興趣的是「有效」答案的數量，具體取決於您如何定義「最快」。

如果最快意味着「成本最低」，那麼Marc的二進制搜索方法聽起來就像是您的答案。
如果最快的意思是「最快實施」，那麼Jon的list.Any方法調用是適當的。
如果最快的意思是「蠻力」，那麼你可能想看看並行搜索。就處理需求而言，成本會更高，但根據您的服務器資源可能執行得更快。 PLINQ爲您提供了一個很好的起點。

來源

2009-02-12 13:23:57

在C中搜索數組中的字符串的開始＃

回答

相關問題