人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

比較アルゴリズム 改善案求む
以前yahooに記載したものですが良質な回答が得られなかったためこちらで再度質問させていただきます。

多次元ベクトル値を持つデータの集合中、全ての次元においてそれ以上の値が存在するデータを省きたいと思います。
具体的には次のような感じです。

class C {
int v[10];
}

C obj[10000];

for (i=0; i<10000; i++) for (j=i+1; j<10000; j++) {
//
if (
obj[i].v[0] >= obj[j].v[0] &&
obj[i].v[1] >= obj[j].v[1] &&
...
obj[i].v[9] >= obj[j].v[9]
)
{
// obj[j]を削除
}

のようなことをやりたいです(実際にはデータはstd::listで管理しています)。
全てのインスタンス同士で比較するとO(N^2)の計算量となっています。
計算量を減らすうまい方法はないでしょうか?

「そんなものはない」等の回答はご遠慮願います。

(参考)
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1148208666


●質問者: jeak
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:Class STD Yahoo いただきます うまい
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● ita
●30ポイント

幾何学的に考えると、10次元空間で各点から、どの座標もそれより小さい領域に影ができて、

最終的にほかの点の影になってない点が生き残ることになります。

この影の領域は生き残った点の数Mだけトゲのある複雑な形となります。

ここに新たに点を追加する場合、問題の複雑さからいってこの点が影の領域に入るかどうかはMに比例した判定時間がかかるでしょう。

ということはO(NM)の時間は最低でもかかるのではないかと予想できます。

そしてMがNより十分小さくなるなら、N^2よりも高速化できる可能性があります。

この方針でやるなら、まず有効な点のリストLを空に初期化し、

for(i=0;i<10000;i++)
{
 C *c1=&Obj[i];
 for(c2= Lの各要素)
 {
 if(c1がc2を消す)
 {
 c2をLから消す
 }
 else if(c2がc1を消す)
 {
 c1=NULL;break;
 }
 }
 if(c1!=NULL) c1をLに追加;
}

とすればO(NM)でLに最終的に消えない点のリストが入ります

◎質問者からの返答

ありがとうございます。

これは新しい発想です。実装する価値ありですね。


2 ● soan_4q
●23ポイント

もう1次元増やして、全次元の合計値を入れる。

その値が低い順にソートする。

削除対象は「全ての次元においてそれ以上の値が存在するデータ」なので

自分自身よりも前に居るデータは、最低でも1次元は自分よりも低いことが確実であるから

比較対象にするまでもない。

自分を削除するための判定を自分よりも後ろに対してだけ行えばよい

全件のチェックをする場合の約半分の計算量になるはずです。

◎質問者からの返答

ありがとうございます。

じつはこれに近い処理は既にいれてまして…


3 ● imo758
●22ポイント

Perlという言語で失礼します

下記のアイデアでかつ完全ランダムなデーターにおいて計算量は

次元数で除するくらいにしか削減できないみたいですね…

しかもオーダーとしては変わらないようです。

http://codepad.org/0lC55Ls8

比較関数を呼び出した回数は10次元1万点で1000万回弱でした。


4 ● a-kuma3
●22ポイント

何かの基準で、C の list をソートするのは、最初に考えたのですが、ソートする時点で N log N の計算量が発生しちゃうので、効率はあまり良くならないですよね。


C のインスタンスを作るときに、それぞれの次元の最小値/最大値を C のメンバーとして抱えておいて、

C のインスタンスを比較するときに、それぞれの次元を比較する前に、互いの最小値と最大値を比べると、

計算量が少なくなるんじゃないか、という気がします。


if (

obj[i].v[0] >= obj[j].v[0] &&

obj[i].v[1] >= obj[j].v[1] &&

    ...

if (

obj[i].min > obj[j].max || /* ★これ */

obj[i].v[0] >= obj[j].v[0] &&

obj[i].v[1] >= obj[j].v[1] &&

    ...

データの散らばり方にもよりますが、明らかに違うものを先に刈り取れる分、計算量を減らせるんじゃないかと。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