Бойер-Мур Практика в C #? - PullRequest
Новая
       12

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

29 голосов
/ 05 февраля 2011

Бойер-Мур, вероятно, самый быстрый из неиндексированных алгоритмов поиска текста.Поэтому я внедряю его в 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); }
}

/// <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.

Ответы [ 2 ]

19 голосов
/ 07 февраля 2011

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

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

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

4 голосов
/ 05 февраля 2011

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

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

...