Бойер-Мур, вероятно, самый быстрый из известных алгоритмов неиндексированного текстового поиска. Поэтому я реализую его на C # для моего веб-сайта Black Belt Coder .
У меня он работал, и он показал примерно ожидаемое улучшение производительности по сравнению с String.IndexOf ()
. Однако, когда я добавил аргумент StringComparison.Ordinal
в IndexOf
, он начал превосходить мою реализацию Бойера-Мура. Иногда в значительной степени.
Интересно, может ли кто-нибудь помочь мне выяснить, почему. Я понимаю, почему 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); }
}
///
/// 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.
///
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;
}
}
РЕДАКТИРОВАТЬ: Я разместил весь свой тестовый код и выводы по этому вопросу на http: // www .blackbeltcoder.com / Статьи / алгоритмы / быстрый-текст-поиск-с-Бойером-Муром .