• 締切済み

qsort のアルゴリズムについて

現在Solaris上で作られたソフトウェアをwindowsに乗せ換えるポーティング作業を 行っているのですが、qsortの結果が一致せずに困っています。 比較関数で判定できる範囲は一致するのですが、比較関数が一致するデータ同士の順番が 一致せず、その結果出力される生成物の内容が異なってしまいます。 （同じ生成物が作成されなければポーティング作業完了と成りません） 多分qsortのアルゴリズムの違いだと思うのですが、Solarisのqsortのアルゴリズムがわかる方 いらっしゃいませんか？ Solarisのコンパイラは以下の通り Sun WorkShop Compiler Csparc 5.0 出来ればqsortのソースコードが有ればよいのですが、軸要素の決定方法だけでも解れば 幸いです。 いくつか、公開されているアルゴリズムを試してみたのですが、一致する物は有りませんでした。 （Windowsのソート結果とも違いました） 因みに、Windowsの開発環境は、 Microsoft Visual Studio 10.0 です。

みんなの回答

  • t-okura
  • ベストアンサー率75% (253/335)
回答No.7

Open Solaris の qsort ソースは http://src.opensolaris.org/source/xref/sparks/sparks-hg/usr/src/lib/libbc/libc/gen/common/qsort.c ではないでしょうか。

  • root139
  • ベストアンサー率60% (488/809)
回答No.6

> 新システムと旧システムでグループ内に新旧で同じレコードが > グループ化されていないのが問題と成っています。 これがどういった意味で問題となっているのでしょうか？ 新・旧システムが連携する必要が有るのでしょうか？ それともポーティングの検証として突合せを行なうためでしょうか？ > お客様に問題の比較関数にキーを追加して旧システムの再構築を行って・・・ という案が出るくらいですから、既存のデータとの一貫性では無いと思いますが。 比較関数が一致するデータ同士の順番については、元のSolaris版でも「キー列の値もデータ数も順番も同じ入力に対しては同じソート結果になる」以上のことは前提としていないはずですので、Windows版で使用するソート関数に同様の前提が成り立つことが確認できれば大丈夫な気もするのですが・・・。 まあ、作業量的に可能ならば、お話の様に比較関数にキーを追加する方が良いとは思います。 ちなみにピボットをデータ列からランダムに選ぶやり方も有るので、「キー列の値もデータ数も順番も同じ入力に対しては同じソート結果になる」という前提の成り立たない QuickSort 実装も有りえます。

  • don_go
  • ベストアンサー率31% (336/1059)
回答No.5

安定ソートでないqsortを使う限り同等なデータのソート順序 は不定になります。 ＞データを追加して実施した所関係の無い所まで順番が変わって ＞しまいました。 ＞データを削除したら元に戻りました。 旧システムも今まで気づかれていなかっただけで、同様な結果に なると思われます。 これを固定化しようとするのであれば、旧システムと出力順が 変わってしまいますが、連番(読み込み順)や作成日時等の項目を ソートキーとして追加する等の手段をとる必要があります。 出力順が異なる件に関しては、No.3の回答にあるように条件交渉 してみてはどうでしょうか？ ＞例えば、下記の様なものも作業完了の条件として考えられるのではないでしょうか？ ＞・Solaris版で出力された全データがWindows版でも過不足無く出力されている事 ＞・(比較関数の)仕様に従ってソートされている事

sin_zi
質問者

補足

＞同等なデータのソート順序は不定になります。 ソート前の順番にならないだけで、ソートアルゴリズムに則った順番に並びます。 現在、お客様に問題の比較関数にキーを追加して旧システムの再構築を行ってもらい、 同じ修正を新システムに施し、出力結果が一致することによりポーティングＯＫと しようと言う話に成ってきています。 但し、水平展開として、同じような箇所が無いか調査し、同等な処置を施さなければ 成りません。 ソート対象と成るメモリテーブルは100以上有り、qsort関数の使用箇所は、数百有ります。 そのすべてを調査し、曖昧な比較関数が有れば、ユニークに成る様にキーを追加し、 ソート順を固定化する事による影響を調査し、お客様に、修正依頼をだして再構築して もらい、出力結果の一致確認を行なう。 気が狂いそうです。 旧システムのqsort関数のソースコードが有れば、又、軸要素の決定方法が解れば ユーザ関数としてsort関数を作成し、システム上のqsort関数の使用箇所を、一括置換で ユーザー関数に置き換えて再構築し、最終出力結果の一致確認だけで良いので 何とか成らないかと、探している状況です。

noname#217196
noname#217196
回答No.4

