天泣記

2015-04-09 (Thu)

#1 in-place radix sort

ふと、in-place で radix sort ができるか調べてみると、1bit 単位で quick sort みたいなことをすればできるようだ。

試しに書いてみた。

def inplace_radix_sort(ary)
  max = 0
  ary.each {|v|
    unless v.is_a? Integer
      raise ArgumentError, "non-integer element"
    end
    if v < 0
      raise ArgumentError, "negative integer"
    end
    if max < v
      max = v
    end
  }
  inplace_radix_sort_internal(ary, 1 << (max.bit_length-1), 0, ary.length-1)
  ary
end

def inplace_radix_sort_internal(ary, mask, i0, j0)
  if mask == 0
    return
  end
  i = i0
  j = j0
  while i <= j
    if ary[i] & mask == 0
      i += 1
    elsif ary[j] & mask != 0
      j -= 1
    else
      ary[i], ary[j] = ary[j], ary[i]
      i += 1
      j -= 1
    end
  end
  # assert i == j+1
  mask >>= 1
  inplace_radix_sort_internal(ary, mask, i0, i-1)
  inplace_radix_sort_internal(ary, mask, j+1, j0)
end

ary = (0...10).to_a.shuffle
p inplace_radix_sort(ary) #=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

再帰の深さは最大要素のビット数で、それぞれの深さにおいて結局は全ての要素を調べるので、O(n log max) か。

複数ビット単位でやるには、入れ替える前に要素の数を数えておけば可能なようだ。

2015-03-31 (Tue)

#1

Solaris には posix_spawn_file_actions_addclosefrom_np というのがあって、posix_spawn で、ある fd 以降をすべて close することができるようだ。

Mac OS X には POSIX_SPAWN_CLOEXEC_DEFAULT というのがあって、これも余計な fd を close するのに使える。

2015-02-28 (Sat)

#1

以下の本を読んだ。

両方とも、数学を認知科学から考えたような話。

前者は人間以外の動物がどんな能力を持っているかというのが主な話。チュニジアの砂漠アリが、いろいろ歩き回って餌を見つけた後、巣穴へ一直線に戻るという話はおもしろかった。たしかに人間が同じことをやろうとしたら数学を使う必要があるだろうな。

後者は人間の脳のどの部分がどういう働きをしているかという話を調べているというのが主な話。まぁ、初歩的なところは分かりはじめているわけだな。

2015-01-27 (Tue)

#2 Coq の Permutation

順列組み合わせについてもけっこう悩んだ。ふたつのリストが順列組み合わせの関係にあるという Permutation という述語は以下のように定義される。

