Производительность регулярного выражения в селекторе данных jQuery: зависимость от определенной длины строки

Настройка: У меня есть div с пучком кнопок radio, каждый из которых связан с пользовательским атрибутом и значением с помощью $(element).data(attr_name,attr_value);. Когда изменяется базовая структура данных, я перебираю по полям и устанавливаю соответствующие кнопки в checked:true с помощью селектора ':data', найденного здесь: qaru.site/info/34783/...

$($('#style-options').find(':radio').filter(':data('+key+'=='+value+')'))
                                    .prop('checked',true).button('refresh');

Это отлично работает: он находит соответствующие элементы, даже с плавающей запятой.

Производительность зависит от значения:
Я заметил, что когда я нажимал на определенные кнопки, страница занимала меньше времени, чтобы ответить (для большинства кнопок не было заметной задержки). Копая немного глубже, это, похоже, происходит при поиске определенных значений с плавающей запятой.

Используя инструменты chrome dev, я зарегистрировал следующее:

> key='fill-opacity';  
"fill-opacity"
> value=.2*2;
0.4  
> console.time('find data'); for(var i=0;i<100;++i){$('#style-options').find(':radio').filter(':data('+key+'=='+value+')')} console.timeEnd('find data');
find data: 43.352ms undefined

> value=.2*3;
0.6000000000000001
> console.time('find data'); for(var i=0;i<100;++i){$('#style-options').find(':radio').filter(':data('+key+'=='+value+')')} console.timeEnd('find data');
find data: 10322.866ms undefined

Разница в скорости - это коэффициент > 200!

Затем я попытался ввести номер вручную (например, десятичное место, шесть, 14x нулей, один) - с той же скоростью. Все номера с одинаковым количеством цифр были одинаковой скоростью. Затем я постепенно уменьшал количество цифр:

# of digits    time (ms)
         16    10300 
         15    5185
         14    2665
         13    1314
         12    673
         11    359
         10    202
          9    116
          8    77
          7    60
          6    50
          5    41
          4    39

Я быстро исключил проверку равенства между numeric и string - не зависимо от длины строки.

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

var matcher = /\s*(?:((?:(?:\\\.|[^.,])+\.?)+)\s*([!~><=]=|[><])\s*("|')?((?:\\\3|.)*?)\3|(.+?))\s*(?:,|$)/g;

Переходящая строка имеет вид [name operator value]. Длина name, по-видимому, не имеет большого значения; однако длина value оказывает большое влияние на скорость.

Конкретные вопросы:
1) Почему длина name оказывает минимальное влияние на производительность, а длина value оказывает большое влияние?
2) Удвоение времени выполнения с каждым дополнительным символом в name кажется чрезмерным - это просто характеристика конкретного regex используемого связанного решения или это более общая функция?
3) Как повысить производительность, не жертвуя большой гибкостью? Я бы все равно мог передавать аргументы в виде одной строки в jQuery selector, поэтому проверка типов перед началом кажется сложной, хотя я открыт для предложений.

Базовый тестовый код для regex совпадающих скоростей:

matcher = /\s*(?:((?:(?:\\\.|[^.,])+\.?)+)\s*([!~><=]=|[><])\s*("|')?((?:\\\3|.)*?)\3|(.+?))\s*(?:,|$)/g;

console.time('regex'); for(var i=0;i<1000;++i){matcher.lastIndex=0; matcher.exec('x=='+.1111111111111)}; console.timeEnd('regex')
regex: 538.018ms

//add an extra digit - doubles duration of test
console.time('regex'); for(var i=0;i<1000;++i){matcher.lastIndex=0; matcher.exec('x=='+.11111111111111)}; console.timeEnd('regex')
regex: 1078.742ms

//add a bunch to the length of 'name' - minimal effect
console.time('regex'); for(var i=0;i<1000;++i){matcher.lastIndex=0; matcher.exec('xxxxxxxxxxxxxxxxxxxx=='+.11111111111111)}; console.timeEnd('regex')
regex: 1084.367ms

Ответы

Ответ 1

Характерной особенностью регулярного выражения является то, что они жадные. Если вы попытаетесь сопоставить выражение a.*b с строкой abcd, это произойдет в следующих шагах:

  • первый символ "a" будет соответствовать
  • . * будет соответствовать второй char, а затем третьей, до конца строки
  • до конца строки, все еще существует "b" для соответствия, соответствие не будет выполнено
  • обработка regexp начинается с backtrack
  • последний char будет "непревзойденным", и он попытается сопоставить "b" с "d". Сбой снова. Больше backtracking
  • пытается сопоставить "b" с "c". Потерпеть неудачу. Backtrack.
  • совпадение "b" с "b" . Успех. Соответствие заканчивается.

Хотя вы подобрали всего несколько символов, вы повторили всю строку. Если у вас более одного жадного оператора, вы можете легко получить строку ввода, которая будет соответствовать экспоненциальной сложности.

Понимание backtracking предотвратит множество ошибок и проблем с производительностью. Например, "a. * B" будет соответствовать всей строке "abbbbbbb", а не только "ab".

Самый простой способ предотвратить подобные ошибки в современных системах regexp - использовать нежелательную версию операторов * и+. Обычно они представлены теми же операторами, за которыми следует знак вопроса: *? и +?.

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

(?:\\\.|[^.,])+\.?)+

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

(?:\\\.|[^.,])+\.?)+?

но это действительно просто дикая догадка. Я использую распознавание образов для решения проблемы:-) Это имеет смысл, потому что это возврат к каждому символу "значения" до соответствия оператору. Имя сопоставляется линейно.

Это регулярное выражение слишком сложно для моего вкуса. Мне нравятся регулярные выражения, но похоже, что это соответствует этой знаменитой цитате:

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