こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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行もあるのでスピードが速い方法だと助かります.
具体的なコードもお願いいたします.

投稿日時 - 2009-11-06 19:09:03

QNo.5426871

困ってます

このQ&Aは役に立ちましたか?

1人が「このQ&Aが役に立った」と投票しています

回答(5)

ANo.5

#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は書いたほうが良いです。

投稿日時 - 2009-11-11 00:34:48

お礼

おそくなりすいません。

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が必要ですね。すいません。

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

投稿日時 - 2009-11-16 08:59:32

ANo.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までの値に収まっている必要があります。


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

投稿日時 - 2009-11-10 06:42:22

お礼

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

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

投稿日時 - 2009-11-16 09:04:50

ANo.3

7o8

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

Array[100000][3]に対応する配列を2つ用意しましょう。
ここでは 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さんが提示されている方法がいいかと思います。

投稿日時 - 2009-11-07 21:14:18

お礼

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

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

投稿日時 - 2009-11-09 09:38:36

ANo.2

#1です。

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

投稿日時 - 2009-11-06 22:55:17

ANo.1

速くは無いですが、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がうまくいくかは保証できません・・・。

投稿日時 - 2009-11-06 22:49:33

補足

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

投稿日時 - 2009-11-09 09:39:50

お礼

ありがとうございます。
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にはなにも入っていませんでした。
(すべて""になっていました。)
なにかおかしいところがありますでしょうか?

投稿日時 - 2009-11-09 09:34:59

あなたにオススメの質問