« 2009年06月 | メイン | 2009年08月 »

2009年07月 アーカイブ

2009年07月05日

Java3DのInterpolatorを使ってみる

アニメーションの制御をしてくれるInterpolatorは、デフォルトの設定で使うなら簡単で便利この上ないのだが、ちょっと思い通りに動作を変えようとすると、途端に調べる事と考える事が増える。お仕着せのシンプルなI/Fは融通が利かないというのは世の常である。簡単に使えるようになっているものでも、結局どういう時にどれくらい便利なのか、不都合な副作用が無いのかどうかを綿密に調べる羽目になることはよくある。

過去に何度か、簡単なアニメーションのためにInterpolatorを使おうとしたが、結局はやりたいことをやる方法がわからなくて、諦めてWakeupOnElapsedTimeを使って時間毎の処理を自前で書くことにしてきた。

しかし、賢い人達が練り上げた、OpenGLより上位のJava3DのI/Fが、不便であるはずが無い。必ず理由があってこのようなI/Fになっているはずである。私はすっかりSUNの信者である。使いこなせば便利で安全で堅牢で可般で最適で信頼性が高いに違いないことは、宇宙の真理として決まっているのである。
それにしてもInterpolatorを使ったアプレットはよくクラッシュする。
という訳で、一度きちんとInterpolatorを使う練習をしてみることにした。

テストアプリの起動ページへ
ソースコード

今回は、
・PositionInterpolator
・RotationInterpolator
・ScaleInterpolator
・ColorInterpolator
・TransparencyInterpolator
を使ってみた。

Interpolatorを使う上で最も多く問題になるのは、おそらく、アニメーションの周期や時間毎の動き方を決めるAlphaが作れるかどうかであろう。一定の速度で一方向に動かすだけなら簡単だが、加速・減速させたり、端まで行ったら折り返したり、端まで行ったら直角に進路変更させたりしようとすると、AlphaのI/Fをよく理解しないといけなくなる。

Alphaのコンストラクタには、一番多いもので10個の引数がある。

Alpha(int loopCount, int mode, long triggerTime, long phaseDelayDuration, long increasingAlphaDuration, long increasingAlphaRampDuration, long alphaAtOneDuration, long decreasingAlphaDuration, long decreasingAlphaRampDuration, long alphaAtZeroDuration)

これの5つ目以降が、移動、加速、減速に関するものである。
Alphaというのは基本的には最小値(default=0.0)から最大値(default=1.0)までの間を動く値である。Alphaの動きは、次のようになる。

時刻速度時刻(パラメータ表記)
(1)最小値0(1)
加速(+)
(2)max(+)(1) + increasingAlphaRampDuration / 2
等速(+)
(3)max(+)(4) - increasingAlphaRampDuration / 2
減速(+)
(4)最大値0(1) + increasingAlphaDuration
停止
(5)最大値0(4) + alphaAtOneDuration
加速(-)
(6)max(-)(5) + decreasingAlphaRampDuration / 2
等速(-)
(7)max(-)(8) - decreasingAlphaRampDuration / 2
減速(-)
(8)最小値0(5) + decreasingAlphaDuration
停止
(9)最小値0(8) + alphaAtZeroDuration

AlphaのmodeがINCREASING_ENABLEの時(default)は(1)-(5)が繰り返され、(INCREASING_ENABLE | DECREASING_ENABLE)の時は(1)-(9)が繰り返され、DECREASING_ENABLEの時は(5)-(9)が繰り返される。
従って、端まで行ったら折り返す、というのは、Alphaのmodeを(INCREASING_ENABLE | DECREASING_ENABLE)にすればできる。

残りの引数については、
loopCount: 繰り返しの回数(-1だと無限)
triggerTime: Alphaが内部で動き始める時刻
phaseDelayDuration: Alphaが内部で動き始めてから値が動き始めるまでの時間
のようである。

続きを読む "Java3DのInterpolatorを使ってみる" »

2009年07月09日

秘書問題の考察(3) 期待順位最小の後ろ向き帰納戦略

前回のエントリーの秘書問題をきちんと解く。

問:以下の条件で、結果としてなるべく順位の高い人が選べるようにするには、どのようにすれば良いか。
・n人の応募者から必ず1人を選ぶ。
・1人ずつ面接し、その場で採用するかどうかを伝える。採用したら、残りの人は面接しない。採用しなければ、その人は2度と選べない。
・応募者は、それまでに面接した人の中で、必ず順位付けされる。応募者の良し悪しは、その暫定順位でしか判断できない。


