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インストールできるものです。

2009-06-16

[][] Re: ’,’.join() がなぜキモイのか

ref: http://d.hatena.ne.jp/methane/20090615/1245025996

よいまとめ。Ruby の Array#join は

  • 1. 自然言語の文法とあわないのがキモイ
  • 2. 勝手に型変換 (to_s) するのがキモイ
  • 3. 文字列べったりのメソッドが Array にあるのがキモイ
  • 4. Enumerable ではなく Array なのがキモイ

ということのようです。


1 については、ぼくに英語の感覚がないせいか、どっちでも特に違和感はないです *1Ruby というと英語風 DSL が有名ですが、Ruby 自体は英語文法とのアナロジーをそれほど意識してないと思います *2

2 と 3 については全くその通りで、Rubyist から見ても Array#join に違和感はあります (ぼくだけ?) 。

4 については、Enumerable#join は提案されたことがあるみたい (ruby-talk:143305) ですが、「Enumerable は無限列の場合もある」「Enumearble は順序が保証されない」というあたりが引っかかってうやむやになったみたいです。


違和感があっても Array#join がいいと思う理由は

Arrayのメソッドチェーンを作ってキモチイイと悦ぶ

に尽きます。配列をぐねぐねいじって最終的に join で文字列化するという処理は頻出だと思いますが、

ary.transpose.flatten(1).map { ... }.each_cons(2).map { ... }

まで書いて、いざ文字列化するというとき。Array#join だと

ary.transpose.flatten(1).map { ... }.each_cons(2).map { ... }.join(",")

と続けて書いて終わりですが、','.join だと

",".join(ary.transpose.flatten(1).map { ... }.each_cons(2).map { ... })

# または

ary = ary.transpose.flatten(1).map { ... }.each_cons(2).map { ... }
",".join(ary)

となり、面倒です。あと見通しも悪くなる。というわけで正しさより便利さですね。うーん、やっぱりぼくの意見は Rubyist 一般の意見ではないかも。


そういえば、「文字列はよく使うから特別」ということで Array#join が許されるなら「数もよく使うから特別」ということで Array#sum を許してほしい。

*1RubyPython も元ネタは Perl の join かと思うんですが、Perl は join(区切り文字, 配列) ですね。英語ネイティブにとってはこの語順が自然なのかな。

*2:例えば Array#delete なんか説明が難しいと思います。「配列 delete (its elements that equal to) 引数」だろうか。それほど難しくなかった。

2008-11-02

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

ruby 1.9 は ruby 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

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

  • 抽象構文木をたどるだけの ruby 1.8 と php は速い *2
  • 抽象構文木をたどるだけだけどパーサがややこしそうな perl はやや遅い *3
  • バイトコードにコンパイルする ruby 1.9 と python は遅い

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

まとめ

まあ、速度なんてどうでもいい話題な上に、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:それだけ難しいことをしていないという説も?

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

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

2008-09-22

[] base64.py が RFC 違反をしている件

Python の base64.py はマニュアルででかでかと RFC 3548 をうたっているのですが、全然準拠できてないことに気づきました。

RFC 3548 には

   Implementations MUST reject the encoding if it contains characters
   outside the base alphabet when interpreting base encoded data, unless
   the specification referring to this document explicitly states
   otherwise.  Such specifications may, as MIME does, instead state that
   characters outside the base encoding alphabet should simply be
   ignored when interpreting data ("be liberal in what you accept").
   Note that this means that any CRLF constitute "non alphabet
   characters" and are ignored.

とあり、要するに「base alphabet でない文字が混ざってるエンコード文字列を解釈しようとしたら拒絶しろ (ただし仕様として明記すれば他の挙動でも可)」という感じ *1 。しかるに

$ ./python3.0
Python 3.0rc1 (r30rc1:66499, Sep 22 2008, 21:33:51)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import base64
>>> base64.standard_b64decode(b'Y!"#$%&()-^~\\|[]@;:<>,.?_\nQ==')
b'a'

思いっきり許容 (無視) してる。マニュアルにそれっぽい断りは書かれてないのに。

RFC 3548 中の MUST はたった 3 つなのに守れてない base64.py に失望した!それをチェックせずに添付してる Python に失望した!

いい加減な子がミスしても評価は変わらないけど、しっかりした子だと思われてる子がミスすると一気に評価が下がるのです。


ちなみに他の言語の状況は。

*1:万が一ぼくの解釈が間違ってたらやさしく教えてね!

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 のオブジェクトを毎回変換してるとかかな?