Поиск начала строки в массиве в C #

Question

У меня есть список, содержащий много путей. У меня есть определенный путь, который я хочу проверить по этому списку, чтобы увидеть, есть ли какие-либо пути, которые используют этот путь, то есть:

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;
}

Answer 1

Путь самый быстрый , вероятно, с двоичным поиском:

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;
    }
}

Answer 2

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> есть подобные методы, и вы можете использовать анонимный метод.

Answer 3

Что мне интересно в этом относительно простом вопросе, так это количество «правильных» ответов, в зависимости от того, как вы определяете «самый быстрый».

• Если самый быстрый означает «наименее затратный», то метод двоичного поиска Марка звучит как ваш ответ.
• Если самый быстрый означает «самый быстрый для реализации», тогда уместен вызов метода Джона list.Any.
• Если самый быстрый означает «грубая сила», тогда вы можете захотеть распараллелить поиск. Это будет более затратным с точки зрения требуемой обработки, но может выполняться быстрее в зависимости от ресурсов вашего сервера. PLINQ дает вам хорошую отправную точку для этого.