在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中搜索数组中的字符串的开始＃

回答

相关问题