データ数が多い場合のソート

質問

４バイトのデータが2^26個あり、それに一対一対応した４バイトのデータが同様に2^26個あります。これを前者のデータを基準にソートしたいのですが、静的にデータを確保すると限界（トータルイメージサイズ）を超えてしまい、動的に確保してみても、取り方が悪い？のでうまくいきません。なにかいい方法はないでしょうか？お願いします。
以下は自分なりに作ってみたクイックソートの関数です。
void change(unsigned int i,unsigned int j, unsigned int youso[ ] ,unsigned int youso1[ ]){//配列要素i番目とj番目の値を入れ替える
int t,t1;
t=youso[i];
t1=youso1[i];
youso[i]=youso[j];
youso1[i]=youso1[j];
youso[j]=t;
youso1[j]=t1;
}

void sort(unsigned int left, unsigned int right, unsigned int youso[ ] ,unsigned int youso1[ ]){//lを一番左端の配列要素、rを一番右端の要素としてソートする。
unsigned int i,j,p;

i=left;j=right;
p=youso[(left+right)/2];//ピボットの決定

while(1) {
while(youso[i]<p){//左からピボット以上を探索
i++;
}
while(p<youso[j]){//右からピボット以下を探索
j--;
}
if(i>=j){//探索地点がぶつかったら終了
break;
}
change(i,j,youso,youso1);//お互い発見した値をいれかえる
i++;
j--;
}

if(left<i-1){//左範囲が分割可能なら
sort(left,i-1,youso,youso1);//左範囲を分割してソートを行う
}
if(j+1<right){//右範囲が分割可能なら
sort(j+1,right,youso,youso1);//右範囲を分割してソートを行う
}
}

回答No.3

Oh-Orange · ベストアンサー

★データ量が多すぎますね。
・私も回答者 No.1 さんと同じく最初は 2^24(16MB×8＝128MB) 程度のデータを
　４分割してクイックソートさせます。→128MB×4分割＝512MB
・その後に分割して(一時ファイルなどに保存)したデータをマージソートで
　合併処理させます。
・また、『sort』関数はクイックソートですが、C言語ならば標準で『qsort』が
　あります。→クイックソートのお勉強でしょうか？
・『change』関数は引数が４つありますが、『unsigned int』型のポインタを
　引数に渡せば２つですみますよ。→ポインタ分かりますか？
・つまり、『void change(unsigned int *youso,unsigned int *youso1);』です。
・『sort』関数も引数を２つ程度に出来ますよ。→データ配列、その個数など
・引数の数が多いと単純に『スタック』を多量に消費します。
・ちなみに、４バイトデータが 2^26 個あり、それに対応した４バイトのデータが
　関連付けてあるのならば、構造体を定義すれば１セットで管理できます。

●構造体(一例)
typedef struct {
　unsigned int number;
　unsigned int data;
} userdata_t;

●関数プロトタイプ宣言
void change( userdata_t *youso, userdata_t *youso1 );
void sort( userdata_t data[], unsigned int max );

まとめ:
・データを構造体で管理。
・引数をポインタで渡す。(配列＋添え字＝ポインタ位置)
・データの分割など。

最後に:
・データ以外にも 2^28 個の配列がありますが、すべてメモリ確保できていますか？
・私の環境ではメモリが 256MB しかないので、メモリを 2GB、16GB の環境は
　ちょっと想像できませんね。すごい。→ちゃんとそれだけのメモリ量が使えますか？
・すべてメモリ確保できているのならば、スタック・サイズなどを増やしてみましょう。
・初期設定では、スタック・サイズが 1MB のようです。
→http://oshiete1.goo.ne.jp/qa2645032.html→『C言語　配列の確保』回答者 No.7 さんより
・以上。おわり。

参考URL：

http://www.bohyoh.com/CandCPP/FAQ/FAQ00047.html

補足

回答ありがとうございます
皆様の意見をもとにデータを分割しマージソートで行うために
ソートするデータをファイルに分割して出力し、個別にクイックソートを行ってみたら、うまくソートされてません。
どうしてなのでしょうか
ソート部分の関数はOh-Orangeさんが紹介してくれた参考urlを
参考にしています。

以下ソースを記述します。
データ数は少なくしています。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
int atai;
int number;
} DATE;

int hpcmp(const DATE *x, const DATE *y)
{
return (x->atai < y->atai ? -1 :
x->atai < y->atai ? 1 : 0);
}

void print_date(DATE x)
{
printf("%dcm %dkg\n", x.atai, x.number);
}

int main(void)
{
unsigned int ken1;
unsigned int *mns;
DATE *you;

FILE *fp,*fp1;
fp = fopen("./sample2.txt","w");
fp1 = fopen("./sample1.txt","r");
you = (int*)malloc( sizeof(int) * (2*65593801) );
mns = (unsigned int*)malloc( sizeof(unsigned int) * (16400000) );

for(ken1=0;ken1<=16400000;ken1++){
mns[ken1] = 0;
fscanf(fp1,"%x",&mns[ken1]);

if(mns[ken1]==0)break;
if(ken1%2==0){
you[ken1/2].atai = mns[ken1];
}
else{
you[ken1/2].number = mns[ken1];
}
}

qsort(you, 20, sizeof(DATE), (int(*)(const void*, const void*))hpcmp);

for(ken1=0;ken1<=20;ken1++){
fprintf(fp,"%0x %0x\n",you[ken1].atai,you[ken1].number);
if(you[ken1].atai==0)break;
}

free(you);
free(mns);
fclose(fp1);
fclose(fp);
return 0;
}
sample1.txtのデータ
327644 24
324577 24
3298aa 48
3289bb 48
32fecc 48
3312312 48
3317647 48
3315465 48
33189b8 48
331fecf 48
331dced 48
2302313 48
2306757 48
2305464 48
2304575 48
230ba8a 48
23098a8 48
23089b9 48
230fece 48
5376750 48

