今日は、アントニー・ホーアの誕生日(1934)
コンピューター科学者で、クイックソートの考案者です。
わかる人には「じゃがいもソート」を思い出してもらえばいい。
…もう４年前になるのか。今では毎年正月の恒例となったNHKの教育番組「大人のピタゴラスイッチ」の、初めての放送時に紹介された動画でした。
ジャガイモの重さを比べながら、軽い順に並べていく。この際のアルゴリズムが、クイックソートでした。
＃ちなみに、「しめじソート」もあり、しめじをマージソートで長さ順に並べていました。
ソートというのは「何かを基準に並べること」です。
いろんなアルゴリズムがあるし、適材適所で使い分ける必要がある。
クイックソートは、考えられた当時としては超早かったので「クイックソート」と名付けられましたが、今ではもっと高速なアルゴリズムもあります。
でも、ソートって「理想的な場合」と「最悪の場合」で速度が違うのが普通だし、理論上は速くてもプログラムがややこしくなるのであれば結局遅いし、今でもクイックソートはイイセン行っています。
上は YouTube にあったソートアルゴリズム比較。真ん中がクイックソートです。
繰り返し、いろんな条件でソートを行っているのだけど、クイックソートが平均的に速いのがわかります。
ソートっていうのはアルゴリズムの基本で、いろんな考え方がある、くらいには知っておいた方がいいです。
プログラマでない限り、詳細に知っている必要はないけど。
「検索アルゴリズム」も基本なのですが、検索前に並べてあるのが前提というのも普通だったりもします。
だから、やっぱりソートは重要。
例えば、辞書はすぐに目的の語を検索できます。
これは、辞書の項目が「あいうえお」なり「ABC」なりの順にソートされているためです。
そして、ソートアルゴリズムの中には、「すでにソートされている」ことを前提に、新しい要素を入れる場所を高速に探し出すものもあります。
これ、「ちょうどよい位置を探す」なので、検索アルゴリズムなのね。ソートと検索は密接な関係にあるのです。
「順番に並べる」ための方法をソートと呼ぶので、何もすべてが「計算機で実行できる」わけではありません。
昔、「パスタソート」という話を聞いたことがあります。折れてしまったパスタを長さ順に並べる方法。
パスタをまとめて立てたら、「輪っか」を下から持ち上げていくだけ。
短いものから順に、支えを失って倒れます。倒れたところを傾斜にしておけば、転がって短い順に並んでくれます。
僕は世代じゃないので実際に見たことが無いのだけど、昔の図書館では目録を「検索カード」で管理していたそうです。
著者名順とか、署名順とかで並べられている箱があって、その中でカードを探し出せば、どこの棚に本が置かれているかわかる。
カードの上部…肩の部分には、すべて同じ位置に穴があけられています。
でも、この穴は、「穴」として存在しているものと、穴の上部を切り欠き、カードの辺の「凹み」として存在しているものがあります。
カードを束にして、穴に棒を通して持ち上げると、「穴」のものだけが釣り上げられ、「凹」は下に残ります。
これで、カードを２つに分類できました。
実は、穴は複数空いています。
カードを２つに分けた後、それを「前後」になるように束にして、再度別の穴で持ち上げる。
実は、穴か凹かは２進数になっていて、繰り返すことでカードの束を順番に並べられるのです。
（下の桁から繰り返し、最後に一番上の桁を処理すると、ちゃんと並ぶ）
これもまた、ソートアルゴリズムです。
僕が作るようなプログラムは、ゲームなんかが多いので、使うのはもっぱら挿入ソートです。
非常に単純なアルゴリズムで、あらかじめソート済みの時には十分な速度で動く。
10位までのハイスコアランキング、とかなら全く問題ないし、アルゴリズムが単純なのでむしろ速い。
３Ｄ描画のためにポリゴンをＺ軸に従って順次並べる…なんてことになると、もっと高速なアルゴリズムが必要になります。
何百も、場合によっては何万ものデータを、かなり短い安定した時間で並べる必要があるからね。
Amazon とかでお買い物をすると、他の類似商品をお勧めされることがあります。
これもソートアルゴリズム。何らかの指標で購入製品と別の製品の「類似度」を測り、類似度が高いものから順にお勧めしているのです。
同じように、google 検索も検索文にマッチしたものの中から、様々な指標で「お勧め度」を算出して、ソートして表示しています。
ページそのもののお勧め度もあるし、更新日付の近さや地理条件なども順位に関連する。
だから、同じ検索内容でも、日によってソート順序が変わったりもします。
何十万もあるページの中から瞬時にソートするには高度なアルゴリズムが必要です。
コンピュータープログラムでは、ソートは基本です。
今の世の中はコンピューターがいたる所にありますから、そこらじゅうソートアルゴリズムだらけ。
もちろん、用途に応じて新しいソートアルゴリズムなんかもまだ考案されたりしています。
でも、クイックソートは古典でありながら、今でも十分利用されているソートアルゴリズムの一つです。
同じテーマの日記(最近の一覧)
別年同日の日記
申し訳ありませんが、現在意見投稿をできない状態にしています。 |