流行中の

正規表現ベンチ、もしくは文字列生成ベンチ。Python Challenge が一段落したのでやってみる。

ベースライン、速さに定評のある C。

$ gcc -O2 regex.c
$ time ./a.out
no

real    0m0.737s
user    0m0.734s
sys     0m0.003s

なんか遅い。Mac だからか。

意外と古参 Ruby。

$ cat regex.rb
query = "b" * (1024 * 1024) + "x";
pat = /^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$/;
puts(query =~ pat ? "yes" : "no");
$ 
$ time ruby regex.rb
^Cregex.rb:3:in `=~': Interrupt
    from regex.rb:3


real    60m0.368s
user    59m36.195s
sys     0m4.325s

まさかの長考。

駿足ラクダ O'Caml。

$ cat regex.ml
let query = String.make (1024 * 1024) 'b' ^ "x"
and pat = Str.regexp "^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$"
in 
  print_endline (if Str.string_match pat query 0 then "yes" else "no")
$ 
$ ocamlopt str.cmxa regex.ml
$ time ./a.out
^C

real    60m0.476s
user    59m53.573s
sys     0m1.797s

駄目でした。

純真無垢の怠け者 Haskell。

$ cat regex.hs
import Text.Regex
query = replicate (1024 * 1024) 'b' ++ "x"
pat = mkRegex "^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$"
main = putStrLn $ if matchRegex pat query == Nothing then "no" else "yes"
$ 
$ ghc --make regex.hs 2> /dev/null
$ time ./regex
no

real    0m0.913s
user    0m0.883s
sys     0m0.027s

これは全く怠けていないぞ。

何でも入ってる D 言語。

$ cat regex.d
import std.stdio;
import std.string;
import std.regexp;
void main() {
    auto query = repeat("b", 1024 * 1024) ~ "x";
    auto pat = RegExp("^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$");
    writefln(pat.test(query) ? "yes" : "no");
}
$ 
$ gdc regex.d
$ time ./a.out
^C

real    60m0.415s
user    59m37.156s
sys     0m3.480s

たぶん初めて書いた。

探し物、あります grep。

$ perl -e 'print ("b" x (1024 * 1024) . "x")' > query
$ time grep -c '^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$' query
0

real    0m3.295s
user    0m3.193s
sys     0m0.021s

このくらいが丁度いい速さなんじゃないか。

我らが LiLFeS。

$ cat regex.lil
:- module("regex_bench").
query <- pred. query_sub <- pred. pat <- pred. main <- pred.
query(Q) :- query_sub(20, Q1), strcat(Q1, "x", Q).
query_sub(X, Q) :- X <= 0, !, Q = "b".
query_sub(X, Q) :- X1 is X - 1, query_sub(X1, Q1), strcat(Q1, Q1, Q).
pat("^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$").
main :- query(Q), pat(P), regex_match(P, Q).
$ 
$ time lilfes -l regex.lil -e "?- main." 2> /dev/null
no

real    0m0.937s
user    0m0.920s
sys     0m0.015s

正規表現が使える時点で何かがすごいと思うのです。

孤独の lysh。

$ cat regex.lsh
:let query := nth 20 (iter (:\x := x :++ x) b) :++ x
:and pat := '^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$'
:in 
  regex query pat |> :\x := println :@ ifte (nil? x) no yes
$ 
$ time lysh regex.lsh
no

real    0m0.835s
user    0m0.808s
sys     0m0.019s

なんともコメントしづらい。