Самый эффективный способ удалить специальные символы из строки

Question

Я хочу удалить все специальные символы из строки. Допустимые символы: A-Z (заглавные или строчные), цифры (0-9), подчеркивание (_) или знак точки (.).

У меня есть следующее, это работает, но я подозреваю (я знаю!), Что это не очень эффективно:

    public static string RemoveSpecialCharacters(string str)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.Length; i++)
        {
            if ((str[i] >= '0' && str[i] <= '9')
                || (str[i] >= 'A' && str[i] <= 'z'
                    || (str[i] == '.' || str[i] == '_')))
                {
                    sb.Append(str[i]);
                }
        }

        return sb.ToString();
    }

Какой самый эффективный способ сделать это? Как будет выглядеть регулярное выражение, и как оно будет сравниваться с обычными манипуляциями со строками?

Строки, которые будут очищены, будут довольно короткими, обычно длиной от 10 до 30 символов.

Answer 1

Почему вы считаете, что ваш метод неэффективен? На самом деле это один из самых эффективных способов сделать это.

Вы, конечно, должны прочитать символ в локальной переменной или использовать перечислитель, чтобы уменьшить количество обращений к массиву:

public static string RemoveSpecialCharacters(this string str) {
   StringBuilder sb = new StringBuilder();
   foreach (char c in str) {
      if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || c == '.' || c == '_') {
         sb.Append(c);
      }
   }
   return sb.ToString();
}

Одна вещь, которая делает такой метод эффективным, заключается в том, что он хорошо масштабируется. Время выполнения будет зависеть от длины строки. Нет неприятных сюрпризов, если бы вы использовали его на большой струне.

Edit:
Я сделал быстрый тест производительности, выполняя каждую функцию по миллиону строк из 24 символов. Вот результаты:

Исходная функция: 54,5 мс.
Мое предлагаемое изменение: 47.1 мс.
Мой с настройкой емкости StringBuilder: 43,3 мс.
Регулярное выражение: 294,4 мс.

Редактировать 2: Я добавил различие между A-Z и a-z в приведенном выше коде. (Я перезапускаю тест производительности, и нет заметной разницы.)

Редактировать 3:
Я протестировал решение lookup + char [], и оно работает примерно за 13 мс.

Цена, которую нужно заплатить, - это, конечно, инициализация огромной таблицы поиска и ее сохранение в памяти. Ну, это не так много данных, но много для такой тривиальной функции ...

private static bool[] _lookup;

static Program() {
   _lookup = new bool[65536];
   for (char c = '0'; c <= '9'; c++) _lookup[c] = true;
   for (char c = 'A'; c <= 'Z'; c++) _lookup[c] = true;
   for (char c = 'a'; c <= 'z'; c++) _lookup[c] = true;
   _lookup['.'] = true;
   _lookup['_'] = true;
}

public static string RemoveSpecialCharacters(string str) {
   char[] buffer = new char[str.Length];
   int index = 0;
   foreach (char c in str) {
      if (_lookup[c]) {
         buffer[index] = c;
         index++;
      }
   }
   return new string(buffer, 0, index);
}

Answer 2

Ну, если вам действительно не нужно выжимать производительность из вашей функции, просто переходите к тому, что проще всего поддерживать и понимать. Регулярное выражение будет выглядеть так:

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

public static string RemoveSpecialCharacters(string str)
{
    return Regex.Replace(str, "[^a-zA-Z0-9_.]+", "", RegexOptions.Compiled);
}

Answer 3

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

редактировать

Также, для скорости, вы захотите инициализировать емкость вашего StringBuilder длиной вашей входной строки. Это позволит избежать перераспределения. Эти два метода вместе дадут вам скорость и гибкость.

другое редактирование

Я думаю, что компилятор мог бы оптимизировать его, но с точки зрения стиля и эффективности я рекомендую foreach вместо for.

Answer 4

public static string RemoveSpecialCharacters(string str)
{
    char[] buffer = new char[str.Length];
    int idx = 0;

    foreach (char c in str)
    {
        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z')
            || (c >= 'a' && c <= 'z') || (c == '.') || (c == '_'))
        {
            buffer[idx] = c;
            idx++;
        }
    }

    return new string(buffer, 0, idx);
}

Answer 5

Регулярное выражение будет выглядеть так:

public string RemoveSpecialChars(string input)
{
    return Regex.Replace(input, @"[^0-9a-zA-Z\._]", string.Empty);
}

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

Answer 6

Если вы используете динамический список символов, LINQ может предложить гораздо более быстрое и изящное решение:

public static string RemoveSpecialCharacters(string value, char[] specialCharacters)
{
    return new String(value.Except(specialCharacters).ToArray());
}

Я сравнил этот подход с двумя из предыдущих "быстрых" подходов (компиляция релиза):

• Решение с массивом символов от LukeH - 427 мс
• Решение StringBuilder - 429 мс
• LINQ (этот ответ) - 98 мс

Обратите внимание, что алгоритм немного изменен - ​​символы передаются в виде массива, а не жестко закодированы, что может слегка повлиять на вещи (т. Е. / Другие решения будут иметь внутренний цикл foor для проверки массива символов).

Если я перейду к жестко закодированному решению с помощью предложения LINQ where, то получится:

• Решение с массивом символов - 7ms
• Решение StringBuilder - 22 мс
• LINQ - 60 мс

Возможно, стоит взглянуть на LINQ или модифицированный подход, если вы планируете написать более общее решение, а не жестко кодировать список символов. LINQ определенно дает вам краткий, хорошо читаемый код - даже больше, чем Regex.

Answer 7

Я не уверен, что ваш алгоритм не эффективен. Это O (n) и смотрит на каждого персонажа только один раз. Вы не получите ничего лучше, если не будете волшебным образом знать значения перед их проверкой.

Я бы, однако, инициализировал емкость вашего StringBuilder до начального размера строки. Я предполагаю, что ваша проблема производительности связана с перераспределением памяти.

Примечание: проверка A - z небезопасна. Вы включаете [, \, ], ^, _ и `...

Дополнительное примечание 2: Для этого дополнительного показателя эффективности сравните порядок сравнений, чтобы свести к минимуму количество сравнений. (В худшем случае вы говорите о 8 сравнениях, так что не думайте слишком усердно.) Это меняется с вашим ожидаемым вкладом, но один пример может быть:

if (str[i] >= '0' && str[i] <= 'z' && 
    (str[i] >= 'a' || str[i] <= '9' ||  (str[i] >= 'A' && str[i] <= 'Z') || 
    str[i] == '_') || str[i] == '.')

Примечание 3: Если по какой-либо причине вам ДЕЙСТВИТЕЛЬНО нужно, чтобы это было быстро, оператор switch может быть быстрее. Компилятор должен создать таблицу переходов для вас, что приведет к единственному сравнению:

switch (str[i])
{
    case '0':
    case '1':
    .
    .
    .
    case '.':
        sb.Append(str[i]);
        break;
}

Answer 8

Я согласен с этим примером кода. Единственное другое это я превращаю в метод расширения строкового типа. Так что вы можете использовать его в очень простой строке или коде:

string test = "abc@#$123";
test.RemoveSpecialCharacters();

Спасибо Гуффе за ваш эксперимент.

public static class MethodExtensionHelper
    {
    public static string RemoveSpecialCharacters(this string str)
        {
            StringBuilder sb = new StringBuilder();
            foreach (char c in str)
            {
                if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || c == '_')
                {
                    sb.Append(c);
                }
            }
            return sb.ToString();
        }
}

Answer 9

Вы можете использовать регулярные выражения следующим образом:

return Regex.Replace(strIn, @"[^\w\.@-]", "", RegexOptions.None, TimeSpan.FromSeconds(1.0));

Answer 10

Мне кажется, это хорошо. Единственное улучшение, которое я бы сделал, - это инициализация StringBuilder длиной строки.

StringBuilder sb = new StringBuilder(str.Length);