クイックソートを習得した
6月7日の日記。
きょうは午前10時に起きた。正午とか午後2時とかに起きているのと比べるとかなりまともだ。あしたも早く起きたい。(午前10時というのは決して早起きではないが。)
部屋のごみを廃棄できたので良かった。
午前10時に起きたものの、お風呂に入ったりして、けっきょく出かけたのは午後4時ころだった。
図書館に向かったが、改装中らしく、6月9日まで使えないという。やむをえず施設に向かうことにした。(これで30分以上 無駄になった……。)
ちなみに、図書館は自宅から3~4キロあり、歩いて行く気にはならない(自転車かバスで行く。)。開館は午後7時まで。
施設(おそらく区が運営している。)は自宅から数百メートルだが、上り坂が厳しいのでできれば歩いて行きたくない。施設のほうは、ある時間帯までは子供が騒いでいて発狂してしまうので、基本的には図書館に行きたい。開館は午後9時まで。
『アルゴリズムイントロダクション』で、クイックソートを習得した。実装もできると思う。(そう言ってヒープソートのほうもまだやってないけど。次に行く前に実装しようかな。)
くるみ餅さんがアルゴリズムに興味を持ってくれていて、けさのつぶやきで「一回目に7より大きいグループと小さいグループを集めてーみたいな私が直感的にやっているのが名前がついていくつか手法があるわけだな?」というのがあったが、まさにこれがクイックソートである。
対象の要素の列(リスト)から、一つを適当に選ぶ(ピボットという。)。それで、ピボットより小さいか大きいかで2つのグループに分割して行く(“より小さい”と書いたが、ピボットと同等の値もあるので、実際には“以下”で判定する。)。そして、分割されてできた2つのグループそれぞれに対してさらに同じ分割処理を行なう(再帰的な処理)、ということを繰り返して行く。
ちなみに、この2つのグループは、『プログラミング作法』では「チビ」,「デカ」と呼ばれていた(原語ではなんて言うんだろう。)。
クイックソートのアルゴリズムはやや複雑で、『プログラミング作法』で見たときはかなり難しいと思ったけど、どういう動きをするのかという絵をイメージできれば難しくはない。改めて『プログラミング作法』を見てみると、同書の説明は正直言ってわかりにくい。図もわかりにくいし、コードもわかりにくい。実際にソートを行なう部分と再帰の制御を行なう部分が混在している。ひるがえって『アルゴリズムイントロダクション』では、どのような動きをするのか抽象的にイメージしやすい図だったし、コードは実際にソートを行なう部分がちゃんと関数になっていてわかりやすかった。
とは言え『アルゴリズムイントロダクション』は数学的・理論的な趣きが非常に強く、コードは擬似コードで,変数名はとかとか。意味のわかりにくい変数名だとコードを読んでいてわけがわからなくなってしまう。そこはわかりにくいので、自分で一般的なプログラムっぽく書きなおしてみたりした。
『アルゴリズムイントロダクション』では、ピボットを部分配列の末尾から選択するという,打たれ弱いアルゴリズムだったので、後日、より強いアルゴリズムについて考えてみたい。
- 作者: ブライアンカーニハン,ロブパイク,Brian Kernighan,Rob Pike,福崎俊博
- 出版社/メーカー: アスキー
- 発売日: 2000/11
- メディア: 単行本
- 購入: 58人 クリック: 1,152回
- この商品を含むブログ (207件) を見る
さて、クイックソートでは完全な配列を直接的に部分配列として扱うので、関数のシグネチャに、引き数として部分配列の範囲がなければならない。それで思いだしたことがある。
範囲は、言うまでもなく始まりと終わりの2つの値で表現するわけだが、終わりを表現するのに2つの方法がある。
// 部分配列をその場で分割します var partition = function(array, left, right) { // 省略 };
一つは、部分配列の最後の添え字(インデックス)で表現すること。いわゆる閉区間(いわゆると言うかまさしくか。)だ。もう一つは、部分配列の最後の添え字(インデックス)の次の値で表現すること。これは片方が開区間なので左閉右開区間というらしい。
問題なのは、人が作った,範囲を指定するタイプのプログラムを使うときに、この2つのどちらなのかがわからないということ。説明を見るか、プログラムそのものを見ることになる。
この問題に関して、引き数の名称をどのようにするべきかについて『リーダブルコード』で言及されていたことを思いだしたのだ。そこでは、「範囲を指定するときはfirst
とlast
を使う」,「包含/排他的範囲にはbegin
とend
を使う」と書かれていた。つまり、前述の閉区間の例ではfirst
とlast
を,左閉右開区間の例ではbegin
とend
を使うべきだということだ。
これが実際に常識的(一般的)なことなのかわからないが、そうだとして、どれぐらいのプログラマーがこの規約に従っているのだろうか……。私も平均的なプログラマーよりは勉強しているつもりだが、これは聞いたことがなかった。こういうのって少数の人が従ってもあまり意味がないと思うのだが、少なくとも私は従うことにしようかな〔『リーダブルコード』に載ってるってことで……(笑)。〕。
リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)
- 作者: Dustin Boswell,Trevor Foucher,須藤功平,角征典
- 出版社/メーカー: オライリージャパン
- 発売日: 2012/06/23
- メディア: 単行本(ソフトカバー)
- 購入: 68人 クリック: 1,802回
- この商品を含むブログ (132件) を見る
火曜日は「バトルシステム」の日だが、なにもやっていない……。そもそも夜にやろうとするからいけないんだろうけど……。
日付が変わる前に記事を投稿したかったが、けっきょく過ぎてしまった。