Как сделать быструю проверку на разрешенные символы?

Question

[Drottarutarnum]

У меня есть класс для сериализации данных в текстовой формат с текстовыми индексами (ключами)

Разрешенные символы a-zA-Z09-_

Регулярные выражения довольно медленны для меня, есть ли способ проверить удовлетворяет ли строка условию более быстрым способом?

Comments

[OwDafuq]

1) Регулярки. Почему медленные? Вы хотите проверить за раз 100 МБ текста?
2) Банальный посимвольный перебор

[Александр]

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

Answer 1

[VoidVolker]

Да, просто получаете код символа из строки и далее просто проверяете попадает ли он в диапазон нужных вам символов или совпадает ли с разрешенными символами. Если все равно недостаточно быстро будет, то можно использовать таблицу переходов. Создаете массив и в каждой ячейке под номерами требуемых символов ставите флаг, что такой-то символ разрешен. В этом случае время проверки одного символа всегда будет фиксированным и равняться времени, условно, времени выполнения двух операций: "сложить адрес начала массива и номер символа" и "получить значение по адресу". Условно - потому что никогда не знаешь, какой сюрприз может выдать оптимизатор и что в итоге будет, а еще есть всякие виды адресации, смещения и прочее. Так то оптимизатор может и обычный CASE оптимизировать до таблицы переходов - но я не знаю есть ли такая оптимизация в C# и если есть - то при каких условиях она работает.

Answer 2

[EasyGame]

Быстрее всего запихать допустимые символы в SortedSet и проверять в цикле. Код бенчмарка и результат под спойлером.

спойлер

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Security.Cryptography;
using System.Text.RegularExpressions;

namespace ConsoleApp19
{
    [MemoryDiagnoser]
    public partial class Program
    {
        const string whitlistchars = "qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM1234567890-_";

        static readonly string Source10k = string.Join("", Enumerable.Range(0, 10000).Select(x => whitlistchars[RandomNumberGenerator.GetInt32(0, whitlistchars.Length)]));
        static readonly string Source128 = string.Join("", Enumerable.Range(0, 128).Select(x => whitlistchars[RandomNumberGenerator.GetInt32(0, whitlistchars.Length)]));

        [GeneratedRegex("^[A-Za-z0-9_-]+$")] private static partial Regex Filter();

        static readonly SortedSet<char> whiteList = new();
        static bool CheckSymbolRegex(string symbol) => Filter().IsMatch(symbol);

        static bool CheckSymbolNative(char symbol)
        {
            if ((symbol >= 'A' && symbol <= 'Z')
                || (symbol >= 'a' && symbol <= 'z')
                || (symbol >= '0' && symbol <= '9')
                || symbol == '_'
                || symbol == '-') return true;

            return false;
        }

        [Benchmark]
        public bool CheckRegex10k()
        {
            return CheckSymbolRegex(Source10k);
        }

        [Benchmark]
        public bool CheckNative10k()
        {
            foreach (var symbol in Source10k)
            {
                if (!CheckSymbolNative(symbol)) return false;
            }

            return true;
        }

        [Benchmark]
        public bool CheckSortedSet10k()
        {
            foreach (var symbol in Source10k)
            {
                if (!whiteList.Contains(symbol)) return false;
            }

            return true;
        }

        [Benchmark]
        public bool CheckRegex128()
        {
            return CheckSymbolRegex(Source128);
        }

        [Benchmark]
        public bool CheckNative128()
        {
            foreach (var symbol in Source128)
            {
                if (!CheckSymbolNative(symbol)) return false;
            }

            return true;
        }

        [Benchmark]
        public bool CheckSortedSet128()
        {
            foreach (var symbol in Source128)
            {
                if (!whiteList.Contains(symbol)) return false;
            }

            return true;
        }

        static void InitWhiteList()
        {
            foreach (var symbol in whitlistchars)
            {
                whiteList.Add(symbol);
            }
        }

        static void Main(string[] args)
        {
            InitWhiteList();

            var summary = BenchmarkRunner.Run<Program>();
            Console.ReadKey();
        }
    }
}

Comments

[Drottarutarnum]

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