qsortアルゴリズムの違いよりは、ソート対象のデータ型の違いか、データの文字コードの違い（UTF16LE（またはSJIS）、EUC）、CPUレベルでのバイト順（Big Endian, Little Endian）の違いの方が疑わしいと思います。 アルゴリズムの違いを疑うのであれば、アセンブラコードをデバッガを使ってトレースすればはっきりするでしょう。

sin_zi
質問者

補足

文字コードの違いやEndianの問題はデータの移行時に変換されています。 またソート対象キーは数値フィールドなので文字コードは関係ありませんし、 キー単位でのソートは出来ています。 キーが同じレコードの順番が新旧システムで違うので、qsortアルゴリズムの違いと断定 しました。 旧システムは、旧システムはお客様が業務で使用しているので、デバッガでトレース なんて荒業は行うことは出来ません。

  • root139
  • ベストアンサー率60% (488/809)
回答No.3

直接的な回答ではなく恐縮ですが・・・。 問題の本質は作業完了の条件が不適切だったいうことでは無いでしょうか。 比較関数が一致するデータ同士の順番は、仕様としては特に意味が無いわけですよね？ であるならば、依頼者側に作業完了の条件を修正してもらう様に交渉してはいかがでしょうか？ 契約の内容の見直しも考える事になるのかも知れませんが、解決できるかどうかも分らなく、かつ本質的に不要な作業に無駄な工数を掛けるよりも建設的かと。 例えば、下記の様なものも作業完了の条件として考えられるのではないでしょうか？ ・Solaris版で出力された全データがWindows版でも過不足無く出力されている事 ・(比較関数の)仕様に従ってソートされている事

sin_zi
質問者

補足

＞比較関数が一致するデータ同士の順番は、仕様としては特に意味が無いわけですよね？ どうも、データ作成時に特定のキーでソートし同一キー内で連番を付加し（この番号が、 新旧で順番が異なる）、その後別の複数のキーでソートし(此方はキーにてユニークに 成るので新旧で同じになる)データをメモリテーブルに登録されます。 その後別のプログラムで付加された番号単位でレコードをグループ化し、 （1番目のグループ、２番目のグループ、３番目の・・・）グループ単位で 処理を行っている様なのですが。 新システムと旧システムでグループ内に新旧で同じレコードがグループ化されていない のが問題と成っています。（グループ内が同じレコードでグルーピングされていれば順番、 グループ番号が一致しなくても問題ないのですが。）

  • don_go
  • ベストアンサー率31% (336/1059)
回答No.2

＞同じデータを読ませる限り同じ結果になる事は確認済みです。 同等なデータのソート前の順序は、ソート後も同じですか？ または、データ1件追加した時に順番がどうなりますか？

sin_zi
質問者

補足

＞同等なデータのソート前の順序は、ソート後も同じですか？ それは新システムも旧システムもソート前と変わっています。 但し新システムと旧システムでは順序が違うのが問題です。 ＞データ1件追加した時に順番がどうなりますか？ 旧システムはお客様が業務で使用しているのでデータの追加は出来ません。 新システムは元データに無理やりデータを追加して実施した所関係の無い所まで 順番が変わってしまいました。 データを削除したら元に戻りました。

  • don_go
  • ベストアンサー率31% (336/1059)
回答No.1

qsort(クイックソート)は、安定ソートではありません。 ※（あんていソート、stable sort）ソート（並び替え）の 　アルゴリズムのうち、同等なデータのソート前の順序が、 　ソート後も保存されるもの。 従って、同等なデータがある場合のソート順は不定となります。 Solaris上で作られたソフトウェアで作成されたデータが毎回 同じ結果になるかは、確認してみましたか？

sin_zi
質問者

補足

同じデータを読ませる限り同じ結果になる事は確認済みです。 しかし、新システムと旧システムで結果が違っているので困っています。

  1. カテゴリ
  2. ビジネス・キャリア
  3. 職種
  4. SE・インフラ・Webエンジニア