解:
まず、j番目の応募者の暫定順位(それまでのj人中の順位)がxの時、その応募者が全n人中の何位であるかの期待値を求める。全n人中の順位をyとすると、この期待値は、(順位×確率)の和なので、E(y)=ΣyP(y)のようになる。j人中x位の人がn人中y位である確率は、
1 ...... y ...... n
 ↓
1 ... x ... j
という対応を考えると、j人の組み合わせnCj通りの中で、yの左側(y-1)人の内(x-1)人がxの左側に入って、yの右側(n-y)人の内の(j-x)人がxの右側に入る確率なので、P(y)=(y-1)C(x-1) × (n-y)C(j-x) ÷ nCjである。これを使うと、yの期待値は
¥sum_{y=x}^{n-j+x}y¥frac{¥pmatrix{n-y¥cr j-x}¥,¥pmatrix{y-1¥cr x-1}}{¥pmatrix{n¥cr j}} = ¥frac{n+1}{j+1}¥,x
となるらしい。(参考文献(1)による。この変形は私にはできなかったが、このP(y)は「超幾何分布」の形をしてるので、その知識を使えば簡単な計算で求まるのだと思う。)このE(y)を、以後y(j,x,n)と書く。

次に、最後の応募者の場合から、具体的な手順を考える。j-1番目までの応募者を採用しない時の最終的な採用者の期待順位をR(j,n)とする。
n-1番目までの応募者を採用せず、n番目の応募者を面接する場合、R(n,n)=n番目の応募者の期待順位=1位〜n位の平均=(n+1)/2である。
n-1番目の応募者については、その人が暫定x位の時、その人の最終的な期待順位はy(n-1, x, n)であり、その人を選ばない時の期待順位はR(n,n)である。従って、y(n-1, x, n) ≦ R(n,n)ならその人を採用すれば良いということになる。n-1番目の人がある暫定x位である確率は1/(n-1)なので、min{a,b}をa,bの小さい方とすると、R(n-1,n) = 1/(n-1) * Σ min{ y(n-1, x, n), R(n,n) }と書ける。
これは、n-1番目の応募者に限らず、1≦j<nの全てのjについて同じである。すなわち、j番目の応募者が暫定x位の時、その人の最終的な期待順位はy(j, x, n)であり、その人を選ばない時の期待順位はR(j+1,n)である。従って、y(j, x, n) ≦ R(j+1,n)ならその人を採用すれば良いというのが答である。R(j,n) = 1/j Σ min{ y(j, x, n), R(n,n) }、yを展開すると
¥frac{1}{j}¥sum_{x=1}^{j}min¥left¥{¥frac{n+1}{j+1}x, R(j+1,n)¥right¥}
なので、R(j,n)は末端のR(n,n)から逆向きに帰納的に(backward inductionと言うらしい)計算できる。


n=10の場合、採用する人の期待順位を最小にするために、j番目の人が暫定何位以内ならその人を選べば良いかは、次のようになる。3列目は、その人まで達した時の最終的な期待順位である。


jthresholdR(j,10)
954.28
833.59
723.15
622.89
512.68
412.56
302.56

3人目まではパスし、5人目までは暫定1位なら、7人目までは暫定2位なら、8人目は暫定3位なら、9人目は暫定5位なら採用すれば良く、この戦略による期待順位は約2.56となる。

n=20の場合は次のようになる。


jthresholdR(j,20)
19108.01
1876.62
1755.70
1645.05
1534.56
1434.18
1323.89
1223.64
1123.46
1013.30
913.17
813.06
713.0021
613.0017
503.0017

5人目まではパス、10人目までは1位なら、13人目までは2位なら、15番目までは3位なら(中略)採用すれば良く、期待順位は約3.00となる。

参考文献
(1)「タイミングの数理 最適停止問題」穴太克則 著(朝倉書店)

続きを読む "秘書問題の考察(3) 期待順位最小の後ろ向き帰納戦略" »

2009年07月12日

ソフトウェアリリース問題

秘書問題」の参考文献として図書館から借りた本に、曲がりなりにはソフトウェアに関わっている筆者としては、読んどかないと気になって仕方なくなるに違いない、一際目を引く問題があったので、返却する前に一読した。
「ソフトウェアリリース問題」と呼ばれている、最適停止問題の1つだ。
単純化した概要をメモする。


