Google Code Searchで使われている正規表現ライブラリRE2が公開された。 http://code.google.com/p/re2/ PCRE系のバックトラック式(指数的時間、どこまでも伸びるスタック)に変わるものとして、Ken Thompsonのopen source grepで使われている fast DFA方式(多項式時間、固定スタック)で実装されているらしい。ちょと試してみようかと。 まずはPCREの速度測定 http://swtch.com/~rsc/regexp/regexp1.html とのことで、試してみる。 PCREで(a?)^n(a)nをつくって実験。 #include <iostream> #include <string> #include <sys/time.h> #include <pcrecpp.h> long long gettime() {
![RE2を試してみた。 - 初学者の箸置](https://cdn-ak-scissors.b.st-hatena.com/image/square/9f014a96eef4d5168d1c587cbbc5cd8d1d5bd68e/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Ft%2Ftkuro%2F20100317%2F20100317153143.png)