Inverse String.Replace - более быстрый способ сделать это?

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();
    }

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

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.Compiled, чтобы быть справедливым:

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

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

Answer 1

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

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

Answer 2

Хорошо, для строки ~ 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 3

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

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 4

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

    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), почему у вас нет сигнатуры метода:

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

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

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). Кажется, вы заменяете все алфавиты и пробелы на *, почему бы просто не проверить, является ли текущий символ алфавитом / пробелом, и заменить его?