2次元配列で2項目についてソートのやりかたについて

質問

こんにちは．
VS2005 C++ MFC ダイアログベースでソフトを作成しています．

CString型の配列　Array[100000][3] を定義し，
CSVファイルから読み込んだ値を格納しています．
1列目　X座標
2列目　Y座標
3列目　結果

ファイルから読み込んだデータは以下のように
y優先でxとyの値で昇順に並んでいます．
_____[0] [1] [2]
[0] 200 100 OK
[1] 201 100 OK
[2] 202 100 OK
[3] 200 101 NG
[4] 201 101 OK
[5] 202 101 OK
[6] 201 102 NG
[7] 202 102 OK
…

これを以下のように
x優先でxとyの値で昇順に並び変えたいのですが
どのようにすればよいでしょうか？

_____[0] [1] [2]
[0] 200 100 OK
[1] 200 101 NG
[2] 201 100 OK
[3] 201 101 OK
[4] 201 102 NG
[5] 202 100 OK
[6] 202 101 OK
[7] 202 102 OK

かつ，100000行もあるのでスピードが速い方法だと助かります．
具体的なコードもお願いいたします．

回答No.5

ICE_FALCON

#1です。

できませんでしたか。
reinterpret_castがうまくいかなかったんでしょうかね？
Array[100000][3]を動的に確保してるとか？
まあ、reinterpret_castは環境依存なので、
うまくいかなくても仕方が無いですね。

しょうがないので、普通にコピーしますか。
RowT *rowp = reinterpret_cast<RowT *>(Array);
を削除。

vector<RowT> v(rowp, rowp+100000);
を削除して代わりに、
vector<RowT> v(100000);
iter = v.begin();
for(int i=0;i<100000;i++){
for(int j=0;j<3;j++){
iter->dt[j] = Array[i][j];
}
iter++;
}

後は同じ、でできませんかね？
あと#1お礼の所に書いてある
bool operator<()
で戻り値を戻さない場合がありますね。
最後のelseは書いたほうが良いです。

お礼

おそくなりすいません。

sort(v.begin(), v.end());
の前までは値が入っていたのですが、
ソート後に
int i = 0;
for(iter = v.begin(); iter != v.end(); iter++){
SortedArray[ i ][ 0 ] = iter->dt[ 0 ];
SortedArray[ i ][ 1 ] = iter->dt[ 1 ];
SortedArray[ i ][ 2 ] = iter->dt[ 2 ];

i = i + 1;
}
とすると値が入っていませんでした。

struct RowT
{
CString dt[3];
};
をCStringにしたのがいけなかったのか
ここをintにするとソート後にも値が入っており、
うまく並べ替えられるようになりました。

bool operator<()のところはelseが必要ですね。すいません。

このたびはいろいろ教えてくれてどうもありがとうございました。

回答No.4

7o8

> tmp[X]=atoi(Array[X][0])<<16＋atoi(Array[X][1])
> とはどういうことでしょうか？

処理系にもよりますが、MS C++なら intで32bitを扱えます。
32bitをX,Yで16bitずつ(実質15bitずつですが)使用するようにすれば
X優先でX,Yの値をソートするのに簡単ですよね？ということです。

普通に10進数でも Xを上位3桁、Yを下位3桁の6桁で表現しても
同じことです。
＃X,Yの桁がいくつってのが肝になります。

ちなみに今回の場合は X,Y共に 0～32767までの値に収まっている必要があります。

コードのほうですが、少しはご自分で考えてみましょう。
今時間がないため、提示することができないのですが、
まずはアルゴリズムが理解できればそーは難しくないはずです。

お礼

>処理系にもよりますが、MS C++なら intで32bitを扱えます。
>32bitをX,Yで16bitずつ(実質15bitずつですが)使用するようにすれば
>X優先でX,Yの値をソートするのに簡単ですよね？ということです。
なろほど、そういうことでしたか。
ビットを扱うのは慣れていないの勉強しておきます。

今回の質問ですがICE_FALCONに教えていただいたできるようになりました。
一応int型のデータを並べ替えるように修正したので
さらに処理速度が必要なら、7o8さんの方法で検討したいと思います。
このたびはどうもありがとうございました。

回答No.3

7o8

C言語的な考え方ですが、私なら以下のように作成します。

