Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2009-09-16

[][][][][][][][][][][] quine リレー

Update (2013-07-15): I improved this program to 50-language version. 50 言語版にパワーアップさせました。


これはこのプログラム自身を出力する Unlambda プログラム、を出力する Whitespace プログラム、を出力する brainfuck プログラム、を出力する Java プログラム、を出力する C プログラム、を出力する Haskell プログラム、を出力する OCaml プログラム、を出力する Lua プログラム、を出力する Perl プログラム、を出力する Python プログラム、を出力する Ruby プログラム、です。

# ruby
l=92.chr;eval s="s=s.dump[r=1..-2].gsub(/("+l*4+"){4,}(?!\")/){|t|'\"+l*%d+\"'%(t
.size/2)};5.times{s=s.dump[r]};puts\"# python\\nprint(\\\"# perl\\\\nprint(\\\\\\
\"# lua"+l*4+"nprint("+l*7+"\"(* ocaml *)"+l*8+"nprint_endline"+l*15+"\"-- haskel
l"+l*16+"nimport Data.List;import Data.Bits;import Data.Char;main=putStrLn("+l*31
+"\"/* C */"+l*32+"n#include<stdio.h>"+l*32+"nint main(void){char*s[501]={"+l*31+
"\"++intercalate"+l*31+"\","+l*31+"\"(c(tail(init(show("+l*31+"\"/* Java */"+l*32
+"npublic class QuineRelay{public static void main(String[]a){String[]s={"+l*31+"
\"++intercalate"+l*31+"\","+l*31+"\"(c("+l*31+"\"brainfuck"+l*64+"n++++++++[>++++
<-]+++++++++>>++++++++++"+l*31+"\"++(concat(snd(mapAccumL h 2("+l*31+"\"110"+l*31
+"\"++g(length s)++"+l*31+"\"22111211100111112021111102011112120012"+l*31+"\"++co
ncatMap("+l*32+"c->let d=ord c in if d<11then"+l*31+"\"21002"+l*31+"\"else"+l*31+
"\"111"+l*31+"\"++g d++"+l*31+"\"22102"+l*31+"\")s++"+l*31+"\"2100211101012021122
2211211101000120211021120221102111000110120211202"+l*31+"\"))))))++"+l*31+"\","+l
*63+"\""+l*64+"n"+l*63+"\"};int i=0;for(;i<94;i++)System.out.print(s[i]);}}"+l*31
+"\")))))++"+l*31+"\",0};int i=0;for(;s[i];i++)printf("+l*63+"\"%s"+l*63+"\",s[i]
);puts("+l*63+"\""+l*63+"\");return 0;}"+l*31+"\");c s=map("+l*32+"s->"+l*31+"\""
+l*63+"\""+l*31+"\"++s++"+l*31+"\""+l*63+"\""+l*31+"\")(unfoldr t s);t[]=Nothing;
t s=Just(splitAt(if length s>w&&s!!w=='"+l*31+"\"'then 501else w)s);w=500;f 0=Not
hing;f x=Just((if x`mod`2>0then '0'else '1'),x`div`2);g x= reverse (unfoldr f x);
h p c=let d=ord c-48in(d,replicate(abs(p-d))(if d<p then '<'else '>')++"+l*31+"\"
."+l*31+"\");s="+l*31+"\"# ruby"+l*32+"n"+l*31+"\"++"+l*31+"\"l=92.chr;eval s=\"+
(z=l*31)+\"\\\"\"+s+z+\"\\\""+l*31+"\"++"+l*31+"\""+l*32+"n"+l*31+"\""+l*15+"\""+
l*7+"\")"+l*4+"n\\\\\\\")\\\")\"########### (c) Yusuke Endoh, 2009 ###########\n"

最初のコメント行以外の改行は読みやすさのために入れています。QuineRelay.rb などというファイルとして保存してください。以下のように実行します。

$ ruby QuineRelay.rb > QuineRelay.py
$ python QuineRelay.py > QuineRelay.pl
$ perl QuineRelay.pl > QuineRelay.lua
$ lua QuineRelay.lua > QuineRelay.ml
$ ocaml QuineRelay.ml > QuineRelay.hs
$ runghc QuineRelay.hs > QuineRelay.c
$ gcc -Wall -o QuineRelay QuineRelay.c && ./QuineRelay > QuineRelay.java
$ javac QuineRelay.java && java QuineRelay > QuineRelay.bf
$ beef QuineRelay.bf > QuineRelay.ws
$ wspace QuineRelay.ws > QuineRelay.unl
$ unlambda QuineRelay.unl > QuineRelay2.rb

最終的に得られる出力 QuineRelay2.rb は最初の Ruby プログラムと一致するはず。

$ diff QuineRelay.rb QuineRelay2.rb

念のため各処理系バージョンを書いておきます。すべて Debian/lennyaptインストールできるものです。

2008-11-02

[][][][] eval の速度比較

ruby 1.9ruby 1.8 より eval が 3 倍くらい遅いというのは有名 (?) な話です。では、他の LL と比べてどうなんだろうと思ったので、比較をしてみました。

"1" を 100000 回 eval する

eval の前処理と後処理にかかる時間の比較。

ruby 1.8 (trunk) : 0.22 sec
ruby 1.9 (trunk) : 0.82 sec
perl 5.10        : 1.23 sec
python 3.0rc1    : 1.83 sec
php 5.3 alpha 2  : N/A (> 180 sec)

この結果だけみると、ruby 1.9 の eval はそれでも速い方に見えます *1

それはともかく PHP が激遅なんですが、どうも eval を繰り返し呼ぶと、なぜか呼んだ回数以上にどんどん遅くなる (O(n^3) くらい?) ので、意味のある速度比較ができません。ひょっとしたらやんごとなき事情があるのかもしれませんが、きっとバグだと思います。PHP さすがですね!

"1+1+1+ ...(100000 個)... +1" を eval する

すごく深い抽象構文木をパース・評価するのにかかる時間の比較。

ruby 1.8 (trunk) : N/A (SEGV)
ruby 1.9 (trunk) : N/A (SEGV)
perl 5.10        : 0.17 sec
python 3.0rc1    : N/A (SEGV)
php 5.3 alpha 2  : 0.36 sec

ruby もさすがですね! しかし python が落ちると驚きますね (ぼくの中で python は優等生なのです) 。原因はたぶん共通で、深さ 50000 の構文木関数再帰呼び出しでたどって、スタックオーバーフローしているものと思われます。

しかし比較にならないなあ。

関数定義 50000 個を eval する

何もしない関数の定義を 50000 個並べたものをパース・評価するのにかかる時間の比較。

ruby 1.8 (trunk) : 1.05 sec
ruby 1.9 (trunk) : 2.81 sec
perl 5.10        : 1.93 sec
python 3.0rc1    : 4.51 sec
php 5.3 alpha 2  : 1.01 sec

想像ですが、このくらいが現実を表しているんじゃないでしょうか。

という感じ?ちゃんと調べてないですけどね。

まとめ

まあ、速度なんてどうでもいい話題な上に、eval の速度なんてかなりどうでもいいですよね。いいんです。

ベンチマークに使ったコード

#!/usr/bin/env ruby19

require "tempfile"

RUBY18 = ["ruby 1.8 (trunk)", "ruby18"]
RUBY19 = ["ruby 1.9 (trunk)", "ruby19"]
PERL   = ["perl 5.10       ", "./local/bin/perl"]
PYTHON = ["python 3.0rc1   ", "./local/bin/python3.0"]
PHP    = ["php 5.3 alpha 2 ", "./local/bin/php"]

def bench(header, *args)
  f = Tempfile.new("bench")
  yield f
  f.close
  time = (1..5).map do
    t = Time.now
    system(*args, f.path)
    (p $?; break []) if $? != 0
    Time.now - t
  end.min
  f.unlink
  puts "%s : %.2f sec" % [header, time] if time
end

type = ARGV[0] || :all

if type == "1" || type == :all

puts "eval \"1\" (100000 times)"

n = 100000
bench(*RUBY18) do |f| f.puts <<SRC
i = 0
while i < #{ n }
  eval("1")
  i += 1
end
SRC
end

bench(*RUBY19) do |f| f.puts <<SRC
i = 0
while i < #{ n }
  eval("1")
  i += 1
end
SRC
end

bench(*PERL) do |f| f.puts <<SRC
for($i = 0; $i < #{ n }; $i++) {
  eval("1")
}
SRC
end

bench(*PYTHON) do |f| f.puts <<SRC
for i in range(#{ n }):
  eval("1")
SRC
end

#bench(*PHP) do |f| f.puts <<SRC
#<?php
#for($i = 0; $i < #{ n }; $i++) {
#  eval("1;");
#}
#SRC
#?>
#end

end

if type == "2" || type == :all

puts "eval 1+1+..(100000 times)..+1"

s = "1+" * 100000 + "1"
bench(*RUBY18) {|f| f.puts 'eval("' + s + '")' }
bench(*RUBY19) {|f| f.puts 'eval("' + s + '")' }
bench(*PERL  ) {|f| f.puts 'eval("' + s + '")' }
bench(*PYTHON) {|f| f.puts 'eval("' + s + '")' }
bench(*PHP   ) {|f| f.puts '<?php eval("' + s + ';"); ?>' }

end

if type == "3" || type == :all

puts "define 50000 functions"

n = 50000
bench(*RUBY18) do |f|
  f.puts "eval <<SRC"
  (1..n).each {|i| f.puts "def foo#{i};end" }
  f.puts "SRC"
end
bench(*RUBY19) do |f|
  f.puts "eval <<SRC"
  (1..n).each {|i| f.puts "def foo#{i};end" }
  f.puts "SRC"
end
bench(*PERL) do |f|
  f.puts "eval(<<SRC)"
  (1..n).each {|i| f.puts "sub foo#{i}() {}" }
  f.puts "SRC"
end
bench(*PYTHON) do |f|
  f.puts "exec(\"\"\""
  (1..n).each {|i| f.puts "def foo#{i}(): pass" }
  f.puts "\"\"\")"
end
bench(*PHP) do |f|
  f.puts "<?php"
  f.puts "eval(\""
  (1..n).each {|i| f.puts "function foo#{i}(){}" }
  f.puts "\");"
  f.puts "?>"
end

end

ついでに、PHP が eval を重ねる事に遅くなっていく様子。

$ ./local/bin/php -v
PHP 5.3.0alpha2 (cli) (built: Oct 31 2008 19:55:08)
Copyright (c) 1997-2008 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2008 Zend Technologies

$ ./local/bin/php -r '
$t = time() + (float)microtime();
while(1) {
  for($i = 0; $i < 10000; $i++) eval("1;");
  $u = time() + (float)microtime();
  print ($u - $t) . "\n";
  $t = $u;
}
'
0.58000898361206
1.6200242042542
3.3400499820709
12.870194911957

*1:それだけ難しいことをしていないという説も?

*2php の実装は全く知らないで言ってます。勘違いだったら教えてください。

*3perl 6 はもっと遅くなってるかも?

2008-01-16

[][][] 多倍長整数演算の速度比較

rubyperlpython の多倍長整数演算の速度を適当に比較してみました。フィボナッチ数の計算速度比較以上にどーでもいい比較です。

前置き

使用した処理系のバージョンはそれぞれ以下のとおりです。

perl は多倍長整数を扱う方法が何個かあるようなので、標準装備らしい bigint と、別途 CPAN でインストールしないといけない Math::BitInt::GMP (GMP の binding) の 2 種類を試しました。python の psyco はなんか動かなくて面倒だったので試してません。この比較にはあまり影響しないような気がしてます。僕は PerlPython は素人なので、もっと速くて美しい書き方・やり方があったら教えてください。

実験 1: 5 の累乗の計算

5 の 30,000 乗、100,000 乗、300,000 乗、1,000,000 乗の計算にかかる時間を調べました。単位は秒。

300001000003000001000000
ruby 0.09 0.13 0.78 8.21
python 0.14 0.12 0.31 1.37
perl(bigint) 3.67 37.05 N/A N/A
perl(GMP) 0.06 0.06 0.09 0.21

GMP は当然として python も結構速いです。python は乗算に Karatsuba 法を実装しているようです。perl の bigint は圧倒的に遅いです。100 秒超えたら N/A です。

以下ソース。n を数字に置き換えてください。

# ruby
5**n
# python
5**n
# perl (bigint)
use bigint;
5**n;
# perl (GMP)
use Math::BigInt lib => "GMP";
Math::BigInt->new(5)->bpow(n);

実験 2: 5 の累乗の表示

実験 1 の数字を 10 進表示するのにかかる時間を調べました。多倍長整数を文字列化するということは基数変換するということであり、これが結構時間のかかる処理なのです。

300001000003000001000000
ruby 0.01 0.05 4.05 42.88
python 0.24 3.16 28.92 N/A
perl(bigint) 0.01 1.74 N/A N/A
perl(GMP) 0.02 0.06 0.21 1.20

やはり GMP が圧倒的ですが、Ruby もかろうじて動きます。Ruby は基数変換に Karatsuba 法を用いているためです (ruby-dev:31323) 。ちょっと手前味噌

以下ソース。上の表の数値は下のソースの実行時間から実験 1 の数値を引いてあります (つまり累乗の計算時間は含みません) 。

# ruby
p(5**n)
# python
print(5**n)
# perl (bigint)
use bigint;
print(5**n);
print "\n";
# perl (GMP)
use Math::BigInt lib => "GMP";
print Math::BigInt->new(5)->bpow(n);
print "\n";

実験 3: 円周率の計算

最後に、多倍長整数を使って円周率を 100 桁、1,000 桁、10,000 桁計算する時間を調べました。

100100010000
ruby 0.03 0.25 5.77
python 0.09 0.13 6.11
perl(bigint) 0.25 3.44 N/A
perl(GMP) 0.11 0.59 6.56

あれほど圧倒的だった GMP がなぜか普通です。もっと大きな桁で威力を発揮するのかな。rubypython はほぼ同じ。bigint はやっぱり全然ダメです。

以下ソース。python わからないのでなんだかかっこわるい。GMP の演算は破壊的なので copy() とか必要でうっとうしすぎます。

# ruby
a = b = 10 ** n
(n * 8 + 1).step(3, -2) do |i|
  a = (i / 2) * (a + b * 2) / i
end
puts "3.#{ a - b }"
# python
a = b = 10 ** n
for i in range(n * 8 + 1, 1, -2):
  a = divmod(divmod(i, 2)[0] * (a + b * 2), i)[0]
print("3." + str(a - b))
# perl (bigint)
use strict;
use bigint;

my $a;
my $b;
my $i;

$a = $b = 10 ** n;
for($i = n * 8 + 1; $i >= 3; $i -= 2) {
  $a = int(int($i / 2) * ($a + $b * 2) / $i);
}
$a -= $b;
print("3.$a\n");
# perl (GMP)
use strict;
use Math::BigInt lib => "GMP";

my $a = Math::BigInt->new(10)->bpow(n);
my $b = $a->copy();
my $i;
my $t;

for($i = n * 8 + 1; $i >= 3; $i -= 2) {
  $t = $b->copy();
  $a->badd($t);
  $a->badd($t);
  $t = Math::BigInt->new(int($i / 2));
  $t->bmul($a);
  $t->bdiv($i);
  $a = $t;
}
$a->bsub($b);
print("3.$a\n");

いい加減なまとめ

現状では、気軽に多倍長演算を享受したい時は rubypython がおすすめです。perl の bigint は速度がどうでもいいときだけ使いましょう速度が重要なら GMP とあわせて使いましょう。ソースを書くのが面倒でもそれなりに速く多倍長演算したいときは GMP がよさそうです。

以下追記:

H.I. 2008/01/17 10:09

「use bigint lib => 'GMP'」と書くことができて、GMPで

operator/constant overload をしてくれるみたいです。

との情報をいただきました。Perl では記述性と速度を両取りする選択肢もあるようです。Perl はさすがですね。円周率 10000 桁で試したところ、10 秒でした。GMP を直接たたくより若干遅い *1 ようですが、記述性があがる方がいいですね。

あと、すべて実時間で計測してます。プロセスの初期化時間やコンパイル時間が含まれますので、0.0x のような小さい数値はあてにしないでください。

Appendix

以上の実験を自動でやってくれるスクリプトです。清書してないので読みにくくてごめんなさい。

require "timeout"

RB="./ruby19/local/bin/ruby"
PY="./python30/local/bin/python"
PL="./perl5/local/bin/perl"
LIMIT = 100

puts `#{RB} -v`
puts `#{PY} --version`
puts `#{PL} -v`.split("\n")[1]
puts

def test(prog, src, offset = 0)
  open("test-code", "w") {|fh| fh.print src }
  pid = fork
  unless pid
    $stdout.reopen(open("/dev/null", "w"))
    Process.setrlimit(Process::RLIMIT_CPU, LIMIT + 10)
    exec(prog, "test-code")
  end
  t = Time.now
  Process.wait
  t = Time.now - t
  puts(t > LIMIT ? "n/a" : "%3.3f" % (t - offset))
  t
end

def test_rb(src, offset = 0)
  print "ruby: "
  test(RB, src, offset)
end

def test_py(src, offset = 0)
  print "python: "
  test(PY, src, offset)
end

def test_pl(src, offset = 0)
  print "perl(bigint): "
  test(PL, src, offset)
end

def test_plg(src, offset = 0)
  print "perl(Math::BigInt::GMP): "
  test(PL, src, offset)
end

[30000, 100000, 300000, 1000000].each do |n|
  puts "5^#{n}"
  trb = test_rb "(5**#{n})"
  tpy = test_py "(5**#{n})"
  tpl = test_pl <<SRC
use strict;
use bigint;
5**#{n};
SRC
  tplg = test_plg <<SRC
use strict;
use Math::BigInt lib => "GMP";

Math::BigInt->new(5)->bpow(#{n});
SRC
  puts

  puts "5^#{n} with print"
  test_rb "p(5**#{n})", trb
  test_py "print(5**#{n})", tpy
  test_pl <<SRC, tpl
use strict;
use bigint;

print 5**#{n};
print "\\n";
SRC
  test_plg <<SRC, tplg
use strict;
use Math::BigInt lib => "GMP";

print Math::BigInt->new(5)->bpow(#{n});
print "\\n";
SRC
  puts
end

[100, 1000, 10000].each do |n|
  puts "#{n} digits of pi"
  test_rb <<SRC
a = b = 10 ** #{n}
#{n * 8 + 1}.step(3, -2) do |i|
  a = (i / 2) * (a + b * 2) / i
end
puts "3.\#{ a - b }"
SRC
  test_py <<SRC
a = b = 10 ** #{n}
for i in range(#{n * 8 + 1}, 1, -2):
  a = divmod(divmod(i, 2)[0] * (a + b * 2), i)[0]
print("3." + str(a - b))
SRC
  test_pl <<SRC
use strict;
use bigint;

my $a;
my $b;
my $i;

$a = $b = 10 ** #{n};
for($i = #{n * 8 + 1}; $i >= 3; $i -= 2) {
  $a = int(int($i / 2) * ($a + $b * 2) / $i);
}
$a -= $b;
print("3.$a\n");
SRC
  test_plg <<SRC
use strict;
use Math::BigInt lib => "GMP";

my $a = Math::BigInt->new(10)->bpow(#{n});
my $b = $a->copy();
my $i;
my $t;

for($i = #{n * 8 + 1}; $i >= 3; $i -= 2) {
  $t = $b->copy();
  $a->badd($t);
  $a->badd($t);
  $t = Math::BigInt->new(int($i / 2));
  $t->bmul($a);
  $t->bdiv($i);
  $a = $t;
}
$a->bsub($b);
print("3.$a\n");
SRC
  puts
end

*1:全然調べてませんが、Perl のオブジェクトと GMP のオブジェクトを毎回変換してるとかかな?

2007-09-13

[][][] quine 変種あれこれ

quine は極めてる人がいっぱいいるので quine の変種を考えてみました。あんまりいいのを思いつきませんでしたが、誰かがもっと面白いのを考える種になるといいなと思いつつ晒します。


Python -> Ruby -> Perl -> Python .. と回るプログラム。quine っぽいのは python だけなので全然ダメ。

q='print "puts %%(print q(q=%s;exec q).$/)"%`q`';exec q
$ cat quine.rb.pl.py |python |ruby |perl > q
$ diff quine.rb.pl.py q

Hello, world! 。標準エラー出力に 1 文字だけ出力したら、残りを出力するプログラムを出力して終了します。

"Hello, world!\n".instance_eval q=%q(STDERR.putc c=self[0];puts (self[1..-1]+c.
chr).dump+%(.instance_eval q=%q(#{q})))
$ ruby quinehello.rb
H"ello, world!\nH".instance_eval q=%q(STDERR.putc c=self[0];puts (self[1..-1]+c.
chr).dump+%(.instance_eval q=%q(#{q})))

$ cp quinehello.rb q.rb; while ruby q.rb > q2.rb; do mv q2.rb q.rb; done
Hello, world!
Hello, world!
Hello, world!
...

上とほとんど同じですが、brainfuck インタプリタ。1 命令だけ実行して、残りを実行するプログラムを出力して終了します。1 行目の配列が、現在の実行位置、現在のポインタ位置、現在のテープ状態を表します。こんな風にプログラムを書いておけばプロセスマイグレーションがとても簡単ですね (笑)

[0,0].
instance_eval a=%q(c,f,*t=self;t[f]||=0;eval({?>=>'f+=1',?<=>'f-=1',?+=>'t[f]+=
1',?-=>'t[f]-=1',?[=>'t[f]==0&&(d=0;(c+=1;d+={?[=>1,?]=>-1}[n[c]]||0)while d>=0
)',?]=>"d=0;(c-=1;d+={?[=>-1,?]=>1}[n[c]]||0)while d>=0;c-=1",nil=>"exit 1;;;",
?,=>'t[f]=STDIN.getc',?.=>'STDERR.putc t[f]',}[(n=DATA.read)[c]]||"");$><<("%p.
"%[[c+1,f]+t])+"instance_eval a=%q(#{a})\n__END__\n"+n)
__END__
$ cat hello.bf
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

$ time (cat quinefuck.rb hello.bf  |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |ruby |
ruby |ruby |ruby; echo)
Hello, world!

real    0m9.715s
user    0m3.370s
sys     0m6.250s

2007-08-09

[][]後方参照のある正規表現の能力

定期的に出てくる話題ですが、プログラミングで出てくる正規表現は正規表現ではないので、素数判定ができます。正確には、文字列の長さが素数かどうかを判定できます。2 文字以上のマッチが 2 回以上出現するかどうかを見ます。後方参照がポイント。

p (2..30).select{|x| !("X" * x)[/^(..+)\1+$/] }
  #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

ところで、{ a^n | n は素数 } は文脈依存言語のはずなので、後方参照のある正規表現は線形拘束オートマトン以上の表現力を持つことになるのでしょうか。でも、文脈自由文法である { a^nb^n | n は自然数 } や括弧の対応は書けなさそうです。ちょっと調べてみても、後方参照のある正規表現の能力はよくわかりませんでした。


とりあえずPerl の正規表現マッチングで 3-CNF-SAT が解けるそうです。つまり NP 完全。別に 3-CNF でなくても CNF なら同じ方法でできる気がします。(x_1 ¥vee x_2) ¥wedge (x_1 ¥vee ¥bar{x_2}) ¥wedge (¥bar{x_1} ¥vee ¥bar{x_2}) (wikipedia より) を判定するマッチングは以下の通り。頭いいなあ。

str = "xx;x,x,x,"
re = /^(x?)(x?)x*;

    (\1|\2),    (?# (x1 || x2) )
    (\1|\2x),   (?# (x1 || !x2) )
    (\1x|\2x),  (?# (!x1 || !x2) )

$/x

str[re] #=> 充足可能ならマッチング成功、不能ならマッチング失敗

任意の CNF の充足可能性問題を文字列と正規表現に変換するプログラムも載っていましたが、Perl は読めないので Ruby に書き直してみました。

def regex_sat(v, clauses)
    # v : 変数の数
    # clauses : 論理式、x1 and x2 and (not x3) を [1, 2, -3] と書く

    str = "x" * v + ";" + "x," * clauses.size
    re = "^" + "(x?)" * v + "x*;"
    re +=
        clauses.map do |xs|
            "(" +
            xs.map {|x|
                "\\" + (x > 0 ? x.to_s : (-x).to_s + "x")
            end.join("|") +
            "),"
        end.join
    re += "$"
    re = Regexp.new(re)

    str[re] && $~[1..v].map {|x| x == "x" }
end

# (x1 || x2) && (x1 || !x2) && (!x1 || !x2) の判定
p regex_sat(2, [[1, 2], [1, -2], [-1, -2]]) #=> [true, false]
# x1 = true かつ x2 = false で充足可能

# (x1 || x2) && (x1 || !x2) && (!x1 || x2) && (!x1 || !x2) の判定
p regex_sat(2, [[1, 2], [1, -2], [-1, 2], [-1, -2]]) #=> nil
# 充足不能