Как работает String.Contains?

Question

Можно создать дубликат:
What algorithm .Net use for searching a pattern in a string?

У меня есть цикл в моей программе, которая получает строку из файла. Затем происходит проверка на содержит ли строка в строку

if(line.Contains("String")) 
{ 
    //Do other stuff 
} 

Есть более 2 миллионов строк в файле, так что если я могу ускорить скорость, даже 1/10 мс, то это позволит сэкономить мне в течение 3 минут каждый бег.

Итак ... Скажите, что линия длинна 1000 символов, быстрее ли искать короткую или длинную строку или это не имеет значения?

line.Contains("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); 

или

line.Contains("ABCDEFG") 

Спасибо заранее.

Answer 1

String.Contains() следует мучительному маршруту через System.Globalization.CompareInfo в CLR и подсистему поддержки NLS, где я полностью потерялся. Это содержит высоко оптимизированный код с впечатляющим перфомансом. Единственный способ сделать это быстрее через pinvoking стандартную функцию CRT wcsstr, доступный в msvcrt.dll

[DllImport("msvcrt.dll", CharSet = CharSet.Unicode)] 
    private static extern IntPtr wcsstr(string toSearch, string toFind); 

возвращает IntPtr.Zero, если строка не найдена. Я сделал некоторые измерения, используя String.IndexOf() вместо Contains(), чтобы проверить различные варианты сравнения строк. Все время в наносекундах, поиск строки из 7 символов в строке из 60 символов. При использовании строки, не показанной таким худшим случаем.Использовали низкий время из образца 20:

StringComparison.Ordinal (same as Contains) : 245 nanoseconds 
StringComparison.OrdinalIgnoreCase : 327 
StringComparison.InvariantCulture : 251 
StringComparison.InvariantCultureIgnoreCase : 327 
StringComparison.CurrentCulture : 275 
StringComparison.CurrentCultureIgnoreCase : 340 
wcsstr : 213 

Очень впечатляющие цифры и на одном уровне с тем, что вы ожидали бы, что эти функции требуют. Функция wcsstr() выполняет такое же порядковое сравнение, как String.Compare(). Это на 13% быстрее, статистически незначительное улучшение, учитывая, что реальный перфомант вряд ли приблизится к этим измерениям из-за влияния локализации кэша процессора. Я могу только сделать вывод, что вы так быстро, как можете ожидать. Независимо от того, стоит ли небольшое улучшение от wcsstr, это зависит от вас.

Answer 2

«Как правило, алгоритм становится быстрее, так как ключ разыскивается становится больше»

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Answer 3

Метод String.Contains возвращает истину, если и только если эта строка содержит заданную последовательность значений гольцов.

Он в основном используется для проверки подстроки внутри строки.

http://csharp.net-informations.com/string/csharp-string-contains.htm

Answer 4

Если .NET String.Contains использует Boyer-Moore algorithm это быстрее искать более длинную строку.

Могу ли я предположить, что если вы читаете файл с разделителями, например, каждая строка представляет собой серию текстовых полей, разделенных запятыми, что вы можете сохранить некоторое время поиска, не выполнив поиск в позиции 0 в строке, если вы знаете, что это может например, перед символом 40.

Общепринято разделить строку, используя функцию String Spilled на символе разделителя, это возвращает массив строк. Затем вы будете искать только в пределах поля, где может отображаться значение. Это тоже будет быстрее.

Answer 5

Contains, как и все методы поиска строк (я думаю), в конечном итоге приводит к внешнему методу InternalFindNLSStringEx - что бы это ни было, это довольно сложно.

Answer 6

Когда дело доходит до повышения производительности, вы хотите убедиться, что то, что вы намерены улучшить, на самом деле является причиной узкого места. Я бы начал с профилирования производительности различных частей в моем коде и определения того, какая часть представляет наибольшее узкое место.

На первый взгляд, я вижу три основные составляющие этого процесса, которые стоит профилирование:

• Перебор всего содержимого файла (это может быть или может не включать в файл ввода-вывода соображения, которые вы, возможно, пожелают для проверки отдельно).
• Отметьте String.Contains() для каждой строки в файле.
• «Do Stuff», когда есть матч

Хотя есть большие коммерческие профайлеры там, вы можете начать с помощью простого таймера (например System.Diagnostics.Stopwatch) в вашем коде, или, если этот процесс действительно долго, просто используйте часы для измерения времени.

Измерьте время каждого из следующих действий.

1. Измерьте время, затраченное на простое просмотрение всего файла без каких-либо действий. Это изолирует ваш цикл и код ввода-вывода, чтобы вы могли видеть, насколько хорошо он работает.
2. Затем добавьте только сравнение строк (String.Contains) и измерьте общее время, затрачиваемое на это добавление.
3. Наконец, добавьте код «do stuff» и измерьте общее время с добавлением.

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

Test   Total Time Cost (Difference) 
============================================= 
Do Nothing  0s   0s 
Loop Only  100s   100s 
Add Comparison 105s   5s 
Add Do Stuff 130s   25s 

Глядя на эти (фальшивые) чисел, самая дорогая часть процесса является цикл и IO-код, так что там я бы начать, чтобы попытаться увеличить представление. Поскольку часть «Do Stuff» добавила 25 секунд к общему времени выполнения, я бы взглянул на этот код, чтобы увидеть, есть ли что-нибудь, что я мог бы улучшить. Наконец, я бы посмотрел на сравнение строк.

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

Answer 7

К моему удивлению, скомпилированный Regex на самом деле намного, намного быстрее, чем Contains. Конечно, стоимость компиляции стоит того, если вы будете искать одну и ту же строку несколько раз. Но если так, то это более чем в два раза быстрее.Попробуйте сами:

static void Test() 
{ 
    var random = new Random(10); 

    var alphabet = "abcdefghijklmnopqrstuvwxyz"; 
    var content = new String((from x in Enumerable.Range(0, 10000000) 
          select a[random.Next(0, a.Length)]).ToArray()); 

    var searchString = content.Substring(5000000, 4096); 

    var regex = new Regex(searchString); 

    var sw = Stopwatch.StartNew(); 
    for (int i = 0; i < 1000; i++) 
    { 
    if (!regex.IsMatch(content)) 
    { 
     throw new Exception(); 
    } 
    } 

    sw.Stop(); 
    Console.WriteLine("Regex: " + sw.Elapsed); 
    sw.Restart(); 

    for (int i = 0; i < 1000; i++) 
    { 
    if (!content.Contains(searchString)) 
    { 
     throw new Exception(); 
    } 
    } 
    sw.Stop(); 
    Console.WriteLine("String.Contains: " + sw.Elapsed); 

} 

Я до сих пор не понял, как это может быть так быстро, глядя на скомпилированной сборки, что это затемненный беспорядок switch заявления. Но это быстро, действительно быстро.