Array[100000][3]に対応する配列を２つ用意しましょう。
ここでは tmp[10000],idx[10000]とします。
X,Y座標がどの程度の大きさになるのか？次第ですが、例にあるように
3桁数字程度であれば、tmp[],idx[]はint型で以下のように設定します。

　tmp[X]=atoi(Array[X][0])<<16＋atoi(Array[X][1])
　idx[X]=X

tmp[X]を並べ替え、その結果をidx[X]にも反映させれば、Array[idx[X]][3]とすることで
並べ替えられたことになります。

高速化のポイントは 比較はCPUが扱うことができる最も得意なデータで
あるint型を用いることです。
もし例と異なり、数値が3桁整数でない、もしくは小数点含むデータで
あるなら素直にICE_FALCONさんが提示されている方法がいいかと思います。

お礼

ありがとうございます。
すいませんまだ不慣れなもので
コードを全部載せてもらえると助かります。

とりわけ
tmp[X]=atoi(Array[X][0])<<16＋atoi(Array[X][1])
とはどういうことでしょうか？
シフト演算子？16ビットシフトするということでしょうか？

回答No.2

ICE_FALCON

#1です。

・・・３列目いらなかったですね。
bool operator < ()
の深さを一つ減らしてください。

回答No.1

ICE_FALCON

速くは無いですが、std::sortを使うのが簡単です。
私はMFCの環境無いので、とりあえずstd::stringで・・・。

struct RowT
{
string dt[3];
};

bool operator<(const RowT &rowx, const RowT &rowy)
{
if(atoi(rowx.dt[0].c_str()) < atoi(rowy.dt[0].c_str())){
return true;
}else if(atoi(rowx.dt[0].c_str()) > atoi(rowy.dt[0].c_str())){
return false;
}else{
if(atoi(rowx.dt[1].c_str()) < atoi(rowy.dt[1].c_str())){
return true;
}else if(atoi(rowx.dt[1].c_str()) > atoi(rowy.dt[1].c_str())){
return false;
}else{
if(atoi(rowx.dt[1].c_str()) < atoi(rowy.dt[1].c_str())){
return true;
}else if(atoi(rowx.dt[1].c_str()) > atoi(rowy.dt[1].c_str())){
return false;
}else{
return false;
}
}
}
}
//--------------
//main

・・・・
RowT *rowp = reinterpret_cast<RowT *>(Array);
vector<RowT>::iterator iter;
vector<RowT> v(rowp, rowp+100000);
sort(v.begin(), v.end());

for(iter = v.begin(); iter != v.end(); iter++){
cout << iter->dt[0] << ";" << iter->dt[1] << ";" << iter->dt[2] << endl;
}

・・・reinterpret_castがうまくいくかは保証できません・・・。

お礼

ありがとうございます。
ICE_FALCONさんのサンプルを若干変更しました。

struct RowT
{
//CStringに変更//////////////
CString dt[3];
/////////////////////////////
};

bool operator<(const RowT &rowx, const RowT &rowy)
{
//深さを変更/////////////////////////////////////////////////
if(atoi(rowx.dt[0].c_str()) < atoi(rowy.dt[0].c_str())){
return true;
}else if(atoi(rowx.dt[0].c_str()) > atoi(rowy.dt[0].c_str())){
return false;
}else{
if(atoi(rowx.dt[1].c_str()) < atoi(rowy.dt[1].c_str())){
return true;
}else if(atoi(rowx.dt[1].c_str()) > atoi(rowy.dt[1].c_str())){
return false;
}
}
}
}
//////////////////////////////////////////////////////////////
}
//--------------
//main

・・・・
RowT *rowp = reinterpret_cast<RowT *>(Array);
vector<RowT>::iterator iter;
vector<RowT> v(rowp, rowp+100000);
sort(v.begin(), v.end());

//配列に格納するよう変更///////////////////////////
int i = 0;
for(iter = v.begin(); iter != v.end(); iter++){
SortedArray[ i ][ 0 ] = iter->dt[ 0 ];
SortedArray[ i ][ 1 ] = iter->dt[ 1 ];
SortedArray[ i ][ 2 ] = iter->dt[ 2 ];

i = i + 1;
///////////////////////////////////////////////////
}

としたところ，配列SortedArrayにはなにも入っていませんでした。
（すべて""になっていました。）
なにかおかしいところがありますでしょうか？

補足

ちなみに
RowT *rowp = reinterpret_cast<RowT *>(Array);
の時点ではArrayに正常に値が入っています。