Как превзойти эту замену регулярных выражений?

Question

После значительных измерений я обнаружил горячую точку в одной из наших служб Windows, которую я хотел бы оптимизировать. Мы обрабатываем строки, в которых может быть несколько последовательных пробелов, и мы хотели бы сократить их до одних пробелов. Для этой задачи мы используем статическое скомпилированное регулярное выражение:

private static readonly Regex 
    regex_select_all_multiple_whitespace_chars = 
        new Regex(@"\s+",RegexOptions.Compiled);

, а затем используйте его следующим образом:

var cleanString=
    regex_select_all_multiple_whitespace_chars.Replace(dirtyString.Trim(), " ");

Эта строка вызывается несколько миллионов раз и оказывается довольно интенсивной. Я пытался написать что-то лучше, но я в тупике. Учитывая довольно скромные требования к обработке регулярных выражений, наверняка есть что-то более быстрое. Может ли unsafe обработка с указателями ускорить процесс?

Edit:

Спасибо за удивительный набор ответов на этот вопрос ... самый неожиданный!

Answer 1

Это примерно в три раза быстрее:

private static string RemoveDuplicateSpaces(string text) {
  StringBuilder b = new StringBuilder(text.Length);
  bool space = false;
  foreach (char c in text) {
    if (c == ' ') {
      if (!space) b.Append(c);
      space = true;
    } else {
      b.Append(c);
      space = false;
    }
  }
  return b.ToString();
}

Answer 2

Как насчет этого ...

public string RemoveMultiSpace(string test)
{
var words = test.Split(new char[] { ' ' }, 
    StringSplitOptions.RemoveEmptyEntries);
return string.Join(" ", words);
}

Тестовый запуск с NUnit:
Время теста в миллисекундах.

Regex Test time: 338,8885
RemoveMultiSpace Test time: 78,9335

private static readonly Regex regex_select_all_multiple_whitespace_chars =
   new Regex(@"\s+", RegexOptions.Compiled);

[Test]
public void Test()
{
    string startString = "A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      ";
    string cleanString;
    Trace.WriteLine("Regex Test start");
    int count = 10000;
    Stopwatch timer = new Stopwatch();
    timer.Start();
    for (int i = 0; i < count; i++)
    {
        cleanString = regex_select_all_multiple_whitespace_chars.Replace(startString, " ");
    }
    var elapsed = timer.Elapsed;
    Trace.WriteLine("Regex Test end");
    Trace.WriteLine("Regex Test time: " + elapsed.TotalMilliseconds);

    Trace.WriteLine("RemoveMultiSpace Test start");
    timer = new Stopwatch();
    timer.Start();
    for (int i = 0; i < count; i++)
    {
        cleanString = RemoveMultiSpace(startString);
    }
    elapsed = timer.Elapsed;
    Trace.WriteLine("RemoveMultiSpace Test end");
    Trace.WriteLine("RemoveMultiSpace Test time: " + elapsed.TotalMilliseconds);
}

public string RemoveMultiSpace(string test)
{
    var words = test.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    return string.Join(" ", words);
}

Edit:
Сделал еще несколько тестов и добавил метод Guffa «RemoveDuplicateSpaces» на основе StringBuilder.
Поэтому я пришел к выводу, что метод StringBuilder быстрее при большом количестве пробелов, но с меньшим количеством пробелов метод разделения строк немного быстрее.

Cleaning file with about 30000 lines, 10 iterations
RegEx time elapsed: 608,0623
RemoveMultiSpace time elapsed: 239,2049
RemoveDuplicateSpaces time elapsed: 307,2044

Cleaning string, 10000 iterations:
A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      
RegEx time elapsed: 590,3626
RemoveMultiSpace time elapsed: 159,4547
RemoveDuplicateSpaces time elapsed: 137,6816

Cleaning string, 10000 iterations:
A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      
RegEx time elapsed: 290,5666
RemoveMultiSpace time elapsed: 64,6776
RemoveDuplicateSpaces time elapsed: 52,4732

Answer 3

