開発時の苦労話などを集めてみました。
やっぱり、ピボットの位置決めが最も重要なカギを握っています。
じつは、最初から Quick3 を採用したわけではありません。
まず最初に考えたのが、ピボットの格納位置をセンターに置いておき、必要に応じて左右に動かすという方式。例えば、左から右へ向かってスキャンポインタが動くわけです。もし、スキャンポインタがピボットの位置まできたら、その時はピボットを少しずつ右に動かしながら継続するという方式です。
フローティングピボットと呼べば格好いいのかもしれませんが、やる前から、「あんまり動かせば遅いだろうな」と思っていましたが、やってみないと本当のところがわからないので、さっそくテスト。
ハイ、見事に遅かったです。撃沈という感じで。
そこで、ピボットの格納位置を末尾に移動し、もし、重複した別のピボットが現れたら、同じように末尾側に移動させる方式にしました。つまり、スキャン中にピボットが現れると、どんどん末尾側にため込む方式。
スキャン作業が全部終わったら、末尾にあるピボットと入れ替えると、きれいな位置にピボットが座席指定できました。第1弾に比べれば、圧倒的に速い。ですが、Quick3 を使ったものに比べると、200ms ほど遅かったんです。その 200ms をどうにかするのが次の課題になってしまいました。
そこで、結局 Quick3 と同じ方式で、順方向スキャンで発見したピボットは先頭側の位置に、逆方向スキャンで発見したピボットは末尾側の位置に書き込むようにしました。
とりあえずテスト。今度は速度的にも OK でした。そこで、ソースリストをもう少し綺麗にしようと編集していたのですが、どう見ても Quick3 に限りなく近い。
だったら、Quick3 をそのまま使う方が、Quick3 の作者さんにも迷惑にならないし。ということで Quick3 を使うことにしました。だったのですが…
ところが、Quick3 に変更して、いざ動かしてみると、重複ピボットのときに、座席指定から漏れてしまうピボットが出てきました。次回の処理に一緒に含められています。例えば、4個の重複ピボットがあるとき、3個は指定位置に移動するのですが、1個がはずれた位置に移動していました。しかも、よりによって指定位置と交換作業をしている最中に、その現象が発生していました。つまり、交換作業そのものが、位置を壊していたんです。サンプルデータだと、3個とか4個とかのレベルですが、実際の場面ではもっと数が多くなることもありますから、大変です。
高速処理のためには、1個でも少ない範囲で次回を呼び出すというお題でしたから、この1個をどうにかすればよいのですが、この作業が一番時間がかかりました。
結局、位置の補正をしなければいけないけれど、交換作業の後で補正するのか、交換作業より前で補正するのかという結論になりました。ですが、いろいろやってみて採用したのが、それ以前に、ソートを行う前に補正するのが最も効率的という結論になったわけです。ソースリストだと、ピボットを採用した次の while 文の処理の部分になります。同一定数キャンセラーも兼ねています。
この結論が出るまでに、何十本ソースを用意したことか。
ピボットを指定位置に動かす前後の付近ではなく、もっと離れたソート開始前の位置で補正したのがポイントですかね。局所的なところばかりを見ていたなら、その発想は出てなかったと思います。
ただ、改造版 Quick3 だけでは、速度性能はまだ不十分であることを付け加えておきます。メディアンキラーにも弱いですし。
今回は公開したソースリストの範囲ですが、まだまだ手を入れられる部分があるんじゃなかと思います。
L1 キャッシュでの残存時間という観点からみると、少しもったいないなぁ、キャッシュにデータがあるうちに、他のこともできないかなぁとか考えます。
別のところでは、Quick3 の場合、E フラットと F シャープの位置のデータは、速度性能の小さな因子になっていますから、手を加えたほうが良いのかもしれません。これは Quick3 固有の現象です。公開ソースでは手を加えていませんが。
ただ、ずいぶんと長い時間ソートばかりの毎日だったので、考えるのをやめにして、しばらくはお休み。
大学とか、法人の研究だと、こんなソートのような基礎部分は、基礎過ぎて誰も研究していないのが現状です。
とすると、個人のみなさんが、頑張るしかないですね。
人間がソートするときは、値を格納するときに、「できれば、もうちょっと先頭側に…」とかやります。これは、周囲の値との変異量を見ているからです。これができれば人間の動きにも近くてよいのでしょうが、文字列の時は変異量をどう表現する? とか、いろいろ問題あります。創意工夫で少しずつ解決できればいいですね。
人間だとできる、「飛び飛び格納」方式は、シェールソートやコムソートもそうなのかもしれません。「飛び飛び格納」の可能性は、もしかすると未知のネタが隠れているのかもしれません。
でも、本当に速い処理が必要なときは、回路設計込みでやったほうが速いんですよね。コンパレーターとトランシーバーを組み合わせれば、ハードで3値のソートとかできたりします。メモリマップド I/O にしないと遅くなりますが。
ところで、ソフトウェアの場合、情報の最小単位は 0 か 1 か、どちらかを表すことになります。これに対し、ハードウェアの場合は、「どちらにも関与しない」という、合計で3つの状態があります(レベルの話。実際は加えてエッジという重要な要素がある)。Quick3 の場合は、比較結果が大きい、小さい、同じという3つの状態に着目したわけですから、似たような考え方と言えるのかもしれません。
あまりにも大きなデータだと、ハードディスクとの転送が一番時間がかかるので、ソートだけ速くなっても実質無意味ということもしばしばあります。
今回のテストのように、キーが4バイトとか、8バイトという使い方は多いのではないでしょうか。
このような「扱いやすいサイズ」の場合には、ビットスキャン命令をソート前に適用すると、より高速になることもあります。
これは、BSR 命令を使い、本物のゼロの値と、BSR 命令で得られた先頭は何ビット目にあるかという情報を使い、33 のグループに事前に分離します。方法は、カウンティングソートとほぼ同じです。
データの存在するグループを、小さい方から見ていきます。レコード数が1以下のときは、そのままソート済みの扱いになるのでスキップします。2以上の時は、そのグループ内のみ内側をソートします。これを、上位方向の最後まで展開します。
この方法を使うと、メディアンキラーなどの苦手なデータも、化けてしまいますし、小さな単位のソートに変身しますから、速くなることが多くなります。実際、このホームページのサンプルデータも、この処理をしてから♪ドレミファソートやクイックソートを呼ぶと、数百ミリ秒ほど、速くなります。
ちなみに、BSR 命令のみでソートしようとすると、メモ書き領域を使うため、それほど速くなりません。qsort 関数よりは速いですが。ただ、この考え方を使うと、超巨大なファイル(数GB)のソートを速く実行できます。メモ書きの部分をワークファイルに置き換えるだけです。もっとも、ディスクとの転送レートも大きな速度要因になります。
データに何らかの規則や法則があって、取扱い範囲が決まっているような場合は、クイックソート系にこだわらず、専用ソートが一番最適です。ちゃんとした業務用ソフトは専用設計されているものがほとんどです。
例えば、100 点満点のテストだとデータの範囲は 0 〜 100 に固定されているわけです。すると、Radix ソートとか、カウンティングソートなども当然候補になります。ただ、作業領域に転記するタイプは、思ったほど速度が出ないことが多く、レコード長の影響を受けやすくなります。
こだわらずに、見方を変えることは大切です。
バブルソートであっても、横方向にとらわれず、最初の1回だけ、縦方向にソートすると、比較回数は若干増えるものの、交換回数が半分程度に減ることもあります。これは、飛び飛び方式を使うことで、データの移動量が減らせるからです。
英語だと、The Tortoise and the Hare だそうです。
ソートとは全く関係ない話です。どうやって、速度を上げるかという話ばかりなのに、水を差すようですが。
文字列の長さを検出するのには、strlen という関数があります。もちろん、若干違う名前の関数やシステムコールなどもあることでしょう。
この strlen は、基本としては、テキストの末尾を意味するコード、普通はゼロですが、それを1文字ずつ確認しながら文字列の末尾まで繰り返します。
なんですが、高速化のために、4バイトを1回で読んだ最適化や、8バイトを1回で読む最適化などを行い、少しでも速く実行することが多いです。
ほとんどのケースではこれで良いのですが、場合によっては、これが困ることがあります。メモリ管理ユニットを使っている場合で、メモリ区画の末尾付近にデータがあるときです。Windows でいえば、VirtualAlloc を使うときがそうです。実は Microsoft も途中で気が付いたようで、一応修正版を Windows XP のサードバージョンから取り入れたものの、中途半端で不完全。といっても、HeapAlloc のバグよりましですが。
メモリ区画の末尾で1文字ではなく、何バイトか読み出そうとするときに、区画の境界を越えてしまうケースがあります。そうすると、保護領域のアクセスをしたという意味で、システムが思いっきりエラーを出してくれるわけです。めったにないことですが、実際に発生します。XMM レジスタで行うときなどは、特に注意が必要になります。保護違反を検出したら、切り替えて…ということも一応可能ですが、これがやたらに面倒。
結局、遅い方が確実で安心というケースも結構あったりします。
インターネット上で、C言語講座などがありますが、まったくもっていい加減のかたまり。日本人は知能が低いので、まともなプログラムなんぞ作れないのが実情です。ところが銭儲けのために、でたらめ極まりないものを確認もせず書籍を発行する出版社や新聞社などもあり、日本製のソフトはまったく信用できません。しかも、派遣ばっかりだし。数え上げればきりがありませんが、代表的な事例を3つ。
その1 Window のメッセージループ
よくある例
while( GetMessage(& msg, NULL, 0, 0 ) )
{
TranslateMessage( &msg ); DispatchMessage( &msg );
}GetMessage 関数のヘルプを見ていただければ一目瞭然だが、このようなコードは避けてくださいとわざわざ書いてあるにもかかわらず、何の下調べもなく平気で使うのが日本人の特徴。もし、このようなコードを発見したら、その記事のサイトはすべていい加減なものと思って間違いない。
その2 何の変哲もないループ
よくある例
int i;
for( i = 0; i < 1000; i++ )
{
/* ここで何らかの処理 */
}このようなコードを掲載するのは MS-DOS 時代に束縛されている低知能者だけ。どうしてこのコードではダメなのかわからない人はいますぐプログラミングなんぞ辞めることをお勧め。他人の迷惑になるだけでしかありません。
その3 共有空間のフラグの書き込み
マルチスレッドで一斉に中断処理を要求するとき、共有空間にフラグを用意して起き、スレッド側はときどきフラグを確認して中断処理をするという、よくある事例。ところが、共有空間のフラグの書き込みで、
bFlag = TRUE;
というコードを平気で書く。もはや、どうしようもない。
ソフトの外部発注だったら、スイス、ハンガリー、ポーランドといった国の会社が優秀なのでお勧めだが、最近ではインドも高品質ソフトで充実している。しかも、安価。このようなコードしか書けない日本製のソフトとは質が全く違うのですよ。
「私的数学塾」さんにリンクしていただきました。ありがとうございました。興味の出る数学の記事がたくさんあります。
contents |
Top Page caution Bubble Sort Odd Even Sort Cocktail Sort Gnome Sort Selection Sort Min Max Sort Insertion Sort Shell Sort Heap Sort Comb Sort Merge Sort Quick Sort Do-Re-Mi-Fa Sort |