比較アルゴリズム 改善案求む

以前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

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:2010/11/15 16:00:37
  • 終了:2010/11/22 09:54:50

回答(4件)

id:ita No.1

ita回答回数203ベストアンサー獲得回数472010/11/15 21:38:40

ポイント30pt

幾何学的に考えると、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に最終的に消えない点のリストが入ります

id:jeak

ありがとうございます。

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

2010/11/16 05:45:19
id:soan_4q No.2

soan_4q回答回数12ベストアンサー獲得回数02010/11/16 00:37:02

ポイント23pt

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

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

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

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

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

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

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

id:jeak

ありがとうございます。

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

2010/11/16 05:43:55
id:imo758 No.3

imo758回答回数121ベストアンサー獲得回数192010/11/18 05:28:56

ポイント22pt

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

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

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

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

http://codepad.org/0lC55Ls8

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

id:a-kuma3 No.4

a-kuma3回答回数4463ベストアンサー獲得回数18412010/11/20 23:00:24

ポイント22pt

何かの基準で、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] &&

    ...

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

  • id:jeak
    >「そんなものはない」等の回答はご遠慮願います。
    失礼しました。
    「そんなものはない」事の根拠があればOKとします(NP困難である等)。
  • id:Mook
    アイデアレベルなので、コメントです。

    変数の分布にも寄りますが、
    C の最大値、最小値を作業用変数として用意し、全体の中で Cmax が最初ものを探し、これよりも
    Cmin が大きいものは明らかに削除できるでしょう。

    また、ベクタの次数に偏りがあるのであれば、これを分割して上記の処理をすることでより多くの
    インスタンスを省くことができるかと思います。

    最後は、直接比較になるかと思いますが、上記のようなフィルタをかけた後に処理をすれば多少
    計算量を減少できないでしょうか。
  • id:imo758
    あまり芳しいものではありませんが…

    1:個々の各次元において、値の小さい順で値を整列し、各オプジェクトに順番を格納する
    (0次元目軸においては小さい順からオブジェクト番号5<2<7<6…のように算出したとする)
    (オブジェクト5番の0次元目には1番目、オブジェクト2番の0次元目には2番目、
    オブジェクト7番の0次元目には3番目、オブジェクト番号6番の0次元目には4番目という
    情報を記録していく)

    2:比較基準として取り上げるオブジェクト番号において、最も順番が小さい次元を得る
    (0次元目の4番目が全ての次元において最小の順番であるオブジェクト番号6を比較基準に使うとする)

    3:その次元において比較基準のオブジェクトによって省かれる可能性のあるオブジェクトのリストを得る
    (0次元は5<2<7<6…であり、オブジェクト6番目を比較基準として用いるので、5、2、7を得る)
    (このとき、オブジェクト番号が5、2、7のもの以外は、オブジェクト番号6番目のものと
    比較する必要がない)
    (ただし、同値のデータがある場合は注意)

    さらに作業量をケチりたいならば、比較基準に用いるオブジェクトを選ぶ順番に
    工夫の余地がありそうです。最小順番が最大のオブジェクトから比較基準に選ぶとか、
    各次元の(順番÷オブジェクト数)の積をとってその最大値から比較基準に用いるとか…。
  • id:jeak
    今現在実装しているアルゴリズムは次のような感じです。

    for (int i=0; i<10; j++) {
    // 1. 次元v[i%10],v[(i+1)%10],...の順で降順ソート
    // 2. obj[n]とobj[n+1]を比較、obj[n+1]のほうが全ての次元においてobj[n]より低ければobj[n+1]を削除
    }

    この方法で計算量をO(N)(削除のための比較)+O(NlogN)(ソート)に下げています。
    この方法では不要なobj[n]を完全には取りきれないですが、もしこのような許容を加えるとしたら、どんな案が追加で考えられるでしょうか?

  • id:jeak
    コメントへアイデアを頂いているかた、ポイント配分を行いたいので回答をお願いします。
  • id:imo758
    http://codepad.org/NYju4NcC
    もう少し比較回数を減らすことはできましたが些細なものでした。

    ただし70%ほどの探索でよしとするなら
    http://codepad.org/XOnHAcxw
    比較回数を劇的に下げることができるようです。

    そのかわりにソートなど事前の計算が別に必要となります。
    また当然のことながら特定の癖のあるデータに対しては弱くなっています。
  • id:ita
    回答1を実装してみました。データが三次元の場合、ランダムなデータだとデータ数が10^6とかになっても最終的に生き残るデータは100以下でサチるようで、回答1だけの実装でO(N^2)よりははるかに少ない比較回数でいけるようです。
    http://f.hatena.ne.jp/ita/20101119185039
    しかし10次元だとたとえばN=10^5の時 1/4 ほどのデータが生き残り、それほど高速にはなりません。
    そこでこの方法とid:imo758 さんコメントの方法を統合し、生き残っている点のリストを保持しつつ、新たに点を加える時に、このリスト中での新しいデータの各次元の値の順位と、各次元においてリストの要素をソートしたリストを二分木を使ってO(log M)で計算していきます。
    そして新しいデータで一番順位が低い次元についてソートしたリストをケツから新データが出るまで見ていって、新しいデータが既存のデータを消すかどうか比較します。
    消さなかった場合は次に新しいデータで一番順位が上の次元でソートしたリストで、新しいデータから順に上へ見ていって既存のデータが新しいデータを消すかどうか判定します。

    これによって10次元、N=10^5の時はN^2 の1/100程度の比較回数で全比較と同じ結果を得ました。グラフの傾きは2よりは若干小さい1.8くらいでしょうか。Nがもっと大きくなると傾きが小さくなるかもしれませんが、手持ちのマシンではちょっと時間がきついようです。

    回答1のみ実装
    http://d.hatena.ne.jp/ita/00010420/p1

    ソートと併用
    http://d.hatena.ne.jp/ita/00010420/p2

    二分木クラス
    http://d.hatena.ne.jp/ita/00010420/p3
  • id:imo758
    生き残っているリストが新しいデータを消す確率のほうが
    新しいデータが生き残っているリストに消される確率より
    高いと思いますがどうでしょうか

    後者→前者の判定順ではなく
    前者→後者の判定順のほうが
    処理が軽いと思いますが…。
  • id:ita
    試してみました。御指摘の通り、回答1の方法だと逆にしたほうが10次元の場合は比較回数が半分くらいになりました。sort併用の場合は新データの最高ランクと最低ランクを見てどちらを先にするか変えるということも考えられますね。
  • id:jeak
    みなさん回答ありがとうございました。
    やりたい事自体は結構普遍的なことだとは思うので定石的なアルゴリズムがあるのかなーとも思ってましたが、意外に難しいものですね。
    今回の結果は自作中のネトゲ用ツールに応用したいと思います。

この質問への反応(ブックマークコメント)

トラックバック

  • ナンバーワンよりオンリーワン http://q.hatena.ne.jp/1289804435 ネトゲの武器とか、いろんなパラメータがありますが、全てのパラメータにおいて他のある武器を上回っている、という武器は同系
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません