c# - Boyer-Moore可以使用C#吗？

Boyer-Moore可能是已知最快的非索引文本搜索算法。因此，我正在C#中为我的Black Belt Coder网站实现它。

我运行了它，与String.IndexOf()相比，它大致显示了预期的性能改进。但是，当我将StringComparison.Ordinal参数添加到IndexOf时，它的性能开始超过我的Boyer-Moore实现。有时，数量可观。

我想知道是否有人可以帮助我找出原因。我知道StringComparision.Ordinal为什么可以加快速度，但是怎么会比Boyer-Moore更快呢？是因为.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;
    }
}

编辑:我已经在http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore上发布了所有有关此问题的测试代码和结论。

最佳答案

根据我自己的测试和此处的评论，我得出的结论是，String.IndexOf()与StringComparision.Ordinal一起表现出色的原因是，该方法调用了非托管代码，可能使用了手动优化的汇编语言。

我已经运行了许多不同的测试，而且String.IndexOf()似乎比使用托管C#代码可以实现的速度更快。

如果有人感兴趣，我会写出我发现的所有内容，并在http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore上发布C#中的Boyer-Moore算法的几种变体。