天泣記

2016-02-01 (Mon)

#1 RUBY_ で始まる定数の利用状況

ふと、RUBY_VERSION などの定数がどのくらい使われているのか数えてみた。

まず、そういう定数はいくつあるのだろうか。 all-ruby で調べてみる。

% all-ruby -e 'p Object.constants.collect {|x| x.to_s }.delete_if {|x| /\ARUBY_/ !~ x }.sort.join(" ")'
...
ruby-1.3.4-990531     ""
ruby-1.3.4-990611     "RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_VERSION"
...
ruby-1.8.5            "RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_VERSION"
ruby-1.8.5-p2         "RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_VERSION"
...
ruby-1.8.7-preview4   "RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_VERSION"
ruby-1.8.7            "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_VERSION"
...
ruby-1.8.7-p374       "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_VERSION"
ruby-1.9.0-0          "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION"
...
ruby-1.9.0-3          "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION"
ruby-1.9.0-4          "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_ENGINE RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION"
...
ruby-2.2.4            "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_ENGINE RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION"
ruby-2.3.0-preview1   "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_ENGINE RUBY_ENGINE_VERSION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION"
...
ruby-2.3.0            "RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_ENGINE RUBY_ENGINE_VERSION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION"

とりあえず減ったことはないようなので、Ruby 2.3.0 にあるものだけ考えればいいようだ。

gem-codesearch で検索して数えてみる。

% for w in RUBY_COPYRIGHT RUBY_DESCRIPTION RUBY_ENGINE RUBY_ENGINE_VERSION RUBY_PATCHLEVEL RUBY_PLATFORM RUBY_RELEASE_DATE RUBY_REVISION RUBY_VERSION
do
echo -n "$w: "
gmilk -e grep -s rb -a $w|grep "\\<$w\\>"|wc -l
done
RUBY_COPYRIGHT: 32
RUBY_DESCRIPTION: 467
RUBY_ENGINE: 2800
RUBY_ENGINE_VERSION: 34
RUBY_PATCHLEVEL: 681
RUBY_PLATFORM: 10993
RUBY_RELEASE_DATE: 493
RUBY_REVISION: 91
RUBY_VERSION: 23099

RUBY_VERSION がいちばん多くて、次が RUBY_PLATFORM のようだ。

RUBY_ENGINE もそこそこ多いな。CRuby 以外を考慮する人もそこそこいるのだろう。

2016-02-08 (Mon)

#1 条件分岐の心理

ちょっと妄想した。

• プログラミングの条件分岐 (if 文とか) とロジカルシンキングの MECE (Mutually Exclusive and Collectively Exhaustive) で記述することはほぼ同じ。
  • 従って、人間の思考に対して似た効果があるのではないか。
  • if 文を書くときに、分岐のどちらかの内容を考えていなかったことに気がつくことは、たまにある。つまり if 文には分岐のそれぞれに注意を向けさせる効果がある。
  • MECE な分析もそれぞれの場合に注意を向けさせる効果はあるのではないか。
  • SWOT分析だの3C分析だの、いくつかの枠があってそれぞれに記入させるという類は、どれも似たような効果を狙っているのかもしれない。(条件が固定されているのはそういう条件が有用であることが多いという経験則なのだろう)
• 例外は、例外的なことが起こったかどうかで分岐する機構である。
  • 例外的な場合の記述を後まわしにすることで、例外的でない状況に集中できる。
  • 例外的な状況に強制的に注意を向けさせる機構も存在する。(Java の checked exception)
• オブジェクト指向の遅延束縛も分岐とみなせる。
  • 各具象クラスを書いているあいだは、そのクラスだけに注意を向けていればよく、他のクラスへ注意を向ける (思考をコンテキストスイッチする) 必要がない。
• 関数型の高階関数も分岐とみなせる。
  • とても柔軟なので、用途を限定せずになにか言うのは難しい。人間の注意を制御するツールとして使えるだろう。

2016-02-23 (Tue)

#1 範囲を指定した乱数の生成

「PHP の壊れた mt_rand の品質を統計的に検証した」の最後に「mt_rand が奇数しか生成しない（値域の指定によっては）」という話があって、ちょっとまわりを見回してみた。

とりあえず php はそこで示されているように、mt_rand(1, PHP_INT_MAX) が常に奇数を返す。

% php -r 'for ($i=0;$i<10000;$i++) { echo mt_rand(1, PHP_INT_MAX)."\n"; }'|
ruby -e 'ARGF.each {|line| p line.to_i.odd? }'|uniq
true

なお、PHP_INT_MAX は 9223372036854775807=2**63-1 である。

