ああ、目覚めの珈琲は美味しい。
湿度はかなり低いが、相変わらず日射しは厳しく、暑い。
夕方帰宅。
お風呂に入ってから夕食の支度。
御飯を炊いてだしをひき、
鰤の照り焼き、高野豆腐と若芽の卵とじ、小松菜のおひたし、もろきゅう、
油揚げと葱のお味噌汁。
一汁三菜のつもりだったのだが、手を止めないようにしていたら一品多く作ってしまった。
今日もまた、小麦粉を塗るための刷毛が欲しいな、と思ったのだが、
常に「またこんど」になる。
でたらめに並んだものを正しい順番に並び換える、という事務仕事はしょっちゅうある。
言わゆる「ソート問題」だが、これには「クイックソート」と呼ばれる素晴しいアルゴリズムがある。
これを知っていると日常でもけっこう役立つ。
沢山の伝票を何かの順番に並び換えたいとしよう。
まず適当に一つ伝票を選ぶ。そしてこれよりも「大きい」伝票たち、
「小さい」伝票たちに分ける。
日常では大抵、これだけで手頃なサイズの二グループに分けられるので、
それぞれ自分流に並び換えて重ねればOK。
伝票の数がもっと多い場合には、各グループ内で再度同じことをすればよい。
この手続きを最後まで繰り返すことが、
アルゴリズムとしてのクイックソート、ということになる。
一方で、全体を並び換える必要はなくて、
並び換えたあとの何番目かだけを知りたい、ということも良くある。
簡単なのは最大値と最小値だが、この場合は考えるまでもない。
しかし、丁度真ん中だけを知りたいとか、
上からベスト3の三つだけを知りたい、という問題は自明でない。
これについても「クイックソート」の応用で、「クイックセレクション」と呼ばれる名案がある。
例えば、上から 5 番目だけを知りたい、としよう。
まず、適当に一つを選ぶ。
そしてそれより大きいものと小さいものにグループ分けする。
大きい方のグループに5つ以上要素が含まれていれば、この中に答がある。
小さい方は調べなくてよい。
大きい方のグループに4つ以下しかなければ、逆に小さい方のグループに答がある。
例えば三つしかなければ、小さい方のグループの 5-3=2 番目を探せばよくて、
大きい方は調べなくてよい。
これを繰り返せば、すぐに答に辿り着く。
ベスト3だけを知りたいという問題も同じようにできる。
こちらは「部分ソート」と言ったりする。
プログラミングをしていると、ソートについては大抵ライブラリにあるので、
自分で実装する必要はないし、実装しようとしてはいけない。
しかし、セレクションはライブラリにないことが多い。
すると、賢い人は上のアイデアを知っているので(あるいは自分で思いついて)、
自ら実装しようとしてしまう。
でも、これはよろしくない。
このアルゴリズムを完全に正しく、かつ効率良く実装するのは、腕利きにとっても想像以上に難しい。
自分で書くと大抵バグ入りで、かつ、それほど速くないのだ。
一方でライブラリの中のソートや最大最小値関数は、
枯れ切っている上に超高速実装されている。
だから、本当の本当にその必要がない限りは、
これらを使ってダサい次善策をとるのが筋だろう。
こういう見極めが状況に応じてできるのが、プロというものである。