- 締切済み
qsort のアルゴリズムについて
現在Solaris上で作られたソフトウェアをwindowsに乗せ換えるポーティング作業を 行っているのですが、qsortの結果が一致せずに困っています。 比較関数で判定できる範囲は一致するのですが、比較関数が一致するデータ同士の順番が 一致せず、その結果出力される生成物の内容が異なってしまいます。 （同じ生成物が作成されなければポーティング作業完了と成りません） 多分qsortのアルゴリズムの違いだと思うのですが、Solarisのqsortのアルゴリズムがわかる方 いらっしゃいませんか？ Solarisのコンパイラは以下の通り Sun WorkShop Compiler Csparc 5.0 出来ればqsortのソースコードが有ればよいのですが、軸要素の決定方法だけでも解れば 幸いです。 いくつか、公開されているアルゴリズムを試してみたのですが、一致する物は有りませんでした。 （Windowsのソート結果とも違いました） 因みに、Windowsの開発環境は、 Microsoft Visual Studio 10.0 です。
- sin_zi
- お礼率0% (0/7)
- SE・インフラ・Webエンジニア
- 回答数7
- ありがとう数0
- みんなの回答 （7）
- 専門家の回答
みんなの回答
- t-okura
- ベストアンサー率75% (253/335)
- root139
- ベストアンサー率60% (488/809)
- don_go
- ベストアンサー率31% (336/1059)
qsortアルゴリズムの違いよりは、ソート対象のデータ型の違いか、データの文字コードの違い（UTF16LE（またはSJIS）、EUC）、CPUレベルでのバイト順（Big Endian, Little Endian）の違いの方が疑わしいと思います。 アルゴリズムの違いを疑うのであれば、アセンブラコードをデバッガを使ってトレースすればはっきりするでしょう。
補足
文字コードの違いやEndianの問題はデータの移行時に変換されています。 またソート対象キーは数値フィールドなので文字コードは関係ありませんし、 キー単位でのソートは出来ています。 キーが同じレコードの順番が新旧システムで違うので、qsortアルゴリズムの違いと断定 しました。 旧システムは、旧システムはお客様が業務で使用しているので、デバッガでトレース なんて荒業は行うことは出来ません。
- root139
- ベストアンサー率60% (488/809)
直接的な回答ではなく恐縮ですが・・・。 問題の本質は作業完了の条件が不適切だったいうことでは無いでしょうか。 比較関数が一致するデータ同士の順番は、仕様としては特に意味が無いわけですよね？ であるならば、依頼者側に作業完了の条件を修正してもらう様に交渉してはいかがでしょうか？ 契約の内容の見直しも考える事になるのかも知れませんが、解決できるかどうかも分らなく、かつ本質的に不要な作業に無駄な工数を掛けるよりも建設的かと。 例えば、下記の様なものも作業完了の条件として考えられるのではないでしょうか？ ・Solaris版で出力された全データがWindows版でも過不足無く出力されている事 ・(比較関数の)仕様に従ってソートされている事
補足
＞比較関数が一致するデータ同士の順番は、仕様としては特に意味が無いわけですよね？ どうも、データ作成時に特定のキーでソートし同一キー内で連番を付加し（この番号が、 新旧で順番が異なる）、その後別の複数のキーでソートし(此方はキーにてユニークに 成るので新旧で同じになる)データをメモリテーブルに登録されます。 その後別のプログラムで付加された番号単位でレコードをグループ化し、 （1番目のグループ、２番目のグループ、３番目の・・・）グループ単位で 処理を行っている様なのですが。 新システムと旧システムでグループ内に新旧で同じレコードがグループ化されていない のが問題と成っています。（グループ内が同じレコードでグルーピングされていれば順番、 グループ番号が一致しなくても問題ないのですが。）
- don_go
- ベストアンサー率31% (336/1059)
＞同じデータを読ませる限り同じ結果になる事は確認済みです。 同等なデータのソート前の順序は、ソート後も同じですか？ または、データ1件追加した時に順番がどうなりますか？
補足
＞同等なデータのソート前の順序は、ソート後も同じですか？ それは新システムも旧システムもソート前と変わっています。 但し新システムと旧システムでは順序が違うのが問題です。 ＞データ1件追加した時に順番がどうなりますか？ 旧システムはお客様が業務で使用しているのでデータの追加は出来ません。 新システムは元データに無理やりデータを追加して実施した所関係の無い所まで 順番が変わってしまいました。 データを削除したら元に戻りました。
- don_go
- ベストアンサー率31% (336/1059)
qsort(クイックソート)は、安定ソートではありません。 ※（あんていソート、stable sort）ソート（並び替え）の アルゴリズムのうち、同等なデータのソート前の順序が、 ソート後も保存されるもの。 従って、同等なデータがある場合のソート順は不定となります。 Solaris上で作られたソフトウェアで作成されたデータが毎回 同じ結果になるかは、確認してみましたか？
補足
同じデータを読ませる限り同じ結果になる事は確認済みです。 しかし、新システムと旧システムで結果が違っているので困っています。
補足
＞同等なデータのソート順序は不定になります。 ソート前の順番にならないだけで、ソートアルゴリズムに則った順番に並びます。 現在、お客様に問題の比較関数にキーを追加して旧システムの再構築を行ってもらい、 同じ修正を新システムに施し、出力結果が一致することによりポーティングＯＫと しようと言う話に成ってきています。 但し、水平展開として、同じような箇所が無いか調査し、同等な処置を施さなければ 成りません。 ソート対象と成るメモリテーブルは100以上有り、qsort関数の使用箇所は、数百有ります。 そのすべてを調査し、曖昧な比較関数が有れば、ユニークに成る様にキーを追加し、 ソート順を固定化する事による影響を調査し、お客様に、修正依頼をだして再構築して もらい、出力結果の一致確認を行なう。 気が狂いそうです。 旧システムのqsort関数のソースコードが有れば、又、軸要素の決定方法が解れば ユーザ関数としてsort関数を作成し、システム上のqsort関数の使用箇所を、一括置換で ユーザー関数に置き換えて再構築し、最終出力結果の一致確認だけで良いので 何とか成らないかと、探している状況です。