目录
- 背景
- 示例
- 正则分析
- 原理
- 优化空间
- 性能测试
- 总结
背景
昨天无意中看到一篇大佬的文章Primality regex(正则表达式判断质数),惊为天人,正则表达式也能用来判断质数了?立马来研究下
示例
perl -wle \’print \”Prime\” if (1 x shift) !~ /^1?$|^(11+?)\\1+$/\’ [number]
翻译成JS代码如下
function isPrime(n) {
return !/^1?$|^(11+?)\\1+$/.test(\”1\”.repeat(n))
}
代码逻辑非常简单,生成"1" * n长度的字符串,通过/^1?$|^(11+?)\\1+$/正则表达式进行判断,再将结果取反
正则分析
/^1?$|^(11+?)\\1+$/
上面正则表达式有2个分支,分别是
- /^1?$
- ^(11+?)\\1+$
分支1 逻辑很简单,就是匹配0或者1个 "1",因为要排除数字1(非质数)
分支2 就有意思了,可以拆成2块来看
- ^(11+?)
- \\1+$
表达式1,非贪婪模式下匹配 "11" "111" "1111"….,作为一个分组表达式2,\\1代表将表达式1匹配的结果赋值给\\1,判断是否结尾,否的话会触发回溯(因为表达式1可能匹配多种情况)
举个例子就更清晰了,比如传入n = 9,分支1不满足可以直接忽略^(11+?)\\1+$
原理
经过上述的分析,不难发现,其实回溯就是将数字不断除于2、3、4….,最后检查是否有余数,没有的话就匹配成功(非质数),非常简单粗暴的穷举法
优化空间
仔细看正则匹配的过程分析,其实step 3 ~ step 4的回溯完全没有必要,那么正则可以改写成这样/^1?$|^(11+?)\\1+?$/,将\\1+改成非贪婪模式\\1+?,那么就放弃step 4回溯
性能测试
console.time(\’优化前\’)
console.log(!/^1?$|^(11+?)\\1+$/.test(\”1\”.repeat(33331)));
console.timeEnd(\’优化前\’)
console.time(\’优化后\’)
console.log(!/^1?$|^(11+?)\\1+?$/.test(\”1\”.repeat(33331)));
console.timeEnd(\’优化后\’)
// true
// 优化前: 227.9189453125 ms
// true
// 优化后: 155.797119140625 ms
耗时上减少了接近一半
总结
其实这个正则性能非常差(穷举法),实用性不高,但是思路很让人惊艳
到此这篇关于一行正则表达式判断质数的文章就介绍到这了,更多相关正则表达式判断质数内容请搜索悠久资源网以前的文章或继续浏览下面的相关文章希望大家以后多多支持悠久资源网!
您可能感兴趣的文章:
- 正则表达式(RegExp)判断文本框中是否包含特殊符号
- JS使用正则表达式判断输入框失去焦点事件
- 使用正则表达式判断密码强弱
- 判断颜色是否合法的正则表达式(详解)
- 正则表达式号码靓号类型判断代码
- 判断时间的正则表达式
- 用正则表达式来判断素数的代码