Бойер-Мур Практический в C#?

Question

Boyer-Moore, вероятно, самый быстрый неиндексированный алгоритм поиска текста. Поэтому я реализую его на C# для моего сайта Black Belt Coder.

У меня было это работает, и он показал примерно ожидаемые улучшения производительности по сравнению с String.IndexOf(). Однако, когда я добавил аргумент StringComparison.Ordinal в IndexOf, он начал превосходить мою реализацию Boyer-Moore. Иногда, на значительную сумму.

Интересно, может ли кто-нибудь помочь мне понять, почему. Я понимаю, почему StringComparision.Ordinal может ускорить процесс, но как это может быть быстрее, чем Бойер-Мур? Это из-за накладных расходов самой платформы .NET, возможно, потому, что индексы массива должны быть проверены, чтобы убедиться, что они находятся в зоне действия, или что-то еще в целом. Некоторые алгоритмы просто не практичны в C# .NET?

Ниже приведен код ключа.

// Base for search classes 
abstract class SearchBase 
{ 
    public const int InvalidIndex = -1; 
    protected string _pattern; 
    public SearchBase(string pattern) { _pattern = pattern; } 
    public abstract int Search(string text, int startIndex); 
    public int Search(string text) { return Search(text, 0); } 
} 

/// <summary> 
/// A simplified Boyer-Moore implementation. 
/// 
/// Note: Uses a single skip array, which uses more memory than needed and 
/// may not be large enough. Will be replaced with multi-stage table. 
/// </summary> 
class BoyerMoore2 : SearchBase 
{ 
    private byte[] _skipArray; 

    public BoyerMoore2(string pattern) 
     : base(pattern) 
    { 
     // TODO: To be replaced with multi-stage table 
     _skipArray = new byte[0x10000]; 

     for (int i = 0; i < _skipArray.Length; i++) 
      _skipArray[i] = (byte)_pattern.Length; 
     for (int i = 0; i < _pattern.Length - 1; i++) 
      _skipArray[_pattern[i]] = (byte)(_pattern.Length - i - 1); 
    } 

    public override int Search(string text, int startIndex) 
    { 
     int i = startIndex; 

     // Loop while there's still room for search term 
     while (i <= (text.Length - _pattern.Length)) 
     { 
      // Look if we have a match at this position 
      int j = _pattern.Length - 1; 
      while (j >= 0 && _pattern[j] == text[i + j]) 
       j--; 

      if (j < 0) 
      { 
       // Match found 
       return i; 
      } 

      // Advance to next comparision 
      i += Math.Max(_skipArray[text[i + j]] - _pattern.Length + 1 + j, 1); 
     } 
     // No match found 
     return InvalidIndex; 
    } 
} 

EDIT: Я отправил все мой тестовый код и выводы по этому вопросу на http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore.

Answer 1

Основываясь на моих собственных тестах и ​​замечаниях, сделанных здесь, я пришел к выводу, что причина, по которой String.IndexOf() так хорошо работает с StringComparision.Ordinal, связана с тем, что метод вызывает неуправляемый код, который, вероятно, использует язык ассемблера, оптимизированный вручную.

Я провел несколько различных тестов, и String.IndexOf() просто кажется быстрее, чем все, что я могу реализовать, используя управляемый код C#.

Если кому-то интересно, я написал все, что я об этом узнал, и опубликовал несколько вариантов алгоритма Бойера-Мура в C# по адресу http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore.

Answer 2

Моя ставка заключается в том, что установка этого флага позволяет String.IndexOf использовать сам Бойер-Мур. И его реализация лучше, чем ваша.

Без этого флага необходимо быть осторожным, используя Boyer-Moore (и, вероятно, нет) из-за потенциальных проблем вокруг Unicode. В частности, возможность Unicode вызывает таблицы переходов, которые использует Бойер-Мур, чтобы взорваться.