はじめまして。
当方、VC.NET2003 MFCで作業しています。
ある番号を配列で管理します。入力された番号を配列から、
重複しているかどうかを調べ、重複しているのならはじき、
重複していないのであれば配列に番号を追加する、というようなことを
しています。番号数は千単位あります。
構造体の配列を管理するクラスを作成したのですが、
構造体配列ではかなりストレスがあるスピードになりました。
そこでCUIntArrayでも使って管理しようとも考えたのですが、
CStringArrayは遅いといわれていますが、CUIntArrayはみなさん
どう思われますか？ご意見ください。
重複チェックならば、Mapリストのほうがいいのでは？
CMap系を調べてみてください。
ついでに、
番号を文字列で比較するとさらに遅くなりますよ。
何でかは分かりますよね。。。？
>重複チェックならば、Mapリストのほうがいいのでは？
>CMap系を調べてみてください。
Mapリスト...知りませんでした(--;)
これはいい情報ありがとうございますm(__)m
>番号を文字列で比較するとさらに遅くなりますよ。
文字列？CUIntArrayは文字列使えましたっけ？
CStringArrayはうちでは禁止になっていますので、もう使うことは
ないでしょうね．．．。
入力された順番を維持したいならちょいと仕掛けが必要です。
編集 削除# MFCのコンテナを使わなくても良い場合のご参考として。
すでに出現した値かどうかをチェックするために、配列とは別にsetを用意す
るのはどうでしょう。
set内の要素は２分木で探索されますから、一般的には配列内の探索より速い
はずです。
setへの要素挿入＋探索のコストと配列内を探索するコストの比較になります
が数が大きくなればなるほどトータルでは前者の方が低くなると思われます。
測ってみないと確実なことは言えないですが。
// お試し
#include <vector>
#include <set>
#include <cstdlib>
#include <iostream>
int main()
{
std::vector< int > coll;
std::set< int > checker; // 既出値チェック用セット
for( int i = 0; i < 100; ++i ){
int val = std::rand() % 100;
if( checker.insert( val ).second ){
coll.push_back( val );
}
}
// 結果を表示してみる
for( std::vector< int >::size_type i = 0; i < coll.size(); ++i ){
std::cout << coll[ i ] << " ";
}
std::cout << std::endl;
}
ふと気になったのですが
>番号数は千単位あります。
この番号数というのは、検索対象の配列でしょうか？それとも追加対象の個数でしょうか？
追加対象ならまだしも、検索対象が千単位なら、整数配列の判定がストレス対象になるとは思えないけど
> 追加対象ならまだしも、検索対象が千単位なら、整数配列の判定がストレス対象になるとは思えないけど
ためしてみよう。
// お試し
#include <vector>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <windows.h>
long test_1(const int* data, int n) {
std::vector< int > coll;
long t = GetTickCount();
for (int i = 0; i < n; ++i ){
int val = *data++;
if ( std::find(coll.begin(), coll.end(), val) == coll.end() ) {
coll.push_back( val );
}
}
return GetTickCount() - t;
}
long test_2(const int* data, int n) {
std::vector< int > coll;
std::set< int > checker; // 既出値チェック用セット
long t = GetTickCount();
for (int i = 0; i < n; ++i ){
int val = *data++;
if ( checker.insert( val ).second ){
coll.push_back( val );
}
}
return GetTickCount() - t;
}
int main() {
std::vector<int> input;
for( int i = 0; i < 1000000; ++i ){
input.push_back(std::rand() % 100);
}
std::cout << test_1(&input[0], input.size()) << std::endl;
std::cout << test_2(&input[0], input.size()) << std::endl;
}
結果: 元データ数100万で 400対800。
千個かそこらでは差が出ないみたいっす。
…てゆっか、set使うと余計に遅くなってんじゃん orz
編集 削除> …てゆっか、set使うと余計に遅くなってんじゃん orz
追試しました。
ただ、値の種類を増やすと"test_1"はほぼ線形で遅くなりますね。
当然と言えば当然ですが^^
for( int i = 0; i < 1000000; ++i ){
input.push_back(std::rand() % 10000); // ここを変えてみる。
}
…ですね。0〜1000の乱数百万個で4500対1000でした。
これならvectorをベタに使うより4倍強速い。
さらに追試。 VC8のハッシュ表: stdext::hast_set を使ってみました。
結果:0〜1000の乱数百万個で
vectorベタ : set : hash_set ≒ 4407 : 1041 : 760
vectorベタより6倍弱速い。
スレ主の返事が見当たらないみたいですけれど、これからかな。
最初の話からすると追加まで含めた一連の処理での話みたいですが、
そもそも、配列上のデータの並びはどうなっているのでしょう？
追加といっていますが、末尾に追加ですか？
それともソート順に従った位置に挿入ですか？
それによっても処理の重さがかなり違うと思いますけれど。
あと、C++でデータの参照等に内容がコピーされるつくりだと
参照するたびにコピーだのテンポラリのインスタンスが起きるだの
色々と処理が動くので結構遅かった入りすることがありますが、
そちらの方の影響は考慮されていますか？
>スレ主の返事が見当たらないみたいですけれど、これからかな。
スイマセン…昨日はネットを触らなかったもので。
当方の考えは、番号を配列としてもっているのは番号のバッティングを防ぐためです。なので、この配列上では追加やソートなども行いません。
たとえば、わかりやすく説明しますと、
---------------------------------------------------
四角形Aの構成点番号．．．点A、点B、点C、点D
五角形Aの構成点番号．．．点A、点B、点E、点F、点G
---------------------------------------------------
四角形Aを追加すると、点A〜点Dの番号がclassAに登録されます。
また、点A〜点Dの番号をCUIntArrayのarrayにAddします。
次に五角形Aを追加します。ここでは四角形Aで登録した点Aと点Bが存在しており、このまま五角形Aの点番号をclassAに登録すると点A、点Bが2つ存在してしまうことになり、その前にarrayでバッティングをチェックし、
点E〜点GのみがclassAに登録されます。
なぜ、ClassAでバッティング管理すればよいと思われるかもしれませんが、
このような仕様だと思ってください。
なにをもってストレスかといえば、使う側が遅いと感じたらアウトかと。
そのためにもインジケータなどを使ってごまかしてはいますが、
早いにこしたことはないです。
生意気でした(\_\;)
>当方の考えは、番号を配列としてもっているのは番号のバッティングを防ぐ>ためです。なので、この配列上では追加やソートなども行いません。
↑
自分の発言
スイマセン、配列には追加は行いますね。
追加といってもAddなのでケツにおくだけです。
んで、はじめからケツめでループさせてバッティングを見つけます。
気になったのは、どの部分がボトルネックになっているのかと言う調査は
既になされているのだろうかと言う点です。ストレスと感じるかどうかは
確かに使用者の感じ方しだいなので見せ方でさも早く動いているように見せる
というのはやりますが、配列の検索でバッティングを見つけ出すのが
遅いのか他の部分が遅いのかそれによって対処が変わりそうだなと感じました。
バイナリ比較でなおかつ配列の末尾に追加すると言う方法で検索スピードが
リーズナブルな数値であるのならおそらくそれが限界でしょう。
後は見せ方で逃げるしかないかと。
あと、MFCのArray系のクラスはデバッグ版とリリース版で動作速度に
天と地くらいの差が出ます。多分、ご存知と思いますが参考まで。
メモリに余裕があり、
整数の値に有る程度の最大値が決まっている場合
取りうるすべての可能性分のフラグを用意しておいてピンポイントで判定する。
という手法もあります
これならバッティングの判定が一回ですむため
すでに登録されている数に左右されることなくほぼ一定の速度が保てる。
欠点は、最初の２行の条件があること
みなさま、たくさんのご意見ありがとうございます。
知らなかった情報がたくさんありました。
やはり、プログラムや開発というのは個人の癖がでてくるものです。
長年やっていると特にパターンが決まってきますよね。
最近は、マシンの性能も上がりプログラムもそこまでナーバスに
組まなくてもよくなりましたが、でも癖上メモリーをあまり使いたく
ない思ってしまうのです。
現段階、CUIntArrayを使うことにしました。
あとはグラフィカルな見てて楽しいインジケータでも作成して
ごまかすことにします。
でも今後を考えて新たなモジュールを作成してもいいかも。
ありがとうございました。