% php -r 'echo PHP_INT_MAX."\n";'
9223372036854775807

以下のように PHP の mt_rand(1, PHP_INT_MAX) の結果を 2進数にすると、なにが起きているのかわかりやすい。

% php -r 'for ($i=0;$i<20;$i++) { echo mt_rand(1, PHP_INT_MAX)."\n"; }'|
ruby -e 'ARGF.each {|line| printf "%.64b\n", line.to_i }'
0101110100010011011010101100110000000000000000000000000000000001
0000100111100101000111010010001100000000000000000000000000000001
0000000000010001100101101110110000000000000000000000000000000001
0001111011000111101001100100000000000000000000000000000000000001
0110011000101000111111011001000100000000000000000000000000000001
0011100011010101010000011101101000000000000000000000000000000001
0010000010011001100001001101010000000000000000000000000000000001
0111001101001100010101001110101100000000000000000000000000000001
0110101111111100010011111001110000000000000000000000000000000001
0000001011010101101111001111110100000000000000000000000000000001
0110011011010100011000100001100100000000000000000000000000000001
0010111100000011100000000111110100000000000000000000000000000001
0111000011011101111110000110001100000000000000000000000000000001
0101101111111111000011110010000000000000000000000000000000000001
0100101001101100101000100101001100000000000000000000000000000001
0100001110111100101011111011010100000000000000000000000000000001
0001111110111111101010111100011000000000000000000000000000000001
0110000001011100001010010110001100000000000000000000000000000001
0000011000100010110101010101101100000000000000000000000000000001
0110111000100111011011101010001100000000000000000000000000000001

乱数は 31bit であって、それを [1,2**63) の範囲に引き伸ばしているので、下位ビットはだいたい 0 になってしまい、最下位だけは下限 (第一引数) が 1 なので 1 になる、というわけである。

第一引数を 0 にすれば [0,2**63) の範囲になって以下のようになる。

% php -r 'for ($i=0;$i<20;$i++) { echo mt_rand(0, PHP_INT_MAX)."\n"; }'|
ruby -e 'ARGF.each {|line| printf "%.64b\n", line.to_i }'
0100101111100111100110110100000100000000000000000000000000000000
0111000010101110011110110111110000000000000000000000000000000000
0111010111001010000010101101011000000000000000000000000000000000
0011100111110100101011001011001100000000000000000000000000000000
0100000000001101010111001010101100000000000000000000000000000000
0010101111001011110000011100100100000000000000000000000000000000
0111110001001000000110111010110000000000000000000000000000000000
0011101000100101111100100110001100000000000000000000000000000000
0010010000000101100110001100101100000000000000000000000000000000
0100110011101011111100010100110000000000000000000000000000000000
0111011000111011110010001011101000000000000000000000000000000000
0111111001110010110001001110111100000000000000000000000000000000
0111110110111010010101100011101100000000000000000000000000000000
0111111001110111111110110100110100000000000000000000000000000000
0011110011111100100001000000001000000000000000000000000000000000
0111111011001001101101110111101100000000000000000000000000000000
0100111001000111101111100011111000000000000000000000000000000000
0110011010111000011001001110101100000000000000000000000000000000
0000101101001000100000011110100100000000000000000000000000000000
0111110110101110011111001100001000000000000000000000000000000000

31bit の乱数に範囲の大きさを乗じて結果を求めればこうなるという話だな。

いくつか調べてみると、perl が同じような動作である。

% perl -e 'for ($i = 0; $i < 20; $i++) { printf "%.53b\n", rand(2**52) }'
00000110001001110010011010110001101010001000000010000
01010001110110000101110001111110001100011011110000000
01101000010110111010001110111010000101010001000110000
01111011010001011111111001001010101100010111100100000
00001001011000111110101011001100010001101000101010000
00111110101100000010001100001000011101111111111000000
01101100010010110110100010010001010010110010101110000
00111001000010001001010010000000000101101000101100000
01101000011010101010000011101110011110110011010010000
01010100101101000110001110100001101000000110000000000
01000110010001001011101001100111100010001110010110000
01110111011000010001101110100101011110101011110100000
01110101110111010111110111110111000100000111111010000
01100001000001000000001010100001101011001110001000000
01101010011100111011110010000001101010000011111110000
01001111010011110110101111100111101100000000111100000
01110100010100010110100110100111011100000110100010000
01110111011101110010101010011110101111111000010000000
00100000000010001100101101011000001000110011100110000
00011110010110111001101000101110101010001000000100000

乱数は 48bit のようだ。おそらく drand48 で生成されているのだろう。