問1:テストが未実施である、開発中のソフトウェアの全バグ数がBとし、n回目のテストで見つかるバグ数をX(n)とする。BとX(n)の確率分布は既知で、E(X(n))は単調減少とする。見つかったバグは、各回のテスト終了時にコスト0で直ちに直される(バグ修正のコストはテストのコストに含まれる)とする。テスト1回当たりの費用をCt、ソフトウェアリリース後に残されるバグ1件当たりのコストをCb、Ct<<Cbとする時、コストを最小にするには、何回テストしてリリースするのが最善か。


ソフトウェアの開発の仕事をしたことがある人なら1回は考えさせられたことがあるであろう、どこまでテストすればいいのかという問題である。「バグが0になるまでに決まってるだろ!」と思う人が居るかも知れないし、そのように上から言われてる人が居るかも知れない。筆者は過去にそんな理不尽な圧力を何度も目撃した。しかし、現実的にはバグが0であることを証明するのは不可能である。ごくごく一部の例外を除き、はるかに不可能であり、不可能オブ不可能ズであり、1秒でも考えるのが無駄なくらい十分に不可能なのである。バグが無いことが証明されてリリースされるソフトウェアなんて存在しないのであり、どれだけテストして修正しても、ソフトウェアにバグは必ず存在するのである。
現実社会できちんと真っ当なソフトウェア開発の仕事をする人にとっては、バグの数が何らかの確率モデルで仮定されることは至極当然であり、むしろ、そうしないと仕事にならない。


解1:n回テストした時のトータルコストC(n)はn*Ct + (B - ΣX(k))Cbであり、
C(n+1)-C(n) = Ct - X(n+1)Cb
であり、E(X(n+1))は単調減少なので、E(C(n+1)-C(n))は単調増加であり、どこかでテストのコストの平均が残バグのコストの平均を上回る。E(C(n+1)-C(n)) > 0を解くと、E(X(n+1)) < Ct/Cbなので、答えはE(X(n+1)) < Ct/Cbとなるnである。


問2:Bが平均λのポアソン分布に従い、X(n)がその時点のバグ数と確率pをパラメーターとする二項分布に従う時、問1の最適なnはいくらか。


ソフトウェアのバグ数は、ソフトウェアの規模に比例すると考えられることが多い。システムの規模が大きくなると単位コード量当たりの複雑さも増すので、比例するというのはおかしい、と考えるのも自然なことなのだが、現実にはソフトウェア開発の対価はコード量に比例して支払われることが多いため、ソフトウェアは冗長であってもなるべく単純に作られ、単位コード量当たりの複雑さは上がらないのである。コード量が減るように工夫して効率の良いコードを作ると逆に報酬が下がってしまうので、コードは最適化されずに単純で似たようなコードの積み重ねとなり、システムの複雑さがそのままコード量として表れるのである。
従って、ソフトウェアのバグ数が(規模×単位コード量当たりのバグ数)を平均とするポアソン分布に従うと仮定するのは、現実社会に居て違和感を感じない。
1回のシステムテストで見つかるバグの数は、1つ1つのバグについて確率pで見つかると考えると、バグ数×pを平均とする二項分布に従うと仮定するのは、至極妥当であろう。


解2:B(n)をn回目のテスト後のバグ数とすると、1回のテスト当たりに見つからずに残る割合の平均が(1-p)なので、B(n)は平均λ(1-p)nのポアソン分布に従う。X(n+1)の平均はB(n)*pなので、答えはE(X(n+1)) = λp(1-p)n < Ct/Cbとなるnである。


参考文献
「タイミングの数理 最適停止問題」穴太克則 著(朝倉書店)

続きを読む "ソフトウェアリリース問題" »

2009年07月19日

秘書問題の考察(4) 最小期待順位の極限値について

前回のエントリーで説明した、秘書問題(secretary problem)の期待順位を最小にする解に関して、もう少し追究する。