В настоящее время вы заменяете один пробел другим пробелом. Попробуйте сопоставить \s{2,} (или что-то подобное, если вы хотите заменить отдельные символы новой строки и другие символы).

Answer 4

Мне любопытно, как может работать прямолинейная реализация:

    static string RemoveConsecutiveSpaces(string input)
    {
        bool whiteSpaceWritten = false;
        StringBuilder sbOutput = new StringBuilder(input.Length);

        foreach (Char c in input)
        {
            if (c == ' ')
            {
                if (!whiteSpaceWritten)
                {
                    whiteSpaceWritten = true;
                    sbOutput.Append(c);
                }
            }
            else
            {
                whiteSpaceWritten = false;
                sbOutput.Append(c);
            }
        }

        return sbOutput.ToString();
    }

Answer 5

Вы не можете использовать регулярные выражения. Например:

private static string NormalizeWhitespace(string test)
{
    string trimmed = test.Trim();

    var sb = new StringBuilder(trimmed.Length);

    int i = 0;
    while (i < trimmed.Length)
    {
        if (trimmed[i] == ' ')
        {
            sb.Append(trimmed[i]);

            do { i++; } while (i < trimmed.Length && trimmed[i] == ' ');
        }

        sb.Append(trimmed[i]);

        i++;
    }

    return sb.ToString();
}

С помощью этого метода и следующего испытательного стенда:

private static readonly Regex MultipleWhitespaceRegex = new Regex(
    @"\s+", 
    RegexOptions.Compiled);

static void Main(string[] args)
{
    string test = "regex  select    all multiple     whitespace   chars";

    const int Iterations = 15000;

    var sw = new Stopwatch();

    sw.Start();
    for (int i = 0; i < Iterations; i++)
    {
        NormalizeWhitespace(test);
    }
    sw.Stop();
    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);

    sw.Reset();

    sw.Start();
    for (int i = 0; i < Iterations; i++)
    {
        MultipleWhitespaceRegex.Replace(test, " ");
    }
    sw.Stop();
    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);
}

Я получил следующие результаты:

// NormalizeWhitespace - 27ms
// Regex - 132ms

Обратите внимание, что это было проверено только на очень простом примере, его можно было бы дополнительно оптимизировать, убрав вызов String.Trim, и оно предназначено только для того, чтобы указывать на регулярные выражения, которые иногда не являются лучшим ответом.

Answer 6

Только одно предложение, если ваши данные не имеют пробелов в Юникоде, вместо \s+ используйте [ \r\n]+ или [ \n]+ или просто + (если есть только пробел), в основном ограничьте его минимальным набором символов .

Answer 7

Массивы всегда будут быстрее

        public static string RemoveMultiSpace(string input)
    {
        var value = input;

        if (!string.IsNullOrEmpty(input))
        {
            var isSpace = false;
            var index = 0;
            var length = input.Length;
            var tempArray = new char[length];
            for (int i = 0; i < length; i++)
            {
                var symbol = input[i];
                if (symbol == ' ')
                {
                    if (!isSpace)
                    {
                        tempArray[index++] = symbol;
                    }
                    isSpace = true;
                }
                else
                {
                    tempArray[index++] = symbol;
                    isSpace = false;
                }
            }
            value = new string(tempArray, 0, index);
        }

        return value;
    }

Answer 8

Поскольку это простое выражение, заменяющее два или более пробелов одним пробелом, избавьтесь от объекта Regex и самостоятельно замените код (в C ++ / CLI):

String ^text = "Some   text  to process";
bool spaces = false;
// make the following static and just clear it rather than reallocating it every time
System::Text::StringBuilder ^output = gcnew System::Text::StringBuilder;
for (int i = 0, l = text->Length ; i < l ; ++i)
{
  if (spaces)
  {
    if (text [i] != ' ')
    {
      output->Append (text [i]);
      spaces = false;
    }
  }
  else
  {
    output->Append (text [i]);
    if (text [i] == ' ')
    {
      spaces = true;
    }
  }
}
text = output->ToString ();