一行正規表示式判斷質數的程式碼

2022-05-26 22:02:35

背景

昨天無意中看到一篇大佬的文章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+$

步驟	匹配結果	說明
step 1	1 1 1 1 1 1 1 1 1	`(11+?)`匹配到`"11"`
step 2	1 1 1 1 1 1 1 1 1	分組結果賦值給`1`，那麼正則就變成 "11"+$，繼續匹配剩餘的字元(7個"1")
step 3	1 1 1 1 1 1 1 1 1	再重複3輪的匹配，發現剩餘一個"1"，不滿足$，進行回溯
step 4	1 1 1 1 1 1 1 1 1	還是不滿足$，繼續回溯
step 5	1 1 1 1 1 1 1 1 1	一直回溯到`step 1`，`(11+?)`匹配到`"111"`
step 6	1 1 1 1 1 1 1 1 1	分組結果賦值給`1`，那麼正則就變成 "111"+$，繼續匹配剩餘的字元(6個"1")
step 7	1 1 1 1 1 1 1 1 1	再重複2輪的匹配，滿足$，匹配成功

原理

經過上述的分析，不難發現，其實回溯就是將數位不斷除於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

耗時上減少了接近一半

總結

其實這個正則效能非常差（窮舉法），實用性不高，但是思路很讓人驚豔

到此這篇關於一行正規表示式判斷質數的文章就介紹到這了,更多相關正規表示式判斷質數內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

一行正規表示式判斷質數的程式碼

目錄

背景

範例

正則分析

原理

優化空間

效能測試

總結

熱門文章