javascript - jQuery 数据选择器中正则表达式的性能 : dependance on certain string length

Question

设置:我有一个带有一堆radio按钮的div，每个按钮都与一个自定义属性和值相关联使用 $(element).data(attr_name,attr_value);。当底层数据结构发生变化时，我遍历字段并使用此处的 ':data' 选择器将适当的按钮设置为 checked:true:https://stackoverflow.com/a/2895933/1214731

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

效果很好:它找到了合适的元素，即使是浮点值也是如此。

性能取决于值(value):
我注意到当我点击某些按钮时，页面响应时间稍长(对于大多数按钮没有明显的延迟)。再深入一点，这似乎是在搜索某些浮点值时发生的。

使用 chrome 开发工具，我记录了以下内容:

> 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

我很快排除了数字和字符串之间的相等性检查 - 那里不依赖于字符串长度。

正则表达式的执行强烈依赖于字符串长度
在上面的链接答案中，解析数据字符串的正则表达式是这样的:

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

传入的字符串格式为[name operator value]。 name 的长度似乎没有太大区别；然而，value 的长度对速度有很大影响。

具体问题:
1)为什么name的长度对性能影响很小，而value的长度影响很大？
2) name 中每个附加字符的执行时间加倍似乎过多 - 这只是链接解决方案使用的特定 regex 的特征，还是更通用的特征?
3)如何在不牺牲很多灵 active 的情况下提高性能？我仍然希望能够将参数作为单个字符串传递给 jQuery 选择器，因此预先进行类型检查似乎很困难，尽管我乐于接受建议。

---

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

Answer 1

正则表达式匹配的一个特点是它们贪婪。如果您尝试将表达式 a.*b 与字符串 abcd 匹配，它将在以下步骤中发生:

1. 第一个“a”将匹配
2. .* 将匹配第二个字符，然后是第三个字符，直到字符串结尾
3. 到达字符串末尾，还有一个“b”需要匹配，匹配失败
4. 正则表达式处理开始回溯
5. 最后一个字符将是“不匹配的”，它将尝试将“b”匹配到“d”。再次失败。更多回溯
6. 尝试将“b”与“c”匹配。失败。回溯。
7. 将“b”与“b”匹配。成功。匹配结束。

虽然您只匹配了几个字符，但您遍历了所有字符串。如果你有多个贪心运算符，你可以很容易地得到一个与指数复杂度相匹配的输入字符串。

了解backtracking将防止很多错误和性能问题。例如，'a.*b' 将匹配所有字符串 'abbbbbbb'，而不仅仅是第一个 'ab'。

在现代正则表达式引擎中防止此类错误的最简单方法是使用运算符 * 和 + 的非贪婪版本。它们通常由相同的运算符后跟一个问号表示:*?和 +?。

我承认我确实没有停下来调试您发布的复杂正则表达式，但我相信问题出在匹配“=”符号之前。贪心运算符在这个子表达式中:

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

我会尝试将其更改为非贪婪版本:

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

但这真的只是一个疯狂的猜测。我正在使用模式识别来解决问题 :-) 这是有道理的，因为它对“值”的每个字符进行回溯，直到匹配运算符。名称是线性匹配的。

这个正则表达式对我来说太复杂了。我喜欢正则表达式，但看起来这个匹配 famous quotation :

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.