Inductive Permutation : list A -> list A -> Prop :=
| perm_nil: Permutation [] []
| perm_skip x l l' : Permutat|on l l' -> Permutation (x::l) (x::l')
| perm_swap x y l : Permutation (y::x::l) (x::y::l)
| perm_trans l l' l'' : Permutation l l' -> Permutation l' l'' -> Permutation l l''.

空リストと空リストは順列組み合わせ (perm_nil)、順列組み合わせとなっている l, l' があったときに先頭に同じ要素を前置したものは順列組み合わせ (perm_skip)、長さ2以上のリストで、先頭の2要素をひっくり返したものは順列組み合わせ (perm_swap)、推移律 (perm_trans)

これらで生成されるものが順列組み合わせであることは明らかなのだが、すべての順列組み合わせがこれらで生成できるというのは納得できなかった

納得するまでにけっこう時間がかかったのだが、こういうことだろう。

先頭要素が異なるリスト a::l と b::l' が順列組み合わせなら、l の中には b が入っているはずで、そうすると l と b::l'' が順列組み合わせになるように l'' を選べる。そうやって選んだ l'' を使うと、perm_skip により a::l と a::b::l'' は順列組合わせ。a::b::l'' と b::a::l'' は perm_swap により順列組み合わせ。a::l'' と l' は順列組み合わせのはずなので、perm_skip により b::a::l'' と b::l' も順列組み合わせ。だからひとつ短いリストの順列組み合わせの関係に帰着できる。

ここで、「はず」というのが 2回でてくる。l と b::l'' および a::l'' と l' の順列組み合わせの関係は、リストの長さがひとつ短いものに対する関係なので、帰納法みたいな感じで仮定してよい。というか、これはリストの長さに関する帰納法をやっているわけだよな。

#1 Coq の False

最近、少し Coq を勉強していて、False について納得するのに困難を感じていた。

悩んでいた話を忘れる前に書いておこう。

2014-12-27 (Sat)

#3 端末における反転の使い方

結局、端末で反転 (文字の背景をデフォルトではない色にすること) はとても目立つため、いちばん目立ってほしいところに使うのは問題ないけれど、それ以外の場所に使うと(とくに使いすぎると)そっちが目立ってしまってよろしくない、という話なのだろう。

#2 test-unit の色の改善

と、書いたら、すとうさんがかなり直してくれて、以下のようになった。

result-latest.png

ここで目立っているものは以下の順だろう。

  1. 最後のサマリ行
  2. 失敗した行
  3. Failure

最後のサマリの行はユーザから見るといつもそこにあるので、ここまで目立たなくてもいいと思う。

失敗した行と Failure はどちらも失敗と対応している。どちらかが十分に目立てば、もっとも目立つものと失敗が対応することになる。

すとうさんは実際に失敗したところが気になるということなので、失敗した行のほうが目立つのは理にかなっているのだろう。

というわけで、その意図を進めるのであれば、サマリ行と Failure をもうちょっと目立たないようにするのがよいのではないか。

#1 test-unit の色の使い方はよくない

Ruby 2.2 から、(Ruby の外部で) require 'test/unit' とすると gem の test-unit が使われるようになって、しばらく使っていたのだが、どうも出力から素早く情報を読み取れない。

最初は慣れていないせいかな、と思っていたのだが、時間がたっても相変わらずで、これはたぶん出力が良くないのだということで、すこし真面目に考えてみた。

以下のテストを考える。

% cat tst.rb
require 'test/unit'

class C < Test::Unit::TestCase
  def test_a
    assert_equal(1, 2)
  end

  def test_b
    assert_equal(1, 1)
  end

  def test_c
    assert_equal(1, 3)
    raise
  end
end

これを Ruby 2.1 と Ruby 2.2 で比較してみた。

出力からまず読み取れる情報はまず個々の文字よりも大きな形や色である。というわけで、出力をぼかしてみてみよう。

Ruby 2.1 では以下のような結果になる。

result-210-blur.png

Ruby 2.2 では以下のような結果になる。

result-220-blur.png

これからいくつかのことがわかる。

テストが失敗した時には、たいていの場合、結局はぜんぶ直すわけだが、どのテストから直すかという選択は必要で、そのためにそれぞれの失敗を眺めることになる。そのときに、個々の失敗をすばやく認識できるとありがたい。Ruby 2.1 ではもっとも目立つ部分が失敗と対応していてそれが容易だったが、Ruby 2.2 ではもっとも目立つ部分は失敗と対応しなくなっていて、これはよくないと思う。結局のところ、テストの結果の表示は、失敗の並びなので、もっとも目立つ構造を個々の失敗が対応していないというのは結果の構造の認識を困難にしている

思うに、色の使い方はずいぶんと改善の余地があるのではないだろうか。

なお、ぼかさない結果は以下のようになる。

result-210.png

result-220.png

これをみると、Ruby 2.2 で出力が大きいのは、失敗した場所のソースを表示していること、予期された結果と実際の結果を 2回 (... expected but was ... と diff で) 表示しているのが原因である。

ソースの表示は、役に立つこともあるだろう。

結果を 2回表示しているのは、このケースではほぼ同じ情報を 2回表示しているだけで役に立っていない。役に立つ場合もあるのだろうが、役に立たない場合は表示しないでくれるとよいのだが。

考えた結果、個人的にもっとも気に入らないのは色の使い方で、失敗をすばやくみてとるのに不適切ということだと感じられる。

2014-12-12 (Fri)

#1

もしかすると、Ruby に16進小数を入れても実際的な非互換性は生じないのかもしれない。

16進小数というのは 0x123.456 みたいなものである。

16進なので a-f も使えて、0xabc.def みたいなこともできる。

16進小数の利点は、浮動小数点数を正確かつコンパクトに表現できることである。IEEE754 の浮動小数点の仮数部は 2進数なので、これを桁を合わせて 16進にしたものが 16進小数で、浮動小数点数を正確に指定したいというときに役に立つ。

ここで問題になるのが、現在 0xabc.def は 0xabc という整数 (2278) に対する def メソッドの呼び出しとして解釈されるので、これを 16進小数として解釈する (0xabcdef / (16**3).to_f つまり約2748.8708) と、意味が変わってしまうので非互換になる、という点である。

この非互換性は実際に問題になるだろうか。

まず、現在 Integer クラスには 16進数に使える文字 ( 0-9a-fA-F に加えて区切りの意味で _ も使える) だけで構成されているメソッドは存在しない。

% ruby -e 'p Integer.instance_methods.reject {|n| /\A[0-9a-fA-F_]+\z/ !~ n.to_s }'
[]

しかし、Ruby では既存のクラスにメソッドを付け加えることができる (オープンクラス) ので、もしかしたら既存のコードが付け加えて使っているかもしれない。

そこで、既存の gem を全文検索してちょっと調べてみる。(1ヶ月くらい前に gem mirror して得た gem の各最新版を展開して milkode で全文検索できるようにしてある。)

% gmilk -s rb 0x|egrep '0x[0-9a-fA-F_]+\.[a-fA-F_][0-9a-fA-F_]*([^0-9a-zA-Z_]|$)'
Because number of records is large, Milkode use external tool. (Same as 'gmilk -e grep')
/extdisk/akr/ruby/rubygems/latest-gems/gnu_mpc-0.9.0/spec/atan_spec.rb:107:    expect(actual.imag).to eq GMP::F.new("-0x8.a7e33db93ecf18@-34", 57, 16)
/extdisk/akr/ruby/rubygems/latest-gems/metasm-1.0.1/tests/preprocessor.rb:263:              t_float['0x1.e4']

ひっかかったのは文字列の中だけなので、どうやら、16進小数とみなしうるコードは既存の gem の中にはないようである。

また、Ruby 2.1 から数値には i (虚数) と r (有理数) という suffix がつけられるようになったが、これらは a-f の範囲外なのでこれも衝突しない。

これは使えるようにしちゃってもいいのかもしれない。

2014-11-30 (Sun)

#2 Casuistry

読んだ後、検索していて、トゥールミンの議論モデルの変容 --- 批判から寛容へ --- を見つけて読んだ。これもおもしろい。

トゥールミンの新しい著作で、モデルから裏付けがなくなっているのはなぜか、という話。

ある推論規則が適用可能であることに合意するためには、裏付けが論拠を正当化することを合意しなければならず、それが受け入れられなければ合意できない、という状況ばかりではない、という話だと理解した。

ものごとの見方・考え方が異なるひとは、裏付けと論拠の関係を合意することは無理なことがあり、それでも合意を行うにはどうしたらいいか。

そういうひとでも個々の典型的な状況については合意が可能な場合、微妙な状況についての合意は無理でも、典型的な状況について一般化された合意は可能という話だと理解した。この合意は裏付けと論拠の関係について合意したわけではないが、それでも合意の一種ではある。

で、その方法が Casuistry というものらしい。(日本語だと決疑論)

しかし、そもそもなんで裏付けを共有していないのに典型的な状況について合意が可能なのか考えると、この話が医療倫理あたりの話からきているからかな。そのあたりは、もともと個々の事例から (直接に、あるいは文化などを経由して) 個人の倫理が作られるだろうから、典型的な事例についてはその良し悪しは個人に依存せずに決まる、つまり、個人がどのような裏付けをもとに判断しているかには依存しないのだろう。

#1 トゥールミンの「議論の技法」

最近、トゥールミンの「議論の技法」を読んだ。

ふつうの主張や議論は、論理学では扱えない話のほうが多い、ということを延々と書いてある、という感想を持った。

論理学では前提から結論を導く方法を論じているわけだが、現実で問題になるのはそもそも前提が正しいかどうかだ、という話。

論理学で要求されるような完全に正しい前提は、とくに「すべての X は Y」というような形(全称)の推論規則については現実世界にはほとんどない、ということが主張されていたように思う。

まぁ、たとえば「すべての人間は死ぬ」とかでもこれが論理学の意味合いで正しいということをいうのは難しい。

この規則についていえば、正しいということはいえないけれど、だいたいのひとにとってはこれを納得するのは簡単だ。だから、納得したひと同士であれば、「ソクラテスは人間である」「すべての人間は死ぬ」というふたつから、「ソクラテスは死ぬ」という結論を得て合意することができる。

もちろん、「ソクラテスは人間である」というほうも納得しないといけないけれど、そちらは全称でないため難しくない。

一般化すると、ある主張に使われている前提を受け入れている人とは合意が可能だ、ということになる。

全称の推論規則はかならずしも全員が納得するかどうかは難しい場合もあるので、これを分解して推論規則自体(論拠W)と、それが正しいと思われる理由(裏付けB)に分割して、その違いを意識するように強調している、というのがトゥールミンモデルかなぁ、と思った。(推論規則が完全ではないため結論も完全ではなく、「だいたい」などといった限定Q と、結論が成り立たない例外Rも必要になる。)

「すべての人間は死ぬ」という推論規則の裏付けは... 生きている人間はたくさん居るので、(人間が絶滅するまでは) すべてのケースについて正しいということは確認できない。それなのになぜ納得できるのか考えてみると「200歳まで生きた人間の記録がない」とか「不死を求めた権力者も結局死んでいる」とか、そういうあたりかなぁ



田中哲