Rでは量指定子を変えても正規表現の実行速度にほとんど影響しない

はじめに

pythonでは

【メモ】量指定子を変えると正規表現の実行速度が桁で変わる（仮）

という話があるので、Rでも試してみた。

• +と{1, }
  
• *と{0, }
  
• ?と{0, 1}
  

を比較する。

結果としてはbase::grepもstringr::str_detectも大差ないか、{m, n}で指定する方が若干遅い。

残念。

実験開始

準備

require(stringr)
require(microbenchmark)
require(knitr)

x <- 'bbbbbbbbbbbbbbbbbb'

base::grepの場合

kable(summary(microbenchmark(
  grep('b+', x),
  grep('b{1,}', x),
  grep('b*', x),
  grep('b{0,}', x),
  grep('b?', x),
  grep('b{0,1}', x)
)))

expr	min	lq	mean	median	uq	max	neval
grep("b+", x)	4.790	5.4740	8.80653	5.4750	9.5795	67.057	100
grep("b{1,}", x)	4.790	5.4740	7.33539	5.8165	10.2640	14.369	100
grep("b*", x)	5.474	5.4740	7.52007	6.1580	7.1850	34.213	100
grep("b{0,}", x)	5.474	5.4745	9.04599	6.1580	10.2640	116.322	100
grep("b?", x)	4.790	5.4740	8.36862	6.1580	10.2640	56.109	100
grep("b{0,1}", x)	5.474	5.4740	9.29229	6.1580	6.8430	95.110	100

stringr::str_detectの場合

kable(summary(microbenchmark(
  str_detect(x, 'b+'),
  str_detect(x, 'b{1,}'),
  str_detect(x, 'b*'),
  str_detect(x, 'b{0,}'),
  str_detect(x, 'b?'),
  str_detect(x, 'b{0,1}')
)))

expr	min	lq	mean	median	uq	max	neval
str_detect(x, "b+")	34.212	36.2650	51.34606	37.6340	60.5560	216.222	100
str_detect(x, "b{1,}")	35.581	37.6340	51.42818	39.6870	64.6615	172.430	100
str_detect(x, "b*")	34.896	36.2655	53.82303	39.3445	63.9770	169.693	100
str_detect(x, "b{0,}")	35.581	37.6340	54.09672	46.1875	66.3725	110.164	100
str_detect(x, "b?")	33.528	34.8970	54.08311	41.7390	59.8715	460.498	100
str_detect(x, "b{0,1}")	34.212	35.5810	59.48179	52.0030	59.1875	632.243	100

感想

• {m, n}の方が、明示的で分かりよいと思う
• grepの方が速いのは意外だった