健全なウソと、不健全な真実。どっちをとる?
二分探索について。かの Knuth先生は 「二分探索はアイデアこそ単純だが、細部はおそろしく厄介で驚ほどだ」と語ったらしい。 Jon Bentley が実験したところによると、二分探索の関数を書かせたプロのプログラマのうち、 正しいコードを書いたのはたった 10% なんだそうな。 たしかに二分探索はやっかいだ。quicksort とか min-max もそうだが、 こういった基本的な (完璧な正確さが要求される) アルゴリズムをバクなしで 実装するのは実は結構むずかしい。コード屋としての実力を計るには、 (インチキしなければ) ある意味これだけで十分にバロメータとして機能しそうである。
さて、どこがどう難しいのか? …おおまかな部分は誰でもみんな知っている。しかし、
通常の二分探索では、配列中のある一定範囲の要素をとりだし、
その中央値を見て要素を狭めていくことになっている。
たとえば、3要素をもつ配列 a = [2,3,5]
を考えよう。
この 3要素を探索範囲とした場合、最初と最後の添字 (それぞれ i0, i1 としよう) は 0 と 2 になる:
しかし、ここで探索範囲として「配列の要素の位置そのもの」ではなく、 「要素と要素の間の境界」の座標を使ってみる:a: [2] [3] [5] 0 1 2 ^ ^ i0 i1
こうすると何がいいのかというと、 配列中に存在しない値を検索したときの答えをわかりやすく返すことができるのだ。 以下のコードはそういう二分探索を Python で書いた例だる:a: [2] [3] [5] 0 1 2 3 | | i0 i1
これを実行すると、以下のようになる:def bsearch(seq, n): i0 = 0 i1 = len(seq) while i0 < i1: i = (i0+i1)/2 x = seq[i] if n == x: (i0,i1) = (i,i+1) break elif n < x: i1 = i else: i0 = i+1 return (i0,i1)
bsearch([2,3,5], 1)
→ (0, 0)
bsearch([2,3,5], 2)
→ (0, 1)
bsearch([2,3,5], 4)
→ (2, 2)
bsearch([2,3,5], 6)
→ (3, 3)
(i0, i1)
のような2要素のタプルとして返す。
これは a[i0:i1]
間に答えがあることを示しており、正確な値が見つかったときは
(0, 1)
のように 1つだけ差がある値を返す。
これは境界 0 と境界1 の間 -- つまり a[0]
-- に答えがあることを示している。
いっぽう正確な値が見つからなかったときは i0 == i1
となるタプルを返す。
たとえば 4 を検索したときの (2, 2)
という答えは、この数値が
境界 2 上 -- つまり a[1] と a[2] の間 -- にあることを示している。
ここでいいのは、(0, 0)
とか (3, 3)
という答えを返すことで
「配列の一番最初の要素のさらに前」とか、
「配列の一番最後の要素のさらに後」といった解答を無理なく表すことができることだ。
そうゆうことです。。。 (オチなし)
安息日に働くやつは、石をぶつけて殺すべし。- Exodus 31:15
(追伸) さ、、っき、「ウギャー 流し台にでっかいクモがいる! しかも腹のあたりが微妙に赤っぽい!!」…と思ったら、 それは自分がけさ捨てた (はずの) トマトのヘタだった。 こわいこわい。
そもそも、digg や reddit で人気が高い記事 (digg がいやなら「はてなブックマーク」でもいいよ) で 本当にマトモなものがいったいいくらあるのか? 本当に? 額面通り判断して? …実際には、(新山が観察したところでは) ヒトは「額面」をほとんど見ない。 かわりに額縁ばかり見ている。 新山はこの手のサイトを生涯に2〜3回しか見たことがないが、 どんなサイトだろうが、いついかなる状態でもこの傾向は絶対に変わらないと断言できる。 それでも人気システムにだまされるアホが後をたたないのは、結局のところ、 モギ健一郎にだまされる人とか、iPhoneにだまされる人とかが後をたたないのと同じだ。 実際には、ほとんどの人々 (新山をふくむ) は「合理的な選択」などしたくないのである。 ただ、そう見せかけておくとカッコよさそうなので、そのための言い訳として 血液型とか、脳科学とか、“モナドによる単量子化プログラミングの並列化”などの鎧を着たがるのだ。 (しかしそれがほんとに「鎧」になっているかどうかは、本人がいちばんよく知っている。) …話をもどすと、だから digg なんか見るのは時間のムダであり、 ついでにそのことについてあれこれ書くのはもっと時間のムダなので、もうやめる。
(追記) ちなみに、米国にいたころ、某カタツムリの館などに行くと、 そこに置いてある「作品」があまりにもワケわかんないものばっかりなので、 美術作品そのものよりも、作品の脇についてる解説ばっかり読んでる人をわりとよくみかけた。 こういうのは典型的な「額面よりも額縁をみる人」である。 結論: 無理すんな。 ワケわからんと思ってるのはおまえだけじゃない。
いままで、event と callback って意味的にどう違うんだ? とずっと思っていた。 ほとんどの C# の解説書では、event のメカニズムの話だけが書かれていて、 意味的な解説にまで踏みこんでいるものがサッパリ見つからない。しょうがないので、 きょう Pro C# 2008 の第11章をうんうん言いながら読んで、 やっと自分なりに理解できた (と思える) ことを書いておく。
基本的に、 C# における event とは、callback (C#用語でいうところの delegate) に毛をはやしたようなものである。 これはある事象の発生を多数のオブジェクトに対してブロードキャストできるよう、 複数のcallback を登録できるようにしたもので、機能的な違いだけを見れば、 べつに event と callback の間にあんまり差異はなさそうに見える。 だがこれは仕組みの話であり、意味的には event と callback はまっったく違う目的で作られている。 これは「どういう場合にどちらを使うべきか」という疑問にわりと明確な基準を与える。 その基準とはこうだ: C# における callback とは、オブジェクトが 1対1 で通信するときに 使われるもので、つねに送信元と宛先がある。これに対して event は宛先がなく、 ただ「起こる」だけ。
これを具体的なたとえで説明すると、たとえば callback というのは、 自分の身体の具合が悪いときに、家族や上司や医者に向かって「私は具合が悪いです」 と伝えるようなものだ。ここにはメッセージの明確な“宛先”が存在する。これに対して、 event というのは「オレは具合が悪いぞ〜!」と大声で宣言する (あるいは具合が悪そうに道端に倒れる) だけである。願わくば、それを見た人が救急車を呼ぶなり、 なんらかの対応をとってくれるかもしれない、と期待して。 英語圏ではよく C# の event は "fireする" という 表現が使われるが、ようするに C# のイベントというのは「自分で勝手に爆発してるだけ」なのだ。 必ずしも、誰か見てる人間がいるとは限らないのである。
で、技術的な話に戻ると、C# の event と callback には以下のような違いがある:
…そういうことです。 もっと別の言い方をすると、C# における event は、デザインパターン (←この言葉嫌い) における publisher-subscriber パターンそのものだ。pub-sub パターンの特徴とは何か? それは「比較的頻度の少ない、散発的な情報を、すべての必要な受け手に行きわたらせる」ことである。 まさに C# の event とそっくりだね。いままでは、pub-sub の実装に必要な機能が 言語レベルで提供されることはあまりなかったが、C# ではそのための機能がきちんと選別され、 event という概念で実現されているわけである。
ちなみに、マイクロソフトが好きになったわけでは決してないよ!
さて、ここから文句になるのだけど、新山がほとんどのプログラミング言語の解説書を見て
「…ダメだ」という気分になるのは、こうしたプログラミングの構成要素の概念的・意味的な
解説に踏み込んでいる書籍がほとんど (あるいはまったく) ないからである。洋書でも和書でも。
ほとんどの本は、ただ技術的な説明のみを載せていて、それが実際の設計時にどう適用されるのか、
まったく、ヒントの断片すら与えてない (ここでいう“実際の設計”ってのは、ゾウさんの数を数えるとか
そんな幼稚園児向けの問題じゃないよ、中小企業の販売管理システムとか、そういうもののことだ。
なぜならほとんどのプログラマはそういった仕事をしてるんだから。)
だから実はああいう本を書くやつにマトモなプログラマなんていないんだろ?
…と新山がちょっと思っても、仕方がないだろう。なぜなら、そこそこの複雑さのシステムを設計するときに
「for
を使うのと while
を使うのと、どっちが効率がいいか?」みたいな
tips的な話は、完全にドーーーでもいい小手先の問題だからだ。はっきりいって、そんなことばっか気にしてるから
まともな設計ができるやつが少ないんだと思う。システム設計において重要なのは、
ある概念 (または使ってるデータ型) について、ほとんど完璧な、
境界のはっきりした理解をもつことだ。実装が完璧にならなくても後からなんとかなるが、
問題に対する理解が完璧にならないことには絶対にまともな (混乱しない)
システムはつくれない。みんな、このことを本当に本当に本当にわかっているのか?
…このような状況において、event と callback を技術的にしか区別しない解説書というのは
お粗末としかいいようがない。「簡単さ」ばっかり宣伝して、
プログラマーを素人の領域に閉じこめておこうとする本にはもううんざりだよ。
プログラミングが簡単なワケがない。
といって、これが一部の「選ばれた人間」にしかできない職人技だという主張も、
おなじようにこっぴどい嘘である。
人間はみんなプログラミングなんかよりもはるかに微妙で、複雑かつ精密な計算が必要な
「人生を生きる」という作業をなんとかやりくりしている (ように見える)。
まあ、どれくらい立派にやりおおせてるかは、わかんないけどね。
しかしこのアホさ加減がいつまで続くのかも気になる。 現在の新山の書く文章は、たとえば5年前 (といってもたかだか2004年だ…) の文章と比べて なんらかの変化がみられるものだろうか? まあ、前よりもたしかに量は減ったと思う (なんしろ、以前は大学からも日中、自宅サーバにログインして書いていましたからね)。 そして微妙にテンションも低い。でも、これが成長とゆうものなんだろうか? うーむ。
デンピーな文章の少なさに関しては、いまはわりとテンションが低いとき (夕食後) に日記を書くことが多いからだと思う。いまの新山は午前中にかなりテンションが高いのだが、 その時間はすべて会社でコードを書くのに使っている。新山が自分で「頭がよく働いてる」と 思うときというのは、じつは同時にもっともデンピーな度合も高いときなのだ。したがって、いまの新山は 会社でキチガイ的な日記を書くかわりに、その「キチガイ性」をコードに埋めこんでいる 状態ともいえる。こういう仕事っぷりがいいかどうかは知らないけど (certainly not exemplary)、 たいていの日はいちばん厄介な部分を昼前のピーク時に生産し、同時に設計や構成も この時期にいちばん激しく変更される (そういえば、commit log の時刻で統計をとったら面白いかもしれない)。 で、あとの午後はほとんど死んだ状態。 ほかの人からも「新山は午後はただの廃人」であるということは認知されているのだが、 こんなことでオレはマトモな社会人になったといえるのか。 いえないんじゃないか。どうでも夜露 (よつゆ)。
…てくるで最近思うこと。C# はかなり快適だ。これは IDE が快適という意味ではない (ちなみに開発環境はいまだに Emacs と make だ)。Python プログラマであれば、C# は かなり感覚的に使える。新山は closure 愛好者だるので、Java などを使うときは結構、 考え方を変えないといけなかったのだが、C# なら delegate が使えるのでそんなこともない (最近のやつは lambda も使えるし)。dot NET でクールだと思ったのは、 ある特定の言語に固有の構文 (たとえば、C# のforeach など) を、名前決めうちの インターフェイス (IEnumerable など) をつかって実現できることである。 これは、かしこいよなあ。新山は言語仕様の単純なのが好きなので、この原理に従えば 本来オレは C# よりも Java のほうが好きなハズなのだが、でもオレは 単純でも「タイプ数が多い言語」は嫌いんだよ (最近のJavaは知らないが)。 Java の、あの、ダラダラと長くなる仕様は許しがたい。 いっぽうで、PerlやC++のように、人間の言葉でない記号を必要以上に 使う言語も醜いからキライである。オレは、わがままなのだ! (あるいは、ぜいたく猫。)
どうでもいいけど (てくるで)、昨日とある外資系企業の日本支社に行ってきた。 都心の一等地にあるリッチそうなビルで、周囲には am/pm とか Tally's Coffee しかないようなところだ。やたら静かで高速な味気ないエレベータ、 気分の重苦しさとは裏腹にキセノン的に明るい廊下、 VXガスで滅菌されてるんじゃないかと思う生活感のない給湯室などなど、 いわゆる最近の日本に多い典型的な「新ピカのビル」である。 まあ、オレに言わせれば「SFに出てくる墓場」のごときオフィスだったね。 とうぜん新山はこういうところが嫌いなのだが、それはなぜかといえば、 ウソくさいからだ。オレはああいう建物を設計するやつに尋きたい、 いったいあんたらは日本人をどんな類の精密器械だと思ってるのかと。 おそらく設計時には「よかれと思って」いろいろ考えた末なのだろうが、 人間の性質とでもいうものを軽視しすぎているために、現実の運用時にはそれらの思惑が どうしようもなく裏目に出るのである。しかも、中途半端に最適化されているために 修正がきかない。コードだけでなく、建築においても "半端な最適化は諸悪の根源である (Knuth)" の格言は成り立つんだなあ。
そういえば、むかし東工大に西8号館ができたときにも同じようなことを考えた。 新山はあの薄汚い (塗りかえられる前の) 本館やS3棟が好きだったのだが、 新しいビルに移ったら、やたら規制ばっかりきびしくなり、研究室で鍋もできないし (新山は鍋奉行だったのでこれには著しく不満だった)、 雨の日には建物全体がゾウキン臭くなるわで、まったく最悪だった。 それでもあの建物にはかなり金をかけたはずで、見た目だけはやけにキレイなのである。 そういやー、JAIST もそんな感じだったな。あそこに行ったとき 「こんなとこに長年いたら精神が破壊されるだろう」 と思ったもんだ。もし日本のIT技術者がみんなああいう建物につめこまれていたら、 彼らが精神に異常をきたすのも理解できるのである。
さて…そういうわけで、めずらしくこういう場所へいって、 自分のいまの環境がいかに恵まれてるのか、あらためて再確認させられてしまった。 なんしろ、うちの会社にはこの手のウソや気取りが一切ない (たいていの中小企業にそんな余裕はない)。 朝は自転車で通勤して、お昼にはスーパーで買い物しつつ古本屋をあされるし、 外食しようと思えばひなびた定食屋がいくつもある。電話がかかってくりゃ、 大声で「○○さ〜ん!」と呼ぶし、社長に向かって軽口もたたけるし、 休憩時には非常口に出て、道ゆくアホ学生の流れをぼんやりと見つつコーヒーを飲む (新山はいつもこの場所で資料も読んでいる、ちなみに Pro C# 2008 は第9章まで読んだ)。 そして週末には銭湯へいって、コインランドリーで洗濯して、築20年のアパートの窓から干してる。 生活のあらゆる部分ですこしも無理がないので、ストレスもない。 まあ、こういう生活にあこがれて日本に帰ってきたのだけど、NYにいたらやはり こうはいかなかっただろうと思う。なぜなら米国の基準で「無理がない」状態でも、 やはりそれは新山にとって「自然な」状態とはいかないだろうから。
それにしても、ああいうアホな建物へいくたびに思うのだが、つくづく日本人は「うわべだけ取り繕う」のが好きだと思う。 まあ、実際にはこういう現象はどこの国にも見られて、たんにその表出の方式がちがうだけだろうけど…。 たとえば欧米では (大げさに言えば) 「刑務所にもゴシック調の装飾を使う」といった感じの 風潮なのに対して、アジアではこれが過剰に効率主義的・近未来的というか、 「どこでもMoMAみたいな建物で生活する」のがオシャレだと思っているらしい。 どうでもいいけど “近未来的”って便利な言葉だね。ここでいう「近くの」未来は、 永久に「近い」ままで、現実とはならない。近未来の近は、近視の近だ。それらはあまりにも浅い考察にもとづいており、 冗談としてしか受けとられない。iPhoneが個人の生活をどう変えたのか、誰かおバカな新山に教えてくれよ!
…しかし、携帯電話についていえば、いまの日本人は「世界的な流れであるタッチパネル式 インタフェイスの非効率性を見抜く」ほどに進化をとげており、ガラパゴス化だろうがなんだろうが、 「近未来」どこではなく、真に「未来化」してしまっているようだ (iPhone を褒めてる一部の欧米コンプレックスを除く)。 それでも、電車の中で必死に携帯のボタンを押してるサラリーマン風の男が、 新山よりも「改善されている」とは、なぜか思えないなあ。
生物学的には、死というプロセスは複雑かもしれないが、まったくワケわからん、というものではない。 しかし精神的な (って何?… とにかく、生物学的な意味以外での) 「死」というのはまったく ワケわからんものである。
そもそも「人が死ぬ」というとき、われわれはなんとなく その人をひとりの (不可分な) “個体”として扱っているが、 実はこれが結構あやしい。新山が死んだとき、オレは本当に死んでるのか? … いや、たぶん死んでるのだろうが、そもそも本当に「オレ == 新山祐介」だったのだろうか。 よく考えてみると、この2つは必ずしも完全に一致しない。 たとえば、もし新山がだれかに臓器提供をしたら、すくなくともその部分の 「新山」は、まだ生物学的には生きてるよね。でも精神的には死んでいるのだろうか? それもナゾだ。精神的にだって生きてることもあるといえる。 なぜなら、新山のことを知っている他人はまだ存在するのだから。 そう考えると、現代のほとんどの人は、たとえ墓が立てられたあとでも 完全に「死にきれていない」ことがわかる。その人に子供がいたら もっと「死にきれていない」だろう。ほかにも、昨日の新山祐介と 今日の新山祐介は、ほんとうに同一人物か? という疑いがある。 自分ではそう思い込んでいるけれど、それを証明してくれるものは何もない。 もしかすると、昨日の新山祐介は殺されていて、今日のオレは新しく生まれた新山祐介なんじゃないだろうか? なんしろ意識が途中で断絶してるんだから、あやしいよな! 名前が一致するだけじゃ不十分である。プログラマとしては、参照が一致しなければならない。
…このように新山は「個人」というものに対して非常に混乱した (ある意味、ふざけた) 見方をしているので、いまのところ個人の死についてもワケのわからん見解しかもてない。 たぶん、状況がくればもっとちゃんとした意見をもてるのかもしれないが…。 いまは、何もかもボワーっとしている。 そもそも新山の感覚では、個人というものは、量子力学の雲のように広がっていて、 一カ所に存在していない。だから新山は「個性」を主張するし認めるが、 「自己同一性」は主張しないし認めもしないように見える。 これはなんだかアホっぽい。個人のアイデンティティを認めなかったら、 それは同時に個人の責任というものも認めないことになるんじゃなかろうか? なぜって、オレは「今日の自分」と「明日の自分」が同一人物かどうかわからん、 といっているのだから。とにかく新山が確実にいえるのは、 「この世界は、いつだって、油断がならない」ということだ。 『我思う故に我あり』なんていってるようでは、まだ甘いのである。 しかしオレがどれほど混乱していようと、病的な考えをもっていようと、 新山の身体はパーフェクトに動き、腹もへるし眠くもなる。 オレは世界に感謝しなければね。…
で、なんの話だっけ?
これ、なんかのCMに使ったら絶対ウケるだろう。
「ぼかぁ」
「つまり」
「基本的に」
「ほら、あれだ」
「その〜」
すまん、10個もなかった。 しかしこの台詞を上から順に言っていけば、新山祐介のできあがりである。 ふんげあ (← ちなみにこの台詞は書き言葉でしか使われず、つまりは口癖ではなくて「書きぐせ」ってことになる)。 あと、寝癖も。
しかし、味は変わっていないんだね。…
「誰のためのモラル??」
(D. Norman 風にいうと、Moral for Everyday Things)
それを問えと。
てくるで (ところで)。
きょうは生まれてはじめてバリウムを飲み、「白いウンコ」を体験したのでここに記しておく。 きょうは電車で行ったのだが、帰りの電車の中でまた下剤が fire up するんではないかと ちょっとヒヤヒヤしてた。まあ、わりと面白かったと思う。
ほとんどの分野において、素人がそこに近づくことは勧められない、という場所が存在する。 なぜなら、迷うから。
しかしオレが一体、素人じゃないという保証がどこにあるだろうか?? ¿
Document ID: 846f798844d1e0f8d39151028559d8df
Yusuke Shinyama