Какой метод поиска строк наиболее эффективен (время чтения)? (С #)

Question

Я обнаружил, что моя программа просматривает множество длинных строк (более 20 000), пытаясь найти конкретную уникальную фразу.

Какой самый эффективный метод для этого в C #?

Ниже приведен текущий код, который работает следующим образом:

1. Поиск начинается в startPos, поскольку целевая область несколько удалена от начала
2. Он перебирает строку, на каждом шаге он проверяет, начинается ли подстрока из этой точки с startMatchString, которая является индикатором того, что было найдено начало целевой строки. (Длина строки назначения варьируется).
3. Отсюда он создает новую подстроку (отсекает 11 символов, которые отмечают начало целевой строки) и ищет endMatchString

Я уже знаю, что это ужасно сложный и, возможно, очень неэффективный алгоритм. Как лучше достичь того же результата?

string result = string.Empty;    
for (int i = startPos; i <= response.Length - 1; i++)
{
   if (response.Substring(i).StartsWith(startMatchString))
   {
       string result = response.Substring(i).Substring(11);
       for (int j = 0; j <= result.Length - 1; j++)
       {
           if (result.Substring(j).StartsWith(endMatchString))
           {
               return result.Remove(j)
           }
       }
   }
}
return result;

Answer 1

Вы можете использовать String.IndexOf, но убедитесь, что вы используете StringComparison.Ordinal, иначе он может быть на порядок медленнее.

private string Search2(int startPos, string startMatchString, string endMatchString, string response) {
    int startMarch = response.IndexOf(startMatchString, startPos, StringComparison.Ordinal);
    if (startMarch != -1) {
        startMarch += startMatchString.Length;
        int endMatch = response.IndexOf(endMatchString, startMarch, StringComparison.Ordinal);
        if (endMatch != -1) { return response.Substring(startMarch, endMatch - startMarch); }
    }
    return string.Empty;
}

Поиск 1000 раз строки в 40% файла размером 183 КБ занял около 270 миллисекунд. Без StringComparison.Ordinal это заняло около 2000 миллисекунд.
Поиск 1 раз с вашим методом занял более 60 секунд, так как он создает новую строку (O (n)) каждую итерацию, делая ваш метод O (n ^ 2).

Answer 2

Есть целая куча алгоритмов,

• Бойер и Мур
• воскресенье
• Кнут-Морриса-Пратта
• Рабина-Карпа

Я бы порекомендовал использовать упрощенный Бойер-Мур, называемый Бойер-Мур-Хорспул.

C-код появляется в википедии. Для кода Java посмотрите на

http://www.fmi.uni -sofia.bg / FMI / логика / vboutchkova / источники / BoyerMoore_java.html

Хорошая статья об этом доступна в http://www.ibm.com/developerworks/java/library/j-text-searching.html

Если вы хотите использовать встроенный материал, переходите к регулярным выражениям.

Answer 3

Это зависит от того, что вы пытаетесь найти в строке. Если вы ищете определенную последовательность, IndexOf/Contains быстрая, но если вы ищете шаблоны с подстановочными знаками, Regex оптимизирован для такого поиска

Answer 4

Я бы попытался использовать Регулярное выражение вместо того, чтобы использовать собственный алгоритм поиска строк. Вы можете предварительно скомпилировать регулярное выражение, чтобы оно работало быстрее.

Answer 5

Вот пример использования IndexOf ( остерегайтесь : написано от макушки головы, не проверял):

int skip = 11;
int start = response.IndexOf(startMatchString, startPos);
if (start >= 0)
{
   int end = response.IndexOf(startMatchString, start + skip);
   if (end >= 0)
       return response.Substring(start + skip, end - start - skip);
   else
       return response.Substring(start + skip);
}
return string.Empty;

Answer 6

Как уже говорилось, регулярное выражение - ваш друг. Вы можете посмотреть на RegularExpressions.Group. Таким образом, вы можете назвать часть совпавшего набора результатов.

Вот пример

Answer 7

Для очень длинных строк вы не можете превзойти алгоритм поиска Бойера-Мура. Это более сложно, чем я мог бы попытаться объяснить здесь, но на сайте CodeProject есть довольно хорошая статья.

Answer 8

Вы можете использовать регулярное выражение; он оптимизирован для такого рода поиска и манипулирования.

Вы также можете попробовать IndexOf ...

string result = string.Empty;

if (startPos >= response.Length) 
    return result;

int startingIndex = response.IndexOf(startMatchString, startPos);
int rightOfStartIndex = startingIndex + startMatchString.Length;

if (startingIndex > -1 && rightOfStartIndex < response.Length)
{
    int endingIndex = response.IndexOf(endMatchString, rightOfStartIndex);
    if (endingIndex > -1)
        result = response.Substring(rightOfStartIndex, endingIndex - rightOfStartIndex);
}

return result;