pp.c の pp_rand のところをみると、これは結局 rand(n) は n * Drand01() と計算されている。ここで Drand01() は [0,1) な乱数を返す関数で double を返す。Drand01() は drand48() / 2**48 になっているのだろう。そのため、2**52 * (drand48() / 2**48) というのは結局 2**4 * drand48() になって、整数を2**4倍しているから下位4bitは0になるのである。

こういう、一定の範囲の乱数を生成するやりかたは、剰余を使うやりかたもある。mruby はそのようである。mruby の (mruby-random の) random.c をみると、rand(max) は mt_rand(t) % mrb_fixnum(max) と計算されている。mt_rand は [0,2**32) な範囲の整数の一様乱数を返す関数である。max のほうは mrb_fixnum(max) となっていて、手元の環境では、2**31-1 までの値しか渡せないようだ。

剰余を使うと、下位ビットが0に固定されることはない。しかし、上位ビットに問題が出てくる。極端な話、乱数の最大値よりも大きな範囲を扱おうとすると、剰余は乱数そのものを返すことになるので、大きな値が返ってこない。

mruby の場合は fixnum の制約によりそういう範囲は渡せないが、それでも確率的な偏りが生じる場合がある。以下のように、rand(1717986918) を繰り返し呼んで数えると、前半 (858993458以下) は後半 (858993459以上) に比べて 1.5倍の確率になってしまう。

% bin/mruby -e 'n = 1717986918; a = [0]*4; 10000.times { r = rand(n); a[r / n * 4] += 1 }; a.each {|n| puts "*" * (n / 100) }'
*****************************
******************************
*******************
*******************

1717986918 というのは、じつは 2**32 * 0.4 である。(これは 2**31-1 以下なので指定できる。) rand(n) は内部的に [0,2**32) の範囲の乱数を n で割って余りを得るわけだが、ここではさらに n で割って 4 を掛けて、0 から 3 までの値に変換している。これは結局、[0,10) の範囲の乱数を 4 で割って余りをとるのと同じような性質になる。簡単のためにそっちで説明すると、[0,8) の範囲の乱数を 4 で割って余りをとれば一様になるだろうが、[0,10) では一様にはならないという話である。8 と 9 が返ってくる場合があるので、それらは余りが 0 と 1 になり、前半の確率を押し上げることになる。

まぁ、php, perl, mruby のいずれにせよ、かなり大きな範囲を指定しないと明瞭な症状は出てこないが、変といえば変である。

ならどうすれば直せるのか、というと、Python がわかりやすい。Python の random.py の _randbelow をみると、いろいろ場合分けがあるが、(おそらく) 簡単なケースでは以下のコードが動作する。

k = n.bit_length()  # don't use (n-1) here because n can be 1
r = getrandbits(k)          # 0 <= r < 2**k
while r >= n:
    r = getrandbits(k)
return r

これは、[0,n) な整数の乱数を生成するコードだが、n が k ビットとして、k ビットの乱数で n 未満なものが求まるまで繰り返す。まず、乱数を生成するときに k ビットと指定することで、十分な桁数の乱数を生成することができ、(php や perl と異なり) 下位ビットが 0 になってしまうことを防げる。そして、半端な値は捨てて再挑戦することにより、半端でない範囲の乱数を扱っていることになり (mruby とは異なり)、一様な乱数が得られる。

以下のようにすると、ちゃんと下位ビットまで乱数が生成されていることがわかる。

% python3 -c 'import random
for i in range(20) : print(random.randint(0,2**100))'|
ruby -e 'ARGF.each {|line| printf "%.100b\n", line.to_i }'
1000101000000100100111000110100001110101000010101111011001000111110101101111111011101111101010000110
0000011111101011010010011101001110000000110110110011110100101010001000100111011000110111010010011011
0001111101100111010111001011111001101000011100101010100111011110011010111001111001110001011101111111
0000111000001001001111101101100101000110000001010010011101101110111000101001001011101111000010000111
0110000100001000000101001000001011101111000000011011101101110111010010011001001000100000110010100001
1000011011110111000101000010000101111100101000011110001010010110010110111110000010111000001001101110
0110010011100101000010000100011001011100010110000000100101011010101110100001101010110000011000111111
0000110111001011110100111110110111101110100111001011111000000110010111101000010101010011101110001001
1001111100100010011111111110010001101111010011001110101100001101100001100001011111110111001110101010
0110011001010101111001110101010001011001010011101000010101100010011111111010010011110101001000010111
0101001110000010001010101010011111101110011011110010110010101011101110010100101001111111000011001000
0100010010110011010010110011101111110001001111010010111111010110111101011110011101010001111011110011
1011100010000010110110011111010000001001001000011001111000101000100011100010000111001101110011101010
1011001011010111001110111100010010011101000000110111100111110001101100101010001010110111100011100101
1001101010001101010111001010100111100010001110010111011100001011010011001011101011001100100011111100
0111110011100011100101000111011101001100010001101001100000101101101101110001001110111110100111011011
0100101010110011110000000100110001111110110110101000111001001111001011110001011010011100111101010101
1010011111101000110010001111010100000101011110001111110101100010000001011110111011100111110000100001
0100111000010101000001010010011101101000110101011101011110011110010101000000101011101011111100000010
0111010011011100100000001000110000011110000010000100000000110000100011100111001000101000110000001010