回答No.4

sakusaker7

とりあえずスタックサイズの問題ならば、Visual Studio には editbin.exeという
ユーティリティがあり、これを使えば再コンパイルしないで実行ファイルのスタック領域の割り当てを
変更できますので試してみてください。

SQL Server スレッド スタック サイズを調整するために、 Editbin を使用する方法
http://support.microsoft.com/kb/160683/ja

なんかに実例があります。
デフォルトが1Mなので実装メモリを考えても数十Mバイト割り付けても大丈夫じゃないかと思います。
ただ本当に再帰のレベルが深すぎたのが原因として、どのくらい足りなかったのが
今までの情報ではわかりません。
素朴なクイックソートでは最悪の場合ほぼ要素数と同じレベルになります。
こんな状態では多少スタック領域を増やしたところで焼け石に水です。

対策ですが、
#3の方の提案のとおり構造体に二つのデータをまとめて、ソートは標準ライブラリ関数のqsortを使うとか
(実装がクイックソートとは限りませんが、クイックソートであっても普通はかなり手の込んだ
実装になっていて、最悪の場合にもスタックレベルがそれほど深くならないように
努力しています)、
外部ソートと組み合わせるというのもあるでしょうし、
どうしてもオンコアでという要求があるのなら、ヒープソートを使うというのはどうでしょう。
マージソートは再帰レベルでの最悪値の心配はありませんが、
要素を納める領域がクイックソートに比べて巨大なので(単純にはソート対象の2倍)、今度はこれが問題になる場合があります。

> CPU Xenon 3.73GHz
> メモリ　　　16GB
> コンパイラ　Visual stadio 2005

こっちは64bitOSだったりしますか?

補足

回答ありがとうございます。
とりあえず　データを分けてそれぞれをクイックソートし、それからマージソートをしてみようと思います。

> CPU Xenon 3.73GHz
> メモリ　　　16GB
> コンパイラ　Visual stadio 2005

こっちは64bitOSだったりしますか?
OSに関してはどちらもWindows XP professionalですが
Xenonマシンのほうは64bit editionです。

static で配列を取りすぎてるせいか？コンパイルした時に
警告で　
トータルイメージサイズが(898752512)が最大値(268435456)を超えています。
と表示されます。前者の数字は自分で確保しようとした配列のメモリ容量？だと思うのですが、グーグルで検索してもトータルイメージサイズ自体の記述もなく悩んでます。質問が増えてしまっていますがどうかお願いします。

回答No.2

sakusaker7

うまくいかないというのは具体的にはどういう動きですか?

・メモリ確保に失敗する
・一見正常終了するが結果が正しくない
・メモリ確保失敗以外の何らかの原因で異常終了してしまう

みたところ素朴なクイックソートなので、メモリが確保できたとしても
データの並び方によっては再帰のレベルが深くなりすぎてスタックを
食いつぶす可能性があります。

お礼

たびたびすみません　お礼を述べる欄ですが、補足への訂正に使わせていただきます。
上記のメインプログラムの最初のコメントの部分
/*他には2^28程度のstatic unsigned intで２次及び３次元配列を使ってます*/
となっていますが、2^28個程度の配列を使っています。

補足

sakusaker7さん回答ありがとうございます。

すみません　眠くて具体的なことを記述するのを忘れてました。
int main(void)
{
　unsigned int *youso;
　unsigned int *youso1;
/*他には2^28程度のstatic unsigned intで２次及び３次元配列を使ってます*/
youso = (unsigned int*)malloc( sizeof(unsigned int) *65593801 );
youso1 = (unsigned int*)malloc( sizeof(unsigned int) * 65593801 );
/*この間に配列youso　youso1にデータ格納しますが少し長いので省略します*/
sort(0, cou1-1, youso, youso1);
free(youso);
free(youso1);
return 0;
}

エラーはソート下から４行目のソート関数内の
while(p<youso[j]){//右からピボット以下を探索
のところでおこります
おそらくsakurasaker7さんのおっしゃられたスタックがオーバーフローしてると思っています。
質問としてはこれを回避するようなうまい考え方についてです。
わかりにくくてすいませんでした。

尚実験環境は
CPU pentium 4 3.4GHz
メモリ 　　　２GB
コンパイラ　Visual stadio C++ 6.0
もしくは
CPU Xenon 3.73GHz
メモリ　　　16GB
コンパイラ　Visual stadio 2005
です

回答No.1

rabbit_cat

大量データの場合はクイックソートではなくて、マージソートにしたほうがいいと思います。
で、分割していってデータ数がある程度より少なくなくなって扱いやすくなったらクイックソートに切り替えればよいです。

＃4×2×2^26=500Mバイトくらいであれば、動的配列なら確保できるような気もするのですが。

補足

rabbit_cat様　ありがとうございます

マージソートは名前は知っていましたがどんな動きをするかわからなかったのでこれからちょっと調べてみようと思います。

デバックをかけてみたところ配列の確保はできていました。
実験環境などは ANo.2の回答補足を参照してください。