Ужасная производительность для ^ [az] {0,20000} $ регулярного выражения с regcomp

Question

Мне интересно, почему компиляция такого регулярного выражения занимает до 70% моей оперативной памяти, что приводит к интенсивной перестановке и средней загрузке 16:

strcpy(regexStr,"^[a-z]{0,20000}$" );
regcomp( &regex , regexStr , REG_NOSUB | REG_EXTENDED );

Время выполнения порядка нескольких минут (раньше пришлось убивать процесс). Исполнение для ^[a-z]{0,2000}$ (2000, а не 20000) составляет около 100 мс, что очень много для меня.

Я использую это для проверки шаблона и в то же время для проверки длины. Ï нашел регулярное выражение удобным для обоих. Я что-то не так делаю?

Answer 1

Я бы предложил использовать strlen для измерения длины строки, а затем регулярное выражение /[^a-z]/ для проверки на отсутствие буквенных символов.ПОЦЕЛУЙ.

Кстати, нет, я не вижу веской причины *, почему вы получаете такую ​​производительность.

* веские причины, очевидно, не включают в себя ошибки или плохой дизайн ...

edit: оказывается, это может быть на самом деле плохой дизайн

edit2: поскольку проверка, которую вы делаете, довольно проста, вы можете реализовать ее на простом C:

int i;
for (i=0; i<20000 && str[i]!=0; i++)
  if (str[i] < 'a' || str[i] > 'z')
    return -1;
return i;

, если она возвращает -1, строка содержит символ вне диапазона az;если он возвращает 20000, строка длиннее 20000 символов;в противном случае он возвращает длину строки.(примечание: это будет явно работать только с неширокыми символьными строками)

Answer 2

Скорее всего, под капотом ваш механизм регулярных выражений преобразует ваш шаблон в нечто вроде ^(|[a-z]|[a-z][a-z]|[a-z][a-z][a-z]|..)$, что является квадратичным по количеству элементов вашего диапазона.

Answer 3

Я предполагаю, что диапазон смертности - это то, что вас убивает.Попробуйте использовать жадное неспецифическое совпадение кардинальности, например "^[a-z]*$", в сочетании с проверкой максимальной длины.Это должно быть намного быстрее.

Answer 4

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