なお、Ruby も (C で書いてあって少しわかりにくいが) Python と同様な処理をしている。(昔自分で直した話なので覚えている。)

% ruby -e '20.times { printf "%.100b\n", rand(2**100) }'
1000111000110111101010000000111110101110111010100010100101111010110001001111011111010010001010010100
1010111101000110001011010101111111010000001110100001101101001011000100000110100011101111110010001001
0000110100101000011010110111000110000111110001100101101011100010011110101010101011000001110111100101
1011110100011101110111010100101000010000100110111101001101001011000100001001111011101101101010110100
1100100001011000101010101001001110111011111011000110101011011111111000101010010110001101011010111100
1000010011111101101100010000110011101110010011100101001111000001011001110001100101011011011011000011
0011001001000111011111001010011101000001110010111110111110010110011001111110010101000000001001000110
1101110110101001001011111101011100000001110110010100101100110010001001011101101110111100001001111110
0010110010001011110101001100000001000101011100101111001111010001000110010110011010100101111111001101
1100001100011010101000000110111101110101100111011010110000100001001101001101001110110010000110110001
1111000001010100110111001111011111011000010101011111110010100100101010011101011110001000001100010000
1011110001100011000001011111110100010101001110100000111000101001101010001011101101100001001100110110
1011011101011110000010001100000101001100000110100010101001010000001101100110001000000100101001010010
1010101000100000011010001101111010011011011011011100001001000100011100101000010000010101011100111001
0111101001101001000001111101010100011101111010111000011011100101011111111000101001111111000000101111
1000110000011001001110100101111011001100000011100111011100000010111100111101110110111010011111010010
1010010011110111000011001111000010011011001101111100001011101001110001011110000100011011000000010010
1011001010001111100110110001111100110011100111101011111111101001001111100101001001001011011111100000
1111001101011011101111110001110010011000111110110010100101101101010111111100110001001010100110101000
1101001111001110110110111110111000000111000011101101110111000101101101100010111110000011100101000010

また、OCaml も半端な値について似たようなことをしている。(30bit よりも大きな範囲指定はエラーになる。) OCaml の random.ml に以下のコードがある。

let rec intaux s n =
  let r = bits s in
  let v = r mod n in
  if r - v > 0x3FFFFFFF - n + 1 then intaux s n else v

intaux は、乱数生成器の状態 s と整数 n を受け取って、[0,n) の乱数を返す関数である。bits は [0,2**30) の範囲の乱数を返す関数である。r - v > 0x3FFFFFFF - n + 1 という条件が成り立てば、(tail recursion で) 再度挑戦している。こういう条件にしているのは、再挑戦の数を少なくできるからかな。

試したバージョンは以下のとおり。

% php -v
PHP 5.6.17-0+deb8u1 (cli) (built: Jan 13 2016 09:10:12)
Copyright (c) 1997-2015 The PHP Group
Zend Engine v2.6.0, Copyright (c) 1998-2015 Zend Technologies
    with Zend OPcache v7.0.6-dev, Copyright (c) 1999-2015, by Zend Technologies
% perl -v

This is perl 5, version 20, subversion 2 (v5.20.2) built for x86_64-linux-gnu-thread-multi
(with 45 registered patches, see perl -V for more detail)

Copyright 1987-2015, Larry Wall

Perl may be copied only under the terms of either the Artistic License or the
GNU General Public License, which may be found in the Perl 5 source kit.

Complete documentation for Perl, including FAQ lists, should be found on
this system using "man perl" or "perldoc perl".  If you have access to the
Internet, point your browser at http://www.perl.org/, the Perl Home Page.

% bin/mruby --version
mruby 1.2.0 (2015-11-17)
% python3 -V
Python 3.4.2
% ruby -v
ruby 2.4.0dev (2016-01-04 trunk 53427) [x86_64-linux]
% ocaml -version
The OCaml toplevel, version 4.02.3

[latest]