＞
結城浩の日記 ＞
2005年10月
|
＞
結城浩の日記 ＞
2005年10月
| 検索 |
| プロフィール | 日記一覧 | 日記ダイジェスト | Twitter | RSS |
|
むしょうにCGIが作りたくなって作った「まだ名前のない実験ページ」です。
拙著『プログラマの数学』の第6章に出てくる「再帰的な木」を描くJavaのソースコードを公開します。
以前から公開しようと思っていたのですが、忘れていました。 (^_^;
追記: JDK 1.4ではコンパイルエラーになるようです。 J2SE 5.0でコンパイルしてください。 すみません。
setPreferredSizeがひっかかるようなので、 そこを直せばいくと思いますが、いますぐは試せません。 ごめんなさい。
「さまざまな方のための祈り」を更新しました。
「ミルカさんとフィボナッチ数列」のLaTeXファイルを公開しました。
先日 日記で紹介した朗読劇団の方から、『賢者の贈り物』の発表が終わりました、 という丁寧なメールをいただきました。 「物語が演者やお客さんに楽しんでもらえたのも、これを版権自由の状態で翻訳してくださった結城さんのおかげです」 とのこと。結城も、とてもうれしいです。 「言葉がいろいろな人の間を色々にわたっていく、最近、そのことがひどく感動的なことに思えます」 と書いておられました。 結城もまったく同感です。
「賢者の贈り物」は、 山形浩生さんの「プロジェクト杉田玄白」に賛同して翻訳したテキストでした。 思い返せば6年前(!)のこと。 1999年のクリスマスに向けての活動でした。
奇しくも『Java言語プログラミングレッスン』の最初の版の出版も1999年。
時が過ぎるのは早いものですが、何とも心地よい時間のながれです。
朝は、 『改訂第2版Java言語プログラミングレッスン』 の掲載ソースリストの整理を進める。
みなさんからのメッセージをにこにこしながら（時にはしんみりとしながら）読む。 結城は、読者さんがどんな方なのかにとても関心があります。 集計しちゃうと消えてしまうような、 一人ひとりの「ごつごつ」や「さらさら」を大事にしたいと思っています。 なので、時間はかかりますけれどメッセージを「読む」のが大事かなと思っています。
それはさておき、メッセージを読んでいて気づいたことをいくつか。
『のだめカンタービレ』の人気がとても高いことがわかりました。 今度機会があったら読んでみようと思います。音楽の話なんですよね。 「カンタービレ」は「歌うように」だったかな。 「のだめ」って何だろう…。(追記：主人公のあだなとのこと)
森博嗣の読者が多いことは予想していたのですが、北村薫の読者が多いこともわかりました。 北村薫の本は『六の宮の姫君』だけ読んだことがあります。いい雰囲気の本でした。
「Rubyの本」を書いて! という要望がとてもたくさんありました。
例の「結城さんがRuby本を書くことを既成事実化しようプロジェクト(?)」
に加担している人の多いこと多いこと (^_^;
こんな風に期待されるというのは、なんとも光栄なことだと思っています。
人数もさることながら、熱気がすごいなあ。ふうむ…。
『プログラマの数学』の続編や「ミルカさんが出てくるような数学読み物」を書いて、という要望も多かったです。 それから、ここには書きませんけれど、結城が考えもしなかったような書籍のアイディアもありました。
「いつも日記を読んでいますが、この機会に感想を送ります」 という方もたくさんいらして、うれしくなりました。 結城の活動を応援してくれるみなさんに感謝し、 結城の命を支えてくださる神さまに感謝します。
私はとても幸せ者ですね。 *^_^*
2005年10月28日 07:18 頃、 『改訂第2版Java言語プログラミングレッスン』 無料プレゼントの抽選を行ない、当選した7名の方に連絡のメールをお送りしました。
申し込み人数は97名でした。 多数の申し込みをありがとうございます。 残念ながら当たらなかった方、本当にごめんなさい。
抽選は、結城の恣意的な操作が入らないように （応募者の名前を見て判断することがないように）、 一覧表を作ったうえで、プログラムを使って当選者を抽出しました。
みなさんからのメッセージを心から感謝します！
みなさん、こんばんは。(^_^)
『改訂第2版Java言語プログラミングレッスン』の無料プレゼントの申し込みは、
現在90名になりました (@_@) 。たくさんのご応募ありがとうございます！
はげましの言葉やアドバイスもありがたく読ませていただいています。
申し込みの〆切は今日の真夜中です。
アマゾンに注文していた本が届いたので、今日はそれを少し勉強する。
おはようございます！ 今日も、祝福に満ちた素晴らしい一日を、先取りして感謝します！
みなさん、こんばんは。(^_^)
『改訂第2版Java言語プログラミングレッスン』の無料プレゼントの申し込みは、 現在67名になりました。たくさんのご応募ありがとうございます。 応援のメッセージもすごくうれしいです。
申し込みの〆切は明日(木曜日)ですので、よろしくどうぞ。
道を歩きながら、最近学んでいることを頭の中で復習する。 コンピュータを開いてから、さっき歩きながら復習したことを文章として書く。 書いた文章を読み返すと、あちこち理解が怪しい箇所が分かってくる。 そこに印を付けておき、その疑問を解決すべく調べ物をする。 少し調べても、わからないことが多い。 そうしたら、疑問に思ったことを文章の形にして残しておく。 疑問に思ったことの解答に後から出会うこともある。 そのときには、解答をそこに文章として書いておく。 要するに、文章を使って学習を進めているのだね。
学習するとき、特に独学しているときには 「自分が本当に理解している」ことを確認するのが大事だ。 では、どうやれば自分の理解を確認できるか。
簡単だ。自分が理解していることを示す「文章」を書けばよい。
その題材について「A. わかりやすい文章を書くことができる」ならば、 「B. 理解している」といえる。
A⇒Bは真である。AはBが成り立つ十分条件である。
文章を書くことは、テストをしているようなものだ。 テストドリブンなソフトウェア開発ならぬ、 テストドリブンな学習ということだ。
ところで（何度も日記で書いている話だが）、 文章を書いて自分の理解を試そうとした場合、もっとも重要なのが 「わかったふりをしない」ということだ。 「わかったふり」は、非常に学習の邪魔になる。
「ここはまだわかっていないけれど、先に進もう」という態度はそれほど悪くはない。 悪いのは、わかっていないのに「自分はわかっている」と思い込もうとする態度だ。
わかったふりをする・しないというのは、習慣の問題でもある。 いつもわかったふりをしていると、それが習慣になってしまう。 いつも「私はほんとうにわかっているのかな？ 自分の言葉で説明できるかな？」という態度をとっていると、 学習効果は非常に高くなる。
わかったふりをするかどうかは、意外なことに（いや、意外じゃないかな）、 自分の心の状態や人間関係にもかかわる。 いつも虚勢をはったり、他人に対して偉そうなそぶりを見せないと自分自身の立場が危ういと感じている人は、 「わかったふり」をしてしまう可能性が高い。 「そんなことは知っているよ」という態度をとらないと馬鹿にされる、 と恐れている人は学習の機会を逸する危険性が高い。
みなさん、おはようございます。(^_^) 今日もみなさんの上に神さまの豊かな祝福がありますように。
『改訂第2版Java言語プログラミングレッスン』の無料プレゼントの申し込みは、 現在39名です。ありがとうございます。 〆切は明日(木曜日)です。
日記ダイジェストを更新しました。 2004年4月、5月分。
音楽シャッフル・クイズ(解答編)に対して、読者さんから 「配列の要素の取り得る順列が等確率で得られるためには、 sizesizeがsize!で割り切れることが必要である」 という部分がよく分からないというご質問がありました。 この方は、 「sizesizeがsize!で割り切れたとしても、等確率になるとは限らないのでは？」 という疑問を抱かれたようでした。 この疑問は正当ですが、 今回のクイズの解答とは直接の関係はありません。 必要条件と十分条件を混同なさっているのだと思います。
「A. 順列が等確率で得られる」という命題と「B. size^sizeがsize!で割り切れる」という命題の関係を整理してみましょう。 AとBの関係は、
A ならば B である …(1)
というものですね。
読者さんは、この命題(1)と、以下の命題(2)を混同したのだと思います。
B ならば A である …(2)
(1)の真偽と(2)の真偽は無関係です。 今回の証明では(1)の真偽は使いますが、(2)の真偽は不要です。
さて、もともと証明したかったのは、Aが偽であることです。 Aが偽であることを証明するため、私は先日の解答で、
の2つを示しました。 命題(1)が真であり、命題Bが偽であれば、命題Aは必ず偽だからです(※)。
たとえば、 「6の倍数ならば2の倍数である」ということと「この数は2の倍数ではない」から「この数は6の倍数ではない」というようなものです。
一般に、
A ならば B である
という命題が真のとき、BをAの必要条件といい、AをBの十分条件といいます。 この「必要」と「十分」という用語は非常にあたまを混乱させるのですが、 「Aが成り立つためには、Bは絶対に成り立っている必要がある」(つまりBを崩せばAも崩れる)ということと、 「Bが成り立つためには、Aが成り立っていることが確認できれば十分である」(つまりAさえ言えればBも言える)ということを 考えれば思い出すことができます。
これでお答えになっていますでしょうかね （追記: 読者さんによれば、答えになっていたようです。よかったよかった）。
補足(a) ※印は、((A⇒B)∧(¬B))⇒¬A が常に真になるということですね。 これは、(A⇒B)の定義が(¬A∨B)であることを思い出せば（式の変形または真理値表で）証明できます。
補足(b) 今回の解答としては「等確率ではない」ことを示せたので終わりなのですが、 ここから先には 「それではどういう条件が成り立てば等確率になるのか？」 という問題は残ります。
『改訂第2版Java言語プログラミングレッスン』 の掲載ソースリストをWebで公開する準備を進める。 readme.txtとの整合性を調べるためのチェックツールをPerlで書く。
『改訂第2版Java言語プログラミングレッスン』の無料プレゼントへは、 現在24名の方が申し込んでくださっています。 みなさんからのメッセージを読んでいると、参考になるだけではなく、とても励みになりますね。 ありがとうございます。
無料プレゼント抽選の〆切は今週木曜日ですので、 応募予定の方はお早めにどうぞ。
みなさん、おはようございます。 今日もみなさんの上に神さまの祝福がありますように。
「コクヨが人間工学に基づいた新サイズのノートを発売」というニュースを聞き、さっそく購入して使っています。 今日でちょうど2週間目。 私はSlimB5のツインリングノートというのを使っています。
SlimB5は確かにスリムで、乗り物の中でも開いたりメモしたりするのに良いです。 じゃまにならないし、「さっと」使える感じです。 特にリングノートは場所を取らないため、SlimB5のスリムさが引き立つようです。
そもそも、新しい文房具を買うと「新しいこと」がしたくなっていい感じです。 心に新しい風が吹き込むようですね。
大量の文章は、すぐにコンピュータに向かって書きます。 ですから、私が紙のノートを開いて書くというのは、 「ゆっくり書きたいとき」や「自分でもよく分かっていないことを書くとき」ですね。 頭を「考えさせる」ために、わざとゆっくり書くこともあります。 紙のノートに書くのには時間がかかる。それを逆手にとるのです。
日付を書く。ゆっくり深呼吸する。 タイトルを書く。首をぐるっとまわして一息入れる。 頭の中で誰かに説明しながら、一行一行ていねいに書いていく。 わざと冗長に数式を展開することも。
コンピュータを使った仕事の合間には、紙のノートを読み返します。 ノートを読み返してみて「ああ、この文章は面白いからタイプしてみようか」とか、 「この数式をきちんとLaTeXで清書してみよう」などと思うことも多いです。 コンピュータに入力したら、 ノートのそのページに、入力したことを示すマークを付けておきます。
暇なときに、ノートをぱらぱらめくっていると、 自分の時系列での活動が見えて面白いですね。 またノートに記された日付を見ていると、 「最近なんにもやってないと思ってたけど、 意外といろんなこと考えているじゃん」と、何だか嬉しい気持ちになります。
紙のノートは直接検索できません。 でも、必要そうなことはコンピュータに入れ直すし、 それになにより、ぱらぱらノートを見返すことで、 自分の頭の中に入っちゃう感じがします。 だから、検索できないことはあまり苦になりません。
先日出した連載原稿も、 ランダム・アルバイト・クイズも、 音楽シャッフル・クイズも、 スタートは、SlimB5のノートでした。
音楽シャッフル・クイズへの解答や反応をありがとうございます。 以下、結城および他の方々の解答（抜粋）を記載します。
クイズに挑戦したい方は、 先を読み進める前に、 問題編をお読みください。
解答：正しくシャッフルしない。
理由：配列の要素の取り得る順列は全部でsize!通りある。 一方、関数shuffleを1回呼び出したときの式random(0, size)の戻り値の列(size個からなる乱数列)は、 全部でsizesize通り（sizeのsize乗通り）ある。 このsizesize通りはすべて等確率で得られるため、 配列の要素の取り得る順列が等確率で得られるためには、 sizesizeがsize!で割り切れることが必要である （さもないと均等に分布しない）。 しかし、size≧3のとき、sizesizeがsize!で割り切れることはない。 したがって、関数shuffleは（3以上のどんなsizeを与えても）正しくシャッフルしない。
補足(1): この問題は、 Introduction to AlgorithmsのExercise 5.3-3 (p.105)を参考にしました。 (余談ですが、Introduction to Algorithmsには、 ペーパーバック版もあるようです)
補足(2): nnがn!で割り切れないのは、n≧3のとき、nがn-1で割り切れないことから明らか。
補足(3): n≧3のとき、nがn-1で割り切れないのは、nとn-1はn≧3のとき共通の素因数を持たないから。 もしnとn-1が共通の素因数p≧2を持ったとすると、nとn-1の差はpの整数倍でなければならない。 しかしnとn-1の差(1)はp≧2の整数倍にはならない （n=ap, n-1=bp を n-(n-1)=(a-b)p にする）。
補足(4): 以下のようにすると正しいシャッフルになります。 （ループの終了条件とrandomの引数に注意）。
/* corrected */
void shuffle(int music[], int size)
{
int i;
for (i = 0; i < size - 1; i++) {
int r = random(i, size);
int m = music[i];
music[i] = music[r];
music[r] = m;
}
}
補足(5): 均等に分布するかどうかを調べるには、 randomを乱数生成の関数にするのではなく、 すべての場合を順番に生成する関数にして実験すると見通しを付けやすくなります。 たとえば、size=3のとき、random(0, size)が、 0, 0, 0; 0, 0, 1; 0, 0, 2; 0, 1, 0; ..., 2, 2, 1; 2, 2, 2という順番で値を返すようにするのです。
補足(6): 読者の中には、 「どう考えていいかまったくわからない。数学は難しくて嫌だ」 と嘆いていらっしゃる方がいらっしゃいました。 こういう問題に向かったときには、最初から一般的に考えるのではなく、 まず、少ない数で試してみるという態度が極めて重要です。 たとえば、 id:seamlessbiasさんがミルカさん風に書いてくださったように、 size=3の場合は、すべての順列を書き上げて考えることができます。 そうすれば、少なくともsize=3の場合には正しくないことが分かると思います。 これは重要な手がかりになりますね。
はらさんからのコメント
結城さんの補足(2)で、nのn乗がn!で割り切れない理由を、 「nがn-1で割り切れないことから明らか」 と述べていますが、これは若干（ほんとに若干ですが）誤解を招 くと思います。なぜなら、一般にaがbで割り切れないからといって、 aのn乗がbで割り切れないとは限らないからです。
正しくは、 「nのn乗がnの階乗で割り切れないのは、『nをn-1で割った余りが1なので、n のn乗をn-1で割った余りは1のn乗=1となる』ということから明らか」 とすべきでしょう。『』は、剰余類の乗法に関する性質です。
この「nをn-1で割った余りは1」より、補足(3)はトリビアルでしょう。
結城さん，こんにちは． 前回のランダム・アルバイト・クイズでは壮絶な勘違いをしでかしてしまいましたが， めげずにシャッフルクイズにも回答してみます．．．
正しくシャッフルしない．
(理由) シャッフルの仕方が何通りあるかを考えてみます． ループ内で r を選ぶのに size 通りの選び方があり， さらにこの過程が i=0 から size-1 まで繰り返されるので， シャッフルされた音楽リストの作り方は size^size (size の size 乗) 通りあります． これらは明らかに等確率で選ばれます． 一方，配列の要素の順列は size! 通りです． 前者を後者で割ると size^size/size! = size^(size-1)/(size-1)! となりますが， 明らかにこの商は整数になりません． （size>=3 では size/(size-1) が整数にならないため) このことは，シャッフルリストの作り方を等確率で各順列に割り振ることができず， 順列によって生起確率に差ができることを意味します． よって，等確率で順列を得る（正しくシャッフルする）ことはできません．
どのように分布が偏るかも考えてみたいのですが，厄介そうなので， 思いついたらまたフィードバックいたします．では．
1)関数shuffleは式randomを（size）回呼び出します。
2)式randomが1回の呼び出しで返す値の選択肢は（size）個です。
3)1と2より、関数shuffleが返す配列は、重複も含めると（sizeのsize乗）通り考えられます。
4)配列music[]内に同じ要素が一つもない時、要素の並べ方は（sizeの階乗）通り考えられます。
5)（size）が3以上の時、（sizeの階乗）は約数に（size-1）を持ちますが、（sizeのsize乗）は約数（size-1）を持ちません。
6)5より、（sizeの階乗）は（sizeのsize乗）の約数ではありません。
7)6より、（sizeのsize乗）個のものを偏りなく（sizeの階乗）通りに分配することは出来ません。
8)3と4と7より、関数shuffleが返す配列の確率は常に偏りを持つことになります。
結論)よって「正しくシャッフルする」ことは出来ません。
解答：正しくシャッフルしない
理由： １）
順列のパターン数：N!
このshuffle関数での場合の数：N^N
N^NはN!で割り切れないため、等確率にはならない。 （割り切れない証明はパス。（笑））
２）実際にプログラムを作って統計的に結果を見てみました。 （Cで作ったものはちょっと長くなったので、Perlで作ったものです。）
#!/bin/perl
sub shuffle {
my $ref_music = shift;
my $size = shift;
for ($i = 0; $i < $size; $i++) {
$r = int rand $size;
$m = $$ref_music[$i];
$$ref_music[$i] = $$ref_music[$r];
$$ref_music[$r] = $m;
}
}
for (1..100000) {
@music = (1..3);
shuffle(\@music, scalar @music);
$count{"@music"}++;
}
foreach (sort keys %count) {
print "$_ : $count{$_}\n";
}
結果
$ ./shuffle.pl 1 2 3 : 14770 1 3 2 : 18503 2 1 3 : 18558 2 3 1 : 18556 3 1 2 : 14748 3 2 1 : 14865
明らかに等確率ではないですね。
そのほか、miya-samaさん, やなぎわらさん、はらさん、ニーニさん、無記名の方、などから解答や感想などをいただきました。
みなさま、楽しんでいただけたでしょうか。 ではまた！
結城浩の最新刊 『改訂第2版Java言語プログラミングレッスン（上・下）』を、読者の皆さんへの感謝を込めて無料プレゼントいたします。 以下のテンプレートにしたがって、 フィードバックの欄からお申し込みください。
〆切は 2005年10月27日(木) です。 （すでに抽選は終了しました）
応募者の中から抽選で7名を選び、 お一人に1セットずつ、全部で7セット(上下巻で1セット)をお送りします。
料金は無料（送料も不要）です。 当選した方にはメールで住所をお尋ねしますので、 申し込み時に住所を入力する必要はありません。 ただし、メールアドレスは間違えずに入力してください。 日本国内限定です。
注意：お送りするのは結城のサイン本ではありません。
テンプレート
■あなたのお名前 ■メールアドレス ■あなたはどんな方？（お仕事や年齢、趣味など） ■『改訂第2版Java言語プログラミングレッスン』を読みたい理由 ■最近あったうれしいこと、かなしいこと ■あなたの好きな本、最近読んだ本など（サイエンス・技術系） ■あなたの好きな本、最近読んだ本など（サイエンス・技術系以外、漫画などでも） ■結城の本を読んだことがあれば、その感想など ■結城に「こんな本を書いてほしい」というご希望があれば ■そのほか、結城の活動に関して、感想をご自由に
例
■あなたのお名前 高橋マモル ■メールアドレス mamoru@example.com ■あなたはどんな方？（お仕事や年齢、趣味など） IT系企業の入社一年目、23歳男性です。 ご多分に漏れず毎日夜中までキーボードを叩いています。 帰るのが面倒になってネット喫茶で仮眠を取るのが月に1度という生活です。 ■『改訂第2版Java言語プログラミングレッスン』を読みたい理由 自分はふだんPHPで仕事をしているのですが、 やっぱりJavaも押さえておきたいなあと前々から思っていたので。 ネットの情報だけでも雰囲気で読めないことはないんですけれど、 何だか細かいところを勘違いしてそうで、基礎を固めようと。 ■最近あったうれしいこと、かなしいこと うれしいことは、自分の仕事をするという感じがわかってきたこと。 大学のころとは違う厳しさが心地よい（といったら生意気でしょうか）です。 かなしいことは、大学時代から付き合ってきた彼女と最近疎遠になってしまったこと。 こっちは一言ではいえません。うー。 ■あなたの好きな本、最近読んだ本など（サイエンス・技術系） 最近読んだ本は、川合さんが翻訳した『ハッカーと画家』と、 それから、ワインバーグの『ライト、ついてますか』です。 『ライト、ついてますか』は会社の先輩に紹介されました。 ■あなたの好きな本、最近読んだ本など（サイエンス・技術系 *以外*、漫画などでも） 『あずまんが大王』が好きです。あの中に大阪っていう女の子がいてですね、 って説明を始めてもしょうがないですが(w とにかく何か好きです。 大学時代は彼女の影響で村上春樹を読んでいましたが、 最近はあまり読んでいません。 ■結城の本を読んだことがあれば、その感想など 『暗号技術入門』は、けっこう熟読しました。暗号って面白いですね。 この本は分かりやすく、ネットやセキュリティに関わる人には 必読書かなと思いました。この本を読んでから「あ、あれはこういう意味だな」 という暗号技術の位置関係のようなものが分かったみたいです。 『プログラマの数学』は未読ですが、 本屋で見つけたら読んでみようかと思っています。 ■結城に「こんな本を書いてほしい」というご希望があれば わたしはいまPHPで仕事をするのが多いので、PHPの本かな。 あ、でもPHPはもうだいぶ分かっちゃっているから…。 うーん。何かこう、データマイニングの本とか？ （すいません、よく知りません） ■そのほか、結城の活動に関して、感想をご自由に 結城さんの文章は、読んでいて何だかほっとします。 これからも、ほっとさせる文章をたくさん書いてください。 期待しています！
ランダムな整数を得る関数randomがあったとして、 以下に示した関数shuffleは配列を正しくシャッフルしますか、 というクイズです。 関数shuffleの引数の配列に曲番号が入っていて、 それをシャッフルするというイメージですね。 このクイズは、 iPod shuffleを聞きながらアルゴリズムの本を読んでいて作りました。
# 流行の言葉を使えば、iPod shuffleに「インスパイア」されて？ (^_^;
言うまでもないことですが、 関数shuffleは実際のiPod shuffleのアルゴリズムとは無関係です。
問題
C言語で書かれた以下の関数shuffleは、 配列の要素music[0]〜music[size-1]を正しくシャッフルするか。 また、その理由を説明せよ。
void shuffle(int music[], int size)
{
int i;
for (i = 0; i < size; i++) {
int r = random(0, size);
int m = music[i];
music[i] = music[r];
music[r] = m;
}
}
解答したい方は、以下のフィードバック欄をお使いください。 解答は、日記などで公開させていただくかもしれませんので、 そのおつもりで。 もちろん、自分のblogに解答を書いて、 URLを送ってくださってもOKです。
Enjoy!
みなさま、 ランダム・アルバイト・クイズへの解答をありがとうございます。 非常にたくさんの方から解答および反応をいただきました。
以下、結城および他の方々の解答（抜粋）を記載します。
クイズに挑戦したい方は、 先を読み進める前に、 問題編をお読みください。
問題1: そもそも、このような採用は可能か。可能だとすれば、どうすればよいか。
【短い解答】: 可能。 n人目にやってきた応募者を確率5/nで(n≦5なら確率1で)待機させる。 控え室が満室なら、控え室にいた人からランダムに一人を選んで拒否してからn人目の応募者を待機させる。
【長い解答】: 可能。 以下の手順を踏む。便宜上、1番〜5番の「待機番号」がついた椅子を控え室に用意する。
問題2: 5名採用ではなくS名採用に一般化せよ (Sは1以上の整数)。
問題1の解答で5をSに置き換える。 なお、応募者が等確率で選ばれることは、nに関する数学的帰納法で証明できる。
まず最初のS人には「待機」してもらいます。
k人目（k＞S）には、S/kの確率で「待機」と言います。
k人目が待機だったときは、その時点で待機しているS人の中からを1人を代わりに「拒否」します。
k＝n人目が終われば完了！！
説明：
・k≦Sのとき、
待機している全員は等確率で選ばれています。
・k＞Sで、
k-1人目までが等確率 S/(k-1)で選ばれているとして、k人目を選ぶ確率をS/kとして、それまでに待機していた人が選ばれる確率を計算すると、
｛[k人目が選ばれない確率]＋[k人目が選ばれて、かつ拒否にならない確率]｝*[k-1人目までに選ばれている確率]
＝ {(1-S/k)＋(S/k)*(1-1/S)} * S/(k-1)
＝ {1-S/k＋S/k-1/k}*S/(k-1)
＝ {(k-1)/k}*S/(k-1)
＝ S/k
従ってこの選び方で、k人目も、それ以前の人も等確率で選ばれている。
n人の選別完了時は全員がS/nの確率で選ばれたことになる。
module Enumerable
def random_select(max = 5)
cand = []
cnt = 0
x = r = nil
each do |x|
cnt += 1
if cand.size < max
cand << x
if block_given?
yield x, true
end
elsif (i = rand(cnt)) < max
r, cand[i] = cand[i], x
if block_given?
yield r, false
yield x, true
end
else
if block_given?
yield x, true
end
end
end
cand
end
end
if $0 == __FILE__
if /\A\d+\z/ =~ ARGV.first
iter = ARGV.shift.to_i
end
list = ARGF.readlines.each {|s| s.chomp!}
if iter
count = Hash.new(0)
iter.times {
list.random_select(5).each {|s| count[s] += 1}
}
all = 0
count.each {|n, i|
printf("%10s %4d %4.1f\n", n, i, i * 20.0 / iter)
all += i
}
abort "#{all} != #{5 * iter}" unless all == 5 * iter
else
p list.random_select(5) {|s, w| puts "#{s} is #{w ? 'wait' : 'return'}ing"}
end
end
可能である。 次のようにすればよい。
応募者に、ランダムな点数を付ける。 点数は、その応募者がやってきた時に付けられ、その後は変化しない。 点数は、他の応募者と同じにはならないだけの、十分な精度があるとする（注）。 最初の5（S）名は無条件で待機させる。 6（S+1）人目からは、その応募者および控え室の5（S）名の中で最も点数が低い人を拒否し、残りの5（S）名を待機とする。 各応募者が採用される確率は、すべての応募者に一度に点数を付けて上位5（S）名を採用するのと同じであり、等確率である。
（注） 点数の精度が有限でしかあり得ない場合は、次のようにして必要な精度を得ることができる。 新しい応募者の点数と同じ点数がすでに現れていた場合、それらの点数が等しくなくなるまで、点数の精度を1桁ずつ上げる。 追加される桁の値は、その時にランダムに決定する。 ある精度において等しくない値は、それ以上の精度でも大小は変わらない。 そのため、必要となってから精度を上げても、すでに拒否されている応募者は拒否されるべき順位のままであり、各応募者が採用される確率は変わらない。 これは、点数が無限の精度であり、それを有限の精度で比較していた場合と同じことである。
結城のコメント: とおりすがりさんからも、同様の解答をいただきました。 きぞくさんの答えは題意を満たしていますが、 「最も点数が低い人」を探すときに余分な手間がかかる可能性があることを指摘しておきます。
そのほか、 suroyuuさん、かがみさん、小黒直樹さん、島田さん、hiragisan、渡辺亨さん、nさん、西村達人さん、ゆーさん、mickeyさん他、 たくさんの方からご解答いただきました。 ありがとうございます。
なお、今回のランダム・アルバイト・クイズは、 Knuth先生のThe Art of Computer Programmingに書かれている「選択サンプリング法」を元にしています。 C MAGAZINE 2005年12月号(来月号)の、結城の連載記事の一部で触れます。
ホフスタッターの『ゲーデル、エッシャー、バッハ』の20周年記念版が出版されています。 書店で今日見かけましたが、序文としてホフスタッター自身の解説（結構長い）がついていました。
『メタマジック・ゲーム』も並んでいました。
あなたは今日、事務所にやってくる応募者の中から5名のアルバイトを採用する仕事をします。 採用条件は以下の通り。
問題1: そもそも、このような採用は可能か。可能だとすれば、どうすればよいか。
問題2: 5名採用ではなくS名採用に一般化せよ (Sは1以上の整数)。
解答したい方は、以下のフィードバック欄をお使いください。 解答は、日記などで公開させていただくかもしれませんので、 そのおつもりで。 もちろん、自分のblogに書いて、URLを送ってくださってもOKです。
Enjoy!
追記(2005-10-17夜中): この問題では、応募者の能力はまったく考慮していないことにご注意ください。 この問題のポイントは「全体の人数が分かっていないのに等確率でランダムに選ぶ」ところにあります。
午前中は礼拝。帰ってきてからお昼寝。 午後から少し原稿の図を描いて、プログラムを少し手直し。 それから文章をスケッチする。 説明を書いているうちにアルゴリズムに不安が生じたのだが、手計算をして大丈夫であることが判明。 気が付くといつものように分量が二倍以上になってしまった。 材料はそろったので、あとは頭がさえている時の数時間を使えば、編集部に送れる原稿ができあがるはず。
今日は静かに原稿を書く。 プログラムはもうできたので、関連する図を描く。 いつものように、説明の図を描いていると、 楽しくなってきて枚数がどんどん増えていく。 まずい。 いや、それほどまずくはない。 平澤さんがよく書いているように、 たくさん書いてから削るほうが楽だから。
PB memoに「ともあれやはり結城さんにRuby本を書いてもらうのが一番でしょう」などと書かれていたので、
何だ何だとruby-listを読む。
関係各位からむちゃくちゃほめられているので恐縮しつつもうれしくなる。(*^_^*)
それはさておき、Rubyの入門書ですか…。うーん。
追記：
SICPの解説書!それは…恐れ多くて、やってみたいが（どっちやねん）。
追追記(2005-10-16)：
「煽ったみたいでちょっと申し訳ない」とのことですが、大丈夫ですよ〜。 言及してくださる方々は みな節度を持って(?)煽ってくださるので、 いろんな方から広い意味での応援をいただいていると思ってます。 考えてみますと「結城さんが書くならぜひ読みたい」などと書いていただけるのは、 ほんとうに光栄なことです。 また、こういう本を書いてほしいという要望を投げていただけるのも、 （結城が実際に手がけるかどうかは別として） とても参考になります。
追記(2005-10-20):
「SICPをまるごと解説するのは大変そうな気がするので…」と書籍の内容のアドバイスをいただきました。 なるほど、なるほど。
夜中にお風呂に入っていると、目が覚めちゃったといって長男も入ってきた。
私「0, 1, 1, 2, 3, 5, 8, 次は?」
長男「ん？13（にやり）」
私「そうだね（にやり）」
長男「次は21, 34」
私「0番目は0, 1番目は1, 2番目も1, 3番目は2」
長男「4番目は3, 5番目は5」
私「それではn番目は？」
長男「簡単だよ。あのね」
私「ちょっと待ったあ。簡単？」
長男「ええとね。n番目はn-1足すn-2」
私「（本当にそうかな？という顔）」
長男「あ、違う違う。n番目はn-1足すn-2じゃなくて、n番目はn-1番目足すn-2番目だ（照れ笑い）」
私「そうそう（にっこり）」
長男「で、n-1番目はn-2番目足すn-3番目」
私「そうだね。実はn番目には√5が出てくる。√5って知ってる？」
長男「知ってる。大根でしょ」
（「大根」というのは『数の悪魔』に出てくるルートの表現。根(root)にかけているわけです）
私「そう。フィボナッチ数列の第n項には√5が出てくるんだ。不思議なことに」
長男「へえ。ところで何でそんな話になるの」
私「いや。最近ずっとそれを考えていたからね」
kdmsnrさんのところからアクセスがたくさんありました。 『プログラマの数学』に対する ご感想を書いてくださりありがとうございます。 とてもはげみになります！
『改訂第2版Java言語プログラミングレッスン』出版のアナウンスをいたします。
1999年に出版したJava言語の入門書『Java言語プログラミングレッスン』は、 非常に多くの読者を得ることができました。みなさん、ありがとうございます。
みなさんからの応援を受けて、2003年には本文の内容を見直し、 さらにサンプルをJDK 1.4対応にした「改訂版」を出版することができました。
そして今回、2005年の『改訂第2版Java言語プログラミングレッスン』では、 書籍全体をもう一度細かく見直し、さらにJ2SE 5.0の内容を取り入れました。
本書も、Java言語を学ぶ方々のお役に立ちますように。
（出版は2005年10月末の予定です）
午前中は教会。小雨。何となく肌寒い天気のせいか、帰ってきてからぐうぐうお昼寝をする （天気とは無関係に、いつもお昼寝しているような気もする）。 その後、少しお仕事をする。
昨日、 「ミルカさんとフィボナッチ数列」を公開した勢いで、 今日はLaTeXいじりをしていた。楽しいなあ。 昔はコンピュータがとても遅くて、一ページ処理するにも時間がかかったものだけれど、 最近はあっという間に何十ページも処理してしまう。 dvipdfmを使ってすぐにPDF化できるし、 よい時代になったなあ（年寄りくさい表現）。 数式を含んでいる文書を作るなら、 手軽さ・美しさ・他者とのデータ互換性の点で、 LaTeXの右に出るソフトウェアはないんじゃないかなあ。
LaTeXをはじめたいと思った方(特にWindowsユーザ)は、 以下のページをご参考にどうぞ。
書籍はいろいろ出ていますが、まずは奥村先生の「美文書」がお薦めです。
そういえば、さっきログを見ていたら、 昨日公開した 「ミルカさんとフィボナッチ数列」のPDFファイルが、一日で300人以上からダウンロードされたことが分かりました。 みなさん、ありがとうございます。とてもはげみになります！
ミルカさんシリーズ第3作、「ミルカさんとフィボナッチ数列」を公開します。 ぜひ、ご感想をお寄せください。
これまでのミルカさんシリーズは以下にあります。
このごろ、夜眠るとき、 ナルニア国ものがたりの『ライオンと魔女』を次男に読み聞かせている。 一日一章ずつ。
最近は カラー版というのもあるんですね。
追記： id:babieさんから、 最近は絵本も出てるんですよと教えていただきました。 ありがとうございます。
最近Web日記（つまりここ）に書く量が少なくなっているけれど、 日記そのものはたくさん書いている。 勉強したことや調べた内容についての記録を時間順で書いているもので、 書いている書籍や記事ごとにファイルを分けているから、 日記というよりも作業記録のようなもの。 ある題材に関する「勉強日記」と呼んでもいいね。 Webからの抜書きや、本をタイプして写したものもあるので公開はできない。
作業の記録は、ずっと昔からつけているけれど、 最近、こういう「勉強日記」を何日かに一度読み返すと、 とても理解が進むということに気づいた。 考えてみれば当たり前のことですけれどね。
新しいことをどんどん頭に入れようとするだけでは、あまり理解は進まない。 人間はコピー機じゃないのだから。 勉強しながら自分が覚えようとしたこと・考えたこと・やってみたことを勉強日記に記録しておく。 勉強日記を読み返すというのは、 自分が体験したことを、もう一度振り返ってみているわけだ。 いったん自分の中を通り抜けたことだから、短時間で思い出せるし、 最初に学んだときには気づかなかった点にも気づく。 以前書いた文章のまずい点（つまり、自分の間違った理解）も見つかる。 それに勉強日記の量が増えてくると「自分はこれだけ勉強してきたんだな」という自信も得られる。 良いことづくめだ。
勉強日記を書くときのコツをいくつか紹介しよう。
1つ目。「当たり前」を書け。 自分がそのとき 「これは当たり前だからわざわざ書くまでもないな」と思ったことこそ書くようにしよう。 自分が学んでいる真っ最中に「これは当たり前」と感じた点というのは、 後から読み返すときに、自分の理解の「足場」になってくれるのだ。
2つ目。自分しか読まなくても、丁寧に書け。 自分しか読まないからといって雑に書くのは意味がない。 むしろ、他人に見せてもいいくらいに丁寧に書くのがよい。 参考書の本の名前やページ数、あるいはWebのURLなども、面倒くさがらずに書こう。 後から読み返すときに、そこが手がかりになってくれる。 数日後、読み返してみて分かりにくいなら、書き方が雑すぎる。
3つ目。「分からない」を書け。 自分が「まだこれはわからない」ということを書いておこう。 しばらくして、読み返したときにチェックすることができるように。
以下のリンクは、似たような話題の過去の日記。
Tim O'ReillyがWeb 2.0: Compact Definition?という短い文を書いていた。 その中に、delivering software as a continually-updated serviceという表現が出てきた。 ふむふむ、という感じ。
話は上記のページからも、Web 2.0からも ややずれていくのですが、 最近よく見られる、以下のような傾向に対する「包括的で適切なネーミング」はないのでしょうかね。
以下を絡めてもよいかも。
追記： よく考えてみれば「包括的で適切なネーミング」がないからこそ「Web 2.0」という呼称になっているともいえる。
追記： 「改変できない全体」よりも「細分化された必要な要素」(例: iTunes Music Store)というのは 分かりにくい表現でした。 あまり深い意味はありません。複数の曲が入ったCDを購入するのではなく、 必要な曲だけを選んで購入というほどの意味です。
早いなあ。
あなたのご意見・感想をお送りください。 あなたの一言が大きなはげみとなりますので、どんなことでもどうぞ。