関連するQ&A

  • SunのWorkshop5.0でコンパイルしたソースはWorkshop6.0でコンパイルしたマシンで動作しますか。

    SunのWorkshop5.0でコンパイルしたソースはWorkshop6.0でコンパイルしたマシンで動作しますか。 どなたかSunのWorkshop5.0 とWorkshop6.0のコンパイラの差異を教えてください。 Web上で調べてみた結果あまり大差がないように思えたのですが。。 Workshop6.0で作成したシステムがあるのですが、Workshop6.0のライセンスを紛失してしまいました。Workshop5.0はライセンス・メディア共にあるので、新しく作ったソースはWorkshop5.0でコンパイルしようと考えているのですが、うまく動作するかわかりません。もし、Workshop5.0でコンパイルしたソースがWorkshop6.0で動作しない場合、最悪、Workshop5.0でシステム全体をmake allしなくてはならないのかと考えていますが、かなりの作業ボリュームになるためできるだけ避けたいと思っています。 月曜日までに方針を決めなければならないので、どなたかご存知の方ご教示いただけませんか。 よろしくお願いします。

  • アルゴリズムプログラミング

    アルゴリズムにおいて以下のような課題が出たのですかその実行結果を出すためのソースプログラム、または実行結果をどなたか教えてください！ （１）バブルソート、選択ソート、挿入ソートプログラムに対して、実行時間（小数点以下２桁まで）、比較回数、代入回数をデータ数50000、100000、150000、200000の4つの場合でそれぞれ測定せよ。ただし対象データはランダム関数SFMTを利用して作成するものとする。 （２） ヒープソート、クイックソートとマージソートプログラムの実行時間（小数点以下２桁まで）、比較回数、代入回数をデータ数50000、100000、150000、200000の4つの場合でそれぞれ測定せよ。ただし対象データはランダム関数SFMTを利用して作成するものとする。 ＳＦＭＴは以下のサイトからＳＦＭＴ－ｓｒｃー1.3.3.zipをダウンロードして解凍する。 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index-jp.html#SFMT そのうち必要なファイルは sfmt.h sfmt.c sfmt-params.h sfmt-params19937.h を使用する。 どうぞよろしくお願いします。

  • アルゴリズムのご相談

    はじめまして DHCPのような動作をするアルゴリズムを考えている最中なのですが… その案の中でどうしてもクリア出来ない課題があります。 「配列で作られたテーブルにユーザ名の一覧があり、 そのユーザ名をキーワードとして配列のインデックスを抽出したい」 というもので、これだけなら簡単なのですが、以下３つの条件の提示により、無理ではないかと思えて仕方がないです。 ・ユーザ名は何らかのルールに則って作られた文字列ではない。 ・キーワードを頭から順に比較して探していく方法を使ってはいけない。 ・ユーザの追加・削除がある度にソートし直さなければならないような構造にしてはいけない。 ２分探索法などの検索回数を減らす方法はソートされてることが前提条件ですし、 ユーザ名から配列のインデックスに使える数値に変換できるような都合のいい関数なんて存在しないように思えるのですが、いかがでしょう？ ちなみに開発言語はCです。

  • コンパイラの互換性について

    コンパイラの互換性について教えてください。違うコンパイラで作成したShared Objectを使用するプログラムの動作が不安定になるといったことは考えられますか？考えられるとすれば、どのような理由でそういった事象が発生するのでしょうか？ WindowsではMSのコンパイラとBorlandのコンパイラについて。 SolarisではSUNのコンパイラとGNUのコンパイラについて。 Linuxでは異なるバージョンのGNUコンパイラについて。 現状を教えてください。 ここらへんを解説している書籍やURLの紹介も嬉しいです。

  • qsortと動的確保の２次元配列

    C言語で以下のようなソートのあるプログラムを作ろうとしているのですが、良い方法が思いつきません。。。。 どなたか,知恵を貸していただけないでしょうか？ ・複数人の身長と体重がcsvファイルに2列に入っている。 人 身長 体重 1 158.9 50.5 2 161.2 72.3 3 150.4 42.8 4 170.7 80.4 5 165.0 59.9 ・ ・ ・ ・ ・ ・ ・↑このように身長も体重もランダムに並んでいる状態 ・身長・体重をプログラムで読み込んだら 身長の低い順にソートする。この時体重も身長に対応して並び換わってほしい。 (わかりやすいかと思い人の番号列を設けましたが、人の番号は考えなくて良いです) この問題に対して,データ数が不特定かつ多いため 動的確保の2次元配列を使ったクイックソートで対応を考えます。 qsortについてあれこれ調べていたのですが,動的確保でのqsort例が無く困っています。。。 どなたかちょっとアドバイスをいただけないでしょうか？ よろしくお願いします。 #include <stdio.h> #include <stdlib.h> enum {HIGHT, WEIGHT, COLUMN}; int comp (const void *a, const void *b) //比較関数 { return (int) (((double *)a)[HIGHT] - ((double *)b)[HIGHT]) ; } int main(void) { ////////////////////////////////////////////////////////// 私情により、ソート以前の処理で使用するため あらかじめ .csv ファイルから fget で値を読み込んで　コンマで分割しx[]y[]に格納してある。 ＆データ数をカウントしている 今は省略　 仮定として以下のように５つのデータ数を読み込んでいたとする double x[5] = {158.9,161.2,150.4,170.7,165.0}; double y[5] = {50.5,72.30,42.8,80.4,59.9}; int n=5; //データカウント数 /////////////////////////////////////////////////////////// int i; double **list; list = (double**)malloc(sizeof(double)*5); for (i=0 ; i< 5 ; i++) { list[i] = (double*)malloc(sizeof(double)*COLUMN); if (list[i]==NULL) return 1;/* 領域確保に失敗したか */ } for(i=0;i<n;i++) { list[i][HIGHT]=x[i]; list[i][WEIGHT]=y[i]; } for(i = 0; i < n; i ++) printf("%lf %lf\n", list[i][HIGHT], list[i][WEIGHT]); puts("Sort"); qsort(list,n, sizeof(double [COLUMN]), comp); for(i = 0; i <n; i ++) printf("%lf %lf\n", list[i][HIGHT], list[i][WEIGHT]); scanf("%d",i); return 0; }

  • XPではタイトルバーが無いウィンドウは作成できないのですか？

    以前、98でアプリを作成していたときは CreateWindow関数でWS_POPUP指定でタイトルバーが 無いウィンドウを作れていたのですが、XPで同様に WS_POPUP指定するとウィドウが生成されません。 参考書のサンプルプログラムの通りに記述しても 駄目でした。 これは仕様でしょうか？ どうすればタイトルバーが無いウィンドウが作成できるのでしょうか？ コンパイラはBorland C++ Compilerを使っています。 なお、ウィンドウは実行されなくても、プロセスは 動き続けている事がタスクマネージャから確認できました。

  • STLのsortで、プライベート変数を比較関数に組み入れたい。

    STLのsortで、プライベート変数を比較関数に組み入れたい。 STLのvectorのsortで比較関数を指定してソートをしようとしております。 ソートしようとするvectorは、とあるクラスのプライベート変数であり、 同じクラスの他のプライベート変数を利用した比較を行おうとしています。 例えば int array[4] = {1, 7, 3, 5}; なるプライベート変数があり、比較関数はこんなアルゴリズムとしたいと。 bool compare(int left, int right) { return array[ left ] < array[ right ]; } この compare をクラスのメソッドとして定義して使えるのかなと思っていたのですが コンパイルしたところエラーが出ました。パブリック変数にして、プレディケートの ためのクラスを作って、そこでパブリックメソッドを作って……という方法は見つかった のですが、そのような面倒な方法を経なければいけないのでしょうか。

  • 比較回数が少なくなるソート

    大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい） 画像はすでにデジタルデータ化されてパソコンの中にあります。 二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。 また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。 以上、ご指導のほど、よろしくお願い申し上げます。

  • 構造体配列の安定なソート

    出席番号と得点の配列を持つ構造体配列で、 出席番号順に並んだ状態でqsortを使って得点をソートする場合、 同じ得点の人でも、出席番号順はばらばらになってしまいますよね。 調べてみて、バブルソートなど安定なソートを使えばいいということが分かったのですが、 qsortは標準ライブラリにあって、 比較関数も見よう見まねで作ってなんとかなったのですが、 他の方法となると具体的にどうすればいいのか、 よくわからない状況です。 http://homepage1.nifty.com/daccho/program/algo/sort3.htm こちらのサイトのソースファイルを見て、 普通のint配列のバブルソートは出来たのですが、 構造体配列を、構造体の中の一つの要素をキーにバブルソートできるようにするには、 ここからどのように変更すればいいのでしょうか？ 並び替える内容はint型だけなので、文字列をソートできるようにする必要はなく、 ソート対象も少ないので（上限100程度）、速度的な問題は考慮しなくて大丈夫だと思います。 Cは勉強中で、基本文法がわかるぐらいという状況で、 もしかしたら変なことを言っているのかもしれませんが、 よろしくお願いします。

  • 遺伝的アルゴリズム

    遺伝的アルゴリズムをCで組み、Cygwinのgccコマンドでコンパイルしたのですが、実行するとエラーが出てしまいます。 gsb内で実行しwhereコマンドで異常箇所を探した場合のメッセージは以下の通りです。 #0 0x61016525 in stack_info::walk () from /usr/bin/cygwin1.dll #1 0x7c859dcc in OutputDebugStringsA () from /cygdrive/c/WINDOWS/system32/kernel32.dll #2 0x40010006 in ?? () #3 0x00000000 in ?? () プログラムは長いので載せられませんが、アルゴリズム中の染色体は二次元配列の遺伝子を含む構造体です。 遺伝子の配列に関わるノード数（chromo[timeslot][NODE]←このNODEです。プログラム冒頭で値をdefineで宣言しています）が30位なら世代数が比較的多くても動くのですが、これが50あたりになると世代数が低くてもエラーが出てしまいます。 printf関数で交叉や突然変異の結果を表示しているのですがちゃんと動作しているようです。 二台のパソコンどちらでやってもこのようなメッセージが出るので困っています。何が起こっているか見当がつく方、いらっしゃいましたら助言願います。 よろしくお願いいたします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する