Обратная строка.Заменить - более быстрый способ сделать это?

Question

У меня есть метод для замены всех символов, кроме тех, которые я указываю.Например,

ReplaceNot("test. stop; or, not", ".;/\\".ToCharArray(), '*'); 

вернулся бы

"****.*****;***,****".

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

    public static string ReplaceNot(this string original, char[] pattern, char replacement)
    {           
        int index = 0;
        int old = -1;

        StringBuilder sb = new StringBuilder(original.Length);

        while ((index = original.IndexOfAny(pattern, index)) > -1)
        {
            sb.Append(new string(replacement, index - old - 1));
            sb.Append(original[index]);
            old = index++;
        }

        if (original.Length - old > 1)
        {
            sb.Append(new string(replacement, original.Length - (old + 1)));
        }

        return sb.ToString();
    }

Финальный номер.Я также добавил тестовый пример для строки из 3 тысяч символов, выполненный со скоростью 100 тысяч раз вместо 1 миллиона, чтобы увидеть, насколько хорошо каждый из этих показателей масштабируется.Единственным сюрпризом было то, что регулярное выражение "масштабировалось лучше", чем другие, но это не помогает, поскольку изначально оно работает очень медленно:

User            Short * 1M  Long * 100K     Scale
John            319             2125            6.66
Luke            360             2659            7.39
Guffa           409             2827            6.91
Mine            447             3372            7.54
DirkGently      1094            9134            8.35
Michael         1591            12785           8.04
Peter           21106           94386           4.47

Обновить:Я сделал создание регулярного выражения для версии Питера статической переменной и установил для нее значение RegexOptions .Скомпилировано, чтобы быть справедливым:

User            Short * 1M      Long * 100K     Scale
Peter           8997            74715           8.30

Вставьте ссылку на мой тестовый код, пожалуйста, поправьте меня, если это неправильно: http://pastebin.com/f64f260ee

Answer 1

Хорошо, для строки ~ 60 КБ это будет работать примерно на 40% быстрее, чем ваша версия:

public static string ReplaceNot(this string original, char[] pattern, char replacement)
{
    int index = 0;

    StringBuilder sb = new StringBuilder(new string(replacement, original.Length));

    while ((index = original.IndexOfAny(pattern, index)) > -1)
    {
        sb[index] = original[index++];
    }

    return sb.ToString();
}

Хитрость заключается в том, чтобы инициализировать новую строку со всеми заменяющими символами, поскольку большинство из них будут заменены.

Answer 2

Разве вы не можете использовать Regex.Replace так:

Regex regex = new Regex(@"[^.;/\\]");
string s = regex.Replace("test. stop; or, not", "*");

Answer 3

Я не знаю, будет ли это быстрее, но при этом не нужно обновлять строки, чтобы их можно было добавить в построитель строк, что может помочь:

    public static string ReplaceNot(this string original, char[] pattern, char replacement)
    {
        StringBuilder sb = new StringBuilder(original.Length);

        foreach (char ch in original) {
            if (Array.IndexOf( pattern, ch) >= 0) {
                sb.Append( ch);
            }
            else {
                sb.Append( replacement);
            }
        }

        return sb.ToString();
    }

Если число символов в pattern будет любого размера (который, как я предполагаю, обычно не будет), возможно, стоит заплатить, чтобы отсортировать его и выполнить Array.BinarySearch () вместо Array.indexOf () .

Для такого простого преобразования я бы поспорил, что у него также не будет проблем с тем, чтобы быть быстрее, чем регулярное выражение.

Кроме того, поскольку ваш набор символов в pattern обычно в любом случае происходит из строки (по крайней мере, это был мой общий опыт работы с этим типом API), почему у вас нет подпись метода be:

public static string ReplaceNot(this string original, string pattern, char replacement)

или, еще лучше, есть перегрузка, где pattern может быть char [] или string ?

Answer 4

Вот еще одна версия для вас. Мои тесты показывают, что его производительность довольно хорошая.

public static string ReplaceNot(
    this string original, char[] pattern, char replacement)
{
    char[] buffer = new char[original.Length];

    for (int i = 0; i < buffer.Length; i++)
    {
        bool replace = true;

        for (int j = 0; j < pattern.Length; j++)
        {
            if (original[i] == pattern[j])
            {
                replace = false;
                break;
            }
        }

        buffer[i] = replace ? replacement : original[i];
    }

    return new string(buffer);
}

Answer 5

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

sb.Append(new string(replacement, index - old - 1));

с:

sb.Append(replacement, index - old - 1);

и это:

sb.Append(new string(replacement, original.Length - (old + 1)));

с:

sb.Append(replacement, original.Length - (old + 1));

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

Answer 6

Это будет O (n). Кажется, вы заменяете все алфавиты и пробелы на * , почему бы просто не проверить, является ли текущий символ алфавитом / пробелом, и заменить его?