まず、前回は参考文献を鵜呑みにした、j人中x位の人がn人中何位であるかの期待値が
¥sum_{y=x}^{n-j+x}y¥frac{¥pmatrix{n-y¥cr j-x}¥,¥pmatrix{y-1¥cr x-1}}{¥pmatrix{n¥cr j}} = ¥frac{n+1}{j+1}¥,x
となること(左辺が右辺に等しくなること)を導出する。
これの左辺をy(j,x,n)と書く。j人中x位の人は、もう1人加えて(j+1)人とすると、x位か(x+1)位かのどちらかになる。(j+1)人目が上位x位に入ると(x+1)位、入らないとx位のままである。このことから、j人中x位の人の最終順位は(j+1)人中(x+1)位の人の最終順位と(j+1)人中x位の人の最終順位で表され、
y(j,x,n) = x/(j+1) y(j+1,x+1,n) + (j+1-x)/(j+1) y(j+1,x,n)
の関係が成り立つことがわかる。扱いやすいように、jを1つずらして、
y(j-1,x,n)=¥frac{x}{j}¥, y(j,x+1,n) + ¥frac{j-x}{j} y(j,x,n)
としておく。
y(n,x,n)=xは自明だから、そこからy(n-1,x,n)が求まり、再帰的に計算するとy(j,x,n)が求まる。
j=n-1については、
y(n-1,x,n) = ¥frac{x}{n}(x+1) + ¥frac{n-x}{n} x = ¥frac{n+1}{n}x
j=n-2については、
y(n-2,x,n) = ¥frac{x}{n-1}¥frac{n+1}{n}(x+1) + ¥frac{n-1-x}{n-1}¥frac{n+1}{n}x = ¥frac{n+1}{(n-1)n}¥left(x(x+1)+(n-1-x)x¥right)=¥frac{n+1}{(n-1)n}nx=¥frac{n+1}{n-1}x
なので、y(j,x,n) = (n+1)/(j+1) xではないかと予想できる。それを帰納法で確認する。
j=n-1, n-2については上のように成り立つ。あるjについて成り立つとすると、
y(j-1,x,n) = ¥frac{x}{j}¥frac{n+1}{j+1}(x+1) + ¥frac{j-x}{j}¥frac{n+1}{j+1}x = ¥frac{n+1}{j(j+1)}¥left(x(x+1)+(j-x)x¥right)=¥frac{n+1}{j(j+1)}(j+1)x=¥frac{n+1}{j}x
となり、(j-1)についても成り立つので、間違いなくy(j,x,n) = (n+1)/(j+1) xである。


次に、Chowという人の1964年の論文によるらしい、その筋では頻出の、筆者を秘書問題地獄に陥れたミラクルな定理を紹介する。
定理:期待順位最小の最適戦略による期待順位をV(n)とすると、
¥lim_{n¥rightarrow¥infty}V(n)=¥prod_{j=1}^{¥infty}¥left(¥frac{j+2}{j}¥right)^¥frac{1}{j+1}¥simeq3.8695
である。
つまり、応募者が何人に増えようが、千人だろうが1万人だろうが、平均的にその中の3.87位以上の人を選択できる採用戦略が存在するのである。その数字の小ささもさることながら、その数字がnを含まないある定数に収束するというのは驚きではなかろうか。

さらに、期待順位最小の最適戦略を、r(x,n)番目の応募者からは暫定x位以上の人を採用すると書くと、次の式が成り立つ。
¥lim_{n¥rightarrow¥infty}¥frac{r(x,n)}{n}=¥frac{1}{V(¥infty)} ¥prod_{j=1}^{x-1}¥left(¥frac{j+2}{j}¥right)^¥frac{1}{j+1}
r(x,n)/nは面接した応募者の割合だから、nが大きい時、全応募者のどれくらいの割合を面接した時点から何位以上の人を選べば良いかというのが、これで計算できる。x=1〜10について計算すると


xr(x,n)/n
10.2584
20.4476
30.564
40.6408
50.6949
60.735
70.7658
80.7903
90.8101
100.8265

となるので、最初の25.8%の人はパスし、25.8%の人が過ぎたら1位の人を、44.7%の人が過ぎたら2位以上の人を、56.4%の人が過ぎたら3位以上の人を(以下略)採用すれば良いということになる。(但し、これはnが小さい場合は正確な値との差が大きい。前回のエントリーでの計算結果と比較すると、n=20でもかなりずれている。)

参考文献
Optimal Stopping and Applications(最適停止理論の大家、Thomas S. Ferguson教授による解説)Chapter 2.

続きを読む "秘書問題の考察(4) 最小期待順位の極限値について" »

About 2009年07月

2009年07月にブログ「Weblog on mebius.tokaichiba.jp」に投稿されたすべてのエントリーです。過去のものから新しいものへ順番に並んでいます。

前のアーカイブは2009年06月です。

次のアーカイブは2009年08月です。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

Powered by
Movable Type 3.35