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

質問

４バイトのデータが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.14

sakusaker7

マージソートを使えというのには反対しませんが

> あと、マージソートを用いても、データ量が極端に多い場合には、再帰処理で
> コーディングしてしまうとスタックの制限に引っかかってくる可能性もでてきますので、
> ループ処理で実装するなどの工夫が必要となってきますので注意してください。

クイックソートの最悪の場合と違って、再帰によるマージソートの場合の
再帰のレベルは log2 N になるのでそれほど心配することはないと思いますが?

回答No.13

guccii

十分に回答されているようなので、蛇足かもしれませんが...

個人的には、マージソートがお勧めです。
理由は、
・処理量がクイックソート同様であること
・適用できるデータ構造が広いこと（リンクリストにも適用できたり、メモリ内に全データを保持してなくてもよかったり）
・上記の条件を持ちつつ、アルゴリズムがシンプルであること！！

ですから私の場合、最速の整列アルゴリズムはクイックソート、最強（あるいは工学的に最速の）整列アルゴリズムはマージソートといったいいかたをよくしています。何か特別な理由がない場合には、まずマージソートを選択します。

あと、マージソートを用いても、データ量が極端に多い場合には、再帰処理でコーディングしてしまうとスタックの制限に引っかかってくる可能性もでてきますので、ループ処理で実装するなどの工夫が必要となってきますので注意してください。

お礼

返信が遅れてしまって申し訳ありません
Oh-Orageさん、sakusaker7さん、rabbit_catをはじめとしてたくさんの方、私の質問に対し真摯にお答えてしただいてありがとうございました。

結果から申しあげると、あらかじめデータファイルを４分割し、マージソートで合併処理することで解決することができました。
　ファイル（テキストデータ）を読み込む、もしくは書き込む際、ファイルポインタを配列に格納おき、読み込み→処理→書き込みを４回繰り返し、最後にデータをマージソートするまで一つのソースとしています。

mallocなどでのsizeof(int)→sizeof(DATE)はANo.3のお礼のところに書かせていたプログラムを記述した後にすぐ気づいたのですが、intcmp関数の不等号の向きはご指摘されるまで気づきませんでした。

私の知識不足でせっかく回答していただいたのにANo4やANo7の
内容は殆どよくわかりませんでした。
時間があるときに勉強してちゃんと理解できるようにしたいと思っています。

本当にありがとうございました。
ポイントに関してですが、今回の方法を提案したのはrabbit_cat様が最初でしたが、Oh-Orageさんとsakusaker7さんの説明がわかりやすかったのでお二人に付与しようと思います。

それでは失礼します。

回答No.12

Oh-Orange

◆最初に『sakusaker7』さんありがとうございます。→テキストデータなのですね。

★実装例(メモリ上ですべてをソートする場合)
・まずデータが、身長(cm)＋体重(kg)で１セットになった構造で、
　unsigned int 型×２つで格納されたファイルと仮定します。
・また全データ数は、1,234,567 件とします。
・このときのメモリ上ですべてをソートする実装例を紹介します。

#include <stdio.h>
#include <stdlib.h>

#define MAX_DATA　1234567　←最大データ数

typedef struct {
　int atai;　←身長(cm)
　int number;　←体重(kg)
} DATA, *LPDATA;　←こんな宣言も出来ます。

int QsortComp( const LPDATA x, const LPDATA y )
{
　return( (x->atai < y->atai) ? -1 :
　　　　　　(x->atai > y->atai) ? +1 : 0 );
}

void main( void )
{
　DATA *data;　←『LPDATA data』でも良い。
　DATA *seek;　←『LPDATA seek』でも良い。
　FILE *fp;　←入力ファイル
　FILE *fo;　←出力ファイル
　unsigned int max;

　if ( (fp = fopen("./sample1.txt","r")) != NULL ){
　　if ( (fo = fopen("./sample2.txt","w")) != NULL ){
　　　if ( (data = (LPDATA)calloc(sizeof(DATA) * MAX_DATA)) == NULL ){
　　　　printf( "メモリが足りません。" );
　　　}
　　　else{
　　　　for ( seek = data, max = 0 ; max < MAX_DATA ; max++, seek++ ){
　　　　　if ( fscanf(fp,"%x %x\n",&seek->atai,&seek->number) != 2 ){
　　　　　　break;
　　　　　}
　　　　}
　　　　qsort( data, max, sizeof(DATA), QsortComp );

　　　　for ( seek = data ; max != 0 ; seek++, max-- ){
　　　　　fprintf( fp, "%x %x\n", seek->atai, seek->number );
　　　　}
　　　　free( data );
　　　}
　　　fclose( fo );
　　}
　　fclose( fp );
　}
}

最後に:
・上記のサンプルを参考にして下さい。
・すべてメモリ上でクイックソートする実行例です。
・ファイルを分割したり、マージソートは行っていません。
・以上。おわり。→参考結果の報告をお願いします。

回答No.11

sakusaker7

> ★『for』文中は、もっと簡単に出来ます。
> ・『fread( you, sizeof(DATA), 8200000, fp1 );』　←for ブロックをこの１行で良い。
> ・構造体メンバ『atai』に『cm』データを読み込みます。
> ・ 構造体メンバ『number』に『kg』データを読み込みます。

あのーバイナリじゃなくてテキストでファイルに入ってるんだから
fread で読んでもダメなんじゃないでしょうか?

元を活かして簡単に書くなら
for (ken1=0; ken1<(16400000/2); ken1++)
if (fscanf(fp1, "%x %x", &you[ken1].atai, &you[ken1].number) != 2)
break;

こんな感じかと。
計算するの面倒くさいので / 2ですませてます。

回答No.10

Oh-Orange

★たくさんおかしいところ発見！
・違う『you = (int*)malloc( sizeof(int) * (2*65593801) );』
・正解『you = (DATA*)calloc( sizeof(DATA) * 65593801 );』　←65,593,801 がデータ数ですよね。
※『malloc』の代わりに『calloc』を使うとデータが全部 0 で初期化されます。→便利です。

・違う『for( ken1 = 0 ; ken1 <= 16400000 ; ken1++ ){』
・正解『for( ken1 = 0 ; ken1 < 16400000 ; ken1++ ){』　←『<=』だと１つ多い。

・違う『for( ken1 = 0 ; ken1 <= 20 ; ken1++ ){』
・正解『for( ken1 = 0 ; ken1 < 20 ; ken1++ ){』　←『<=』だと１つ多い。

・違う『qsort( you, 20, sizeof(DATE), (int(*)(const void*,const void*))hpcmp );』
・正解『qsort( you, 65593801, sizeof(DATA), hpcmp );』　←キャストは必要ないよ。

★比較関数『hpcmp』が間違っています。
int hpcmp( const DATE *x, const DATE *y )
{
　return( (x->atai < y->atai) ? -1 :
　　　　　　(x->atai > y->atai) ? +1 : 0 );　←不等号『>』が正しい。
}

★『print_date』もポインタを引数にして見ましょう。　←間違っていないけど。ポインタ版を紹介。
void print_date( DATE *x )
{
　printf( "%dcm %dkg\n", x->atai, x->number );
}

★『for』文中は、もっと簡単に出来ます。
・『fread( you, sizeof(DATA), 8200000, fp1 );』　←for ブロックをこの１行で良い。
・構造体メンバ『atai』に『cm』データを読み込みます。
・構造体メンバ『number』に『kg』データを読み込みます。
・『cm』と『kg』の１レコードは、8,200,000 件、読み込みます。→あっていますよね。数。

最後に:
・クイックソートが正常でなかったのは、比較関数『hpcmp』が間違っているためです。
・『mns』の配列は何に使うのですか？→参照(使う)されていませんが…。
・どうやら、身長(cm)＋体重(kg)の１レコード(データ)をソートしたいようですね。
・もっと詳しいデータ内容と、ソート結果などの質問者さんは何を行いかを説明して下さい。
・データファイルは、身長(cm)＋体重(kg)を unsigned int 型で 8,200,000 件、全部であるのですか？
・データファイルに関する詳しい内容と、ソート後の出力ファイルのデータ内容を教えて下さい。
・以上。補足要求します。

参考URL：

http://www.bohyoh.com/CandCPP/C/Library/fread.html

回答No.9

sakusaker7

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

最大値として示されている 268435456 ですが、2^28 でほぼ256Mバイトになります。
VC++のコンパイル時のデフォルト値で、ヒープサイズというものがこの256Mという大きさを
持っています。
ひょっとしたらリンク時のオプションでヒープサイズを大きく指定してやれば
実行ファイルの生成ができるかもしれません。
#指定の仕方はわかりますか?

log2 898752512 が 29.7433.. ということなので256MBの4倍くらい必要?
って1GBになりますけど、本当に大丈夫なんでしょうか。

回答No.8

sakusaker7

試してませんが
int hpcmp(const DATE *x, const DATE *y)
{
return (x->atai < y->atai ? -1 :
x->atai < y->atai ? 1 : 0);
}
x->atai と y->atai の比較をしているところ、どっちかの不等号が
逆じゃないですか?

回答No.7

Oh-Orange

★追記。
・メモリ上で上手くソートが出来ない場合は、ファイルへのマッピングを
　行ってソートするのはどうでしょう。
・データが多い場合は『メモリ・マップド・ファイル』という方法があります。

関連関数:
・CreateFileMapping
・MapViewOfFile
・UnmapViewOfFile

最後に:
・上記の方法ならば、大量のデータをポインタを使ってメモリ上と同じ様に
　いろいろと処理できます。
・下の『参考URL』をどうぞ。
・以上。おわり。

参考URL：

http://homepage2.nifty.com/DSS/WinSys/Win/FileMapping.htm

回答No.6

sakusaker7

言い争いはしたくないんですが、ソートアルゴリズムの選択やどのような対策を採るべきかは
前提条件によって変わりますので一つに決め打ちはできないと思います。
多少遅くなってもいいからできるだけ大きなデータで動くようになっているほうがいいとか。

キャッシュミスによるお話ならわかりますが、ページング云々は
環境として例示されている実装メモリ量を考えるとちょっと心配しすぎのような気もします。
確かにほかにプロセスが走っていると独り占めはできませんが。

アルゴリズム的にはヒープソートはマージソートにかないませんので、
条件が許すならマージソートのほうが良いということには異論ありません。

回答No.5

rabbit_cat

補足です。

大量データの処理をする場合には、メモリアクセスをできるだけ局在化させる必要があります。動的配列で巨大な領域を確保できたとしても、実体は仮想メモリでしょうから、好き放題にいたるところをアクセスすると、ページング処理が大量に入って劇遅になります。

配列の要素数をNとしたとき、例えばクイックソートですと、最初の分割のときにN/2離れた要素同士の交換処理が発生することがあります。
ヒープソートですと、そもそも分割統治ではないので、最初と最後の要素の交換が発生する可能性もあります。

マージソートは、インプレースで演算できないので、必要なメモリの総量は多いのですが、メモリアクセスを完全に局在化できるので、物理メモリに入りきらないような大量データ処理では、最も高速になると思います。