Perlのソート関数の内部構造とは？
- Perlのソート関数の内部構造について、質問者が理解できていない点があります。
- Perlの解説本やホームページを参考にしたが、ほとんどのユーザーがソート関数の使い方を丸覚えにしており、詳しい解説がない。
- ソート関数の$aと$bには、配列の値が比較される際に呼び出されるが、具体的にはどのようなタイミングでそれらが入ってくるのか疑問がある。
- ベストアンサー
Perl のソート関数
Perl を使い始めて数年になり、雑誌の隅っこに載る程度のフリーソフトなら作るようにもなりましたが、未だにソート関数の内部構造がさっぱり分かりません(^_^; Perl の解説本も数冊、ホームページに至っては十数ほども有名と言われているところを回ってみましたが、ほとんどの Perl ユーザーがソート関数の使い方を丸覚えにしているようで、的を得ない解説しか載ってません。 そこで質問ですが、$a と $b には、いったい「何が」「どういうタイミングで」入ってきているのでしょうか？（配列の値が比較されるときに呼び出される、ということは分かりますが） 当たり前に考えれば、ソート関数というものは全てをユーザーに任せて関数を書かせるか、でなければフルオートで全てやってくれるソート関数を用意するか、どちらか１方しかないはずです。 なのに、Perl のソート関数は途中部分だけユーザーに書かせるという器用なことをやってます。 これはいったいどういう構造になっているのでしょう？
- Perl
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
> 当たり前に考えれば、ソート関数というものは全てをユーザーに任せて関数を書かせるか、でなければフルオートで全てやってく > れるソート関数を用意するか、どちらか１方しかないはずです。 そのふたつ以外に、もうひとつ当たり前があります。 ソートは、要素の大小比較をして、逆転していれば要素を入れ替える、という ことをやるわけですが、「要素の大小比較」というのは、ときと場合によって いろいろ変わります。 というわけで、その変わるところ、つまり「やり方」をソート関数に渡すという 方法があります。 これは perl に限ったことでは無いのですが、（もう、古い言い方なんですが） コールバック処理と言います。 ある処理（この場合は大小比較）を呼び出す側で用意して、何らかの処理（ソート） から呼び出す、つまり、呼び戻すように見えることから、この名前がついています。 処理自体を指定する手段がある言語の標準的なソートは、大体こういう形式 になってます。私が知っているところだと C/C++、ruby なんかがそうです。
関連するQ&A
- 複数キーによるソート
ここに、3つperlの配列があって、それぞれ問題番号、英単語、日本語訳が入っています。 これらを、例えば「英単語順」「問題番号順」などに並べ替えて先頭から順に取り出したいのですが、sort関数は配列ひとつに対してしか操作できないので、悩んでいます。 たとえば問題番号←→英単語の配列間に単語ごとのリンクを張って、片方をソートしてもリンクをたどるともう片方が取り出せるといったことはできるのでしょうか？ また、配列のソートのルールを使って別の配列をソートする・・・といったことでも構いません。よろしくお願い致します。
- ベストアンサー
- Perl
- [C言語]ソート関数の作成
現在受け取った構造体を受け取ってソートしてポインタで書き換える関数を作成しています。 構造体の配列 typedef struct{ char name[50]; int age; }member; member seito[10] strcpy(seito[0].name,"yamada") seito[0].age = 15; strcpy(seito[2].name,"ito") seito[2].age = 17; strcpy(seito[3].name,"saito") seito[3].age = 19; こちらの構造体は例です。 seito[2]の情報を[1]に seito[3]の情報を[2]に移動させたいのですが、上手くいきません。 構造体配列を、1引いてあげれば良いと思ったのですが、そうすると[0]までマイナスしてしまい上手く判定が出来ません。 どうかアドバイスお願いいたします。
- 締切済み
- C・C++・C#
- 構造体配列の安定なソート
出席番号と得点の配列を持つ構造体配列で、 出席番号順に並んだ状態でqsortを使って得点をソートする場合、 同じ得点の人でも、出席番号順はばらばらになってしまいますよね。 調べてみて、バブルソートなど安定なソートを使えばいいということが分かったのですが、 qsortは標準ライブラリにあって、 比較関数も見よう見まねで作ってなんとかなったのですが、 他の方法となると具体的にどうすればいいのか、 よくわからない状況です。 http://homepage1.nifty.com/daccho/program/algo/sort3.htm こちらのサイトのソースファイルを見て、 普通のint配列のバブルソートは出来たのですが、 構造体配列を、構造体の中の一つの要素をキーにバブルソートできるようにするには、 ここからどのように変更すればいいのでしょうか？ 並び替える内容はint型だけなので、文字列をソートできるようにする必要はなく、 ソート対象も少ないので（上限100程度）、速度的な問題は考慮しなくて大丈夫だと思います。 Cは勉強中で、基本文法がわかるぐらいという状況で、 もしかしたら変なことを言っているのかもしれませんが、 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 【C言語】ファイルでのソート方法について
ファイルの大量データ（構造体をバイナリで書き込んだ）をソートする時（構造体のメンバの1つをキーとして）に用いるソート法で高速にできるソート法はなんでしょうか？ 選択法でやっているのですが遅いもので・・・・ 配列ではなくてファイルに対して高速なソート法をご教示いただきたく。 ファイル全てを読んでからソートしないと厳しいでしょうか？ まだまだｃ言語初心者ですが、なにかアドバイスをよろしくお願い致します。
- ベストアンサー
- C・C++・C#
- クイックソートについて
下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }
- 締切済み
- C・C++・C#
- STLでfind_ifみたいなsortをしたいのですが。
こんにちは。 STLのdequeのソートで少し複雑な条件でソートしようとしています。 簡単なものでしたら、 sort( m_lists.begin(), m_lists.end(), fnComapreLower ) ; // bool fnComapreLower( lpElem0, sElem1 ) としてソートができますが、fnComapreLowerの比較関数にユーザーパラメータを 与えることはできないのでしょうか ? find_ifなら、 find_if( m_lists.begin(), m_lists.end(), _FINDER_ID( nnn )) ; として構造体を利用できるので便利なのですが、sortにも同様のことはできないのものでしょうか ? find_ifみたいに比較関数の他にユーザーパラメータを与えて処理したいのですが方法が分かりません。 もしご存じの方がいらっしゃいましたら教えていただけないでしょうか。
- ベストアンサー
- C・C++・C#
- perlでxmlを処理
現在perlを勉強しています。 xmlで書かれたものを構造体にして処理したいと考えています。 構造体の中の個数などを数えたいです。 構造体はパソコンのお気に入りです。 １、すべてのお気に入りの数 ２、すべてのフォルダの数 ３、１つのお気に入りフォルダの中にさらに何個のフォルダがあるか などをしたいと思っています。 どのような方法で求めることできるでしょうか？ よろしくお願いします。
- 締切済み
- Perl
- perlはc++のようなクラスや構造体は作れない?
c++で class hoge{ hoge(); int menber; }; というようなクラス定義と hoge x; というようなクラス変数定義のようなのは、Perlではできないのでしょうか。 メンバ関数はべつにいいのですが、その構造を配列にして管理したいのです。 たとえば、個人情報のような。 Perlではスタティックなメンバしか持てないと聞いたのですが、本当ですか?
- ベストアンサー
- Perl
- 構造体のリストをソートしたい。
ある名簿のリストを作りました。 以下のような構造体で、 typedef struct meibo{ char name[10]; int old; struct meibo *next; }MEIBO; これを、ポインタp->next->nameをたどっていって、名前が辞書順になるようにリストを作ったのですが、 これを年齢順にソートして表示させたいんです。 どんな方法があるんでしょうか？ 一旦すべてを配列に格納して、クイックソート…とかも考えたのですが、すごく領域をとるし、なんか２度手間（最初から配列に順に格納していけばよかったなぁ・・・と。 それでもやっぱり最初から名列順にするときから配列に入れておくほうがいいのでしょうか？ 教えてください。 （最初から年齢を比較してリストを作れば・・ってのはなしで、名列順のリストが存在するものとしてください。）
- ベストアンサー
- C・C++・C#
- クイックソートがうまくいかない
クイックソートとはこういう仕様のソートのことです。 (1)バラバラの配列から基準値を設定する。 (2)前から順番に辿って行って基準値よりも大きいならば、基準値よりも後に移動、小さいならば、基準値よりも前に移動させる。（私のプログラムの場合は基準値を配列の一番目の数に設定しています。） (3)小さいほうと大きいほうの二つのグループに分かれたらまたそれらのグループごとにクイックソートにかける。 (4)二つのグループを分けることができなくなればソート完了。 自分で確かめてみたのですが、どうやら関数QuickSortの中でさらに再帰的にQuickSortにかけるときにバグが発生しているようです。ですが、なぜバグが起きるのかわかりません。 お手数ですが、よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> #include<time.h> #include<string.h> #define N 10 void QuickSort(char mi,char *hai,int youso) { char *shoubox; char *bigbox; int k=0; int q=0; int i,len,len2; /*もし配列haiの大きさが1ならば終了*/ if(strlen(hai)==1) { return; } /*配列の２番目から最後まで基準値からの大小により仕分けしていく。大きいならば、配列bigboxに小さい*/ /*ならば配列shouboxにそれぞれ入れる。*/ for(i=1;i<youso-1;i++) { if(hai[i]>mi) { bigbox[k++]=hai[i]; } else { shoubox[q++]=hai[i]; } } /*仕分け処理はここまで*/ /*小さいほうの配列と大きいほうの配列をそれぞれクイックソートにかける再帰処理。*/ QuickSort(shoubox[0],shoubox,q); QuickSort(bigbox[0],bigbox,k); /*それぞれのソートが完了したら、配列haiに「小さいほうの配列」→「基準値」→「大きいほうの配列」 の順に値を代入していく。*/ len=strlen(shoubox); for(i=0;i<len;i++) { hai[i]=shoubox[i]; } hai[len]=mi; len2=strlen(bigbox); for(i=(len+1);i<len+len2;i++) { hai[i]=bigbox[i]; } /*代入処理ここまで。*/ } int main(void) { char array[N]; char m; int i,val,j; srand(time(NULL)); /*(1～10)までの数字をランダムに入力する処理*/ for(i=0;i<N;i++) { do{ val=rand()%10; for(j=0;j<i;j++) { if(val+'0'==array[j]) { break; } } }while(j<i); array[i]=val+'0'; } /*ランダムに値を入力する処理ここまで*/ m=array[0]; /*値配列の最初を基準値mに設定*/ QuickSort(m,array,N); /*基準値、配列、要素数を実引数として、クイックソートを呼び出す。*/ /*昇順に並べ替えた配列arrayを出力する。*/ for(i=0;i<N;i++) { printf("array[%d]=%c\n",i,array[i]); } return 0; }
- 締切済み
- C・C++・C#
お礼
ありがとうございます。 もしかして、比較結果で入れ替えるかどうか判断してるだけなんでしょうか(笑) だとしたら俺は何を悩んでいたのだろう(^_^;