jeak回答ポイント 97ptウォッチ 5

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

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

• はてなアカウントでログイン
• 無料ユーザー登録

みんなの回答

• ita2010/11/15 21:38:40

  満足30pt

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

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

  この影の領域は生き残った点の数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に最終的に消えない点のリストが入ります

  スター

  • jeak 2010/11/16 05:45:19

    ありがとうございます。

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

soan_4q2010/11/16 00:37:02

満足23pt

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

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

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

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

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

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

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

スター

• jeak 2010/11/16 05:43:55

  ありがとうございます。

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

imo7582010/11/18 05:28:56

満足22pt

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

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

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

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

http://codepad.org/0lC55Ls8

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

スター

a-kuma32010/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] &&

    ...

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

スター
• その他の回答を読む

この質問へのコメント

• jeak2010/11/15 16:06:54
  >「そんなものはない」等の回答はご遠慮願います。
  失礼しました。
  「そんなものはない」事の根拠があればＯＫとします(NP困難である等)。
• Mook2010/11/16 01:47:16
  アイデアレベルなので、コメントです。
  
  変数の分布にも寄りますが、
  C の最大値、最小値を作業用変数として用意し、全体の中で Cmax が最初ものを探し、これよりも
  Cmin が大きいものは明らかに削除できるでしょう。
  
  また、ベクタの次数に偏りがあるのであれば、これを分割して上記の処理をすることでより多くの
  インスタンスを省くことができるかと思います。
  
  最後は、直接比較になるかと思いますが、上記のようなフィルタをかけた後に処理をすれば多少
  計算量を減少できないでしょうか。
• imo7582010/11/16 09:01:00
  あまり芳しいものではありませんが…
  
  １：個々の各次元において、値の小さい順で値を整列し、各オプジェクトに順番を格納する
  （０次元目軸においては小さい順からオブジェクト番号５＜２＜７＜６…のように算出したとする）
  （オブジェクト５番の０次元目には１番目、オブジェクト２番の０次元目には２番目、
  オブジェクト７番の０次元目には３番目、オブジェクト番号６番の０次元目には４番目という
  情報を記録していく）
  
  ２：比較基準として取り上げるオブジェクト番号において、最も順番が小さい次元を得る
  （０次元目の４番目が全ての次元において最小の順番であるオブジェクト番号６を比較基準に使うとする）
  
  ３：その次元において比較基準のオブジェクトによって省かれる可能性のあるオブジェクトのリストを得る
  （０次元は５＜２＜７＜６…であり、オブジェクト６番目を比較基準として用いるので、５、２、７を得る）
  （このとき、オブジェクト番号が５、２、７のもの以外は、オブジェクト番号６番目のものと
  比較する必要がない）
  （ただし、同値のデータがある場合は注意）
  
  さらに作業量をケチりたいならば、比較基準に用いるオブジェクトを選ぶ順番に
  工夫の余地がありそうです。最小順番が最大のオブジェクトから比較基準に選ぶとか、
  各次元の（順番÷オブジェクト数）の積をとってその最大値から比較基準に用いるとか…。
• jeak2010/11/16 10:51:28
  今現在実装しているアルゴリズムは次のような感じです。
  
  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]を完全には取りきれないですが、もしこのような許容を加えるとしたら、どんな案が追加で考えられるでしょうか？
  
  
• jeak2010/11/17 12:51:14
  コメントへアイデアを頂いているかた、ポイント配分を行いたいので回答をお願いします。
• imo7582010/11/18 08:39:07
  http://codepad.org/NYju4NcC
  もう少し比較回数を減らすことはできましたが些細なものでした。
  
  ただし70%ほどの探索でよしとするなら
  http://codepad.org/XOnHAcxw
  比較回数を劇的に下げることができるようです。
  
  そのかわりにソートなど事前の計算が別に必要となります。
  また当然のことながら特定の癖のあるデータに対しては弱くなっています。
• ita2010/11/19 19:12:50
  回答１を実装してみました。データが三次元の場合、ランダムなデータだとデータ数が10^6とかになっても最終的に生き残るデータは100以下でサチるようで、回答１だけの実装でO(N^2)よりははるかに少ない比較回数でいけるようです。
  http://f.hatena.ne.jp/ita/20101119185039
  しかし１０次元だとたとえばN=10^5の時 1/4 ほどのデータが生き残り、それほど高速にはなりません。
  そこでこの方法とid:imo758 さんコメントの方法を統合し、生き残っている点のリストを保持しつつ、新たに点を加える時に、このリスト中での新しいデータの各次元の値の順位と、各次元においてリストの要素をソートしたリストを二分木を使ってO(log M)で計算していきます。
  そして新しいデータで一番順位が低い次元についてソートしたリストをケツから新データが出るまで見ていって、新しいデータが既存のデータを消すかどうか比較します。
  消さなかった場合は次に新しいデータで一番順位が上の次元でソートしたリストで、新しいデータから順に上へ見ていって既存のデータが新しいデータを消すかどうか判定します。
  
  これによって10次元、N=10^5の時はN^2 の1/100程度の比較回数で全比較と同じ結果を得ました。グラフの傾きは2よりは若干小さい1.8くらいでしょうか。Nがもっと大きくなると傾きが小さくなるかもしれませんが、手持ちのマシンではちょっと時間がきついようです。
  
  回答１のみ実装
  http://d.hatena.ne.jp/ita/00010420/p1
  
  ソートと併用
  http://d.hatena.ne.jp/ita/00010420/p2
  
  二分木クラス
  http://d.hatena.ne.jp/ita/00010420/p3
  
• imo7582010/11/20 01:38:54
  生き残っているリストが新しいデータを消す確率のほうが
  新しいデータが生き残っているリストに消される確率より
  高いと思いますがどうでしょうか
  
  後者→前者の判定順ではなく
  前者→後者の判定順のほうが
  処理が軽いと思いますが…。
• ita2010/11/21 16:20:36
  試してみました。御指摘の通り、回答１の方法だと逆にしたほうが１０次元の場合は比較回数が半分くらいになりました。sort併用の場合は新データの最高ランクと最低ランクを見てどちらを先にするか変えるということも考えられますね。
  
• jeak2010/11/22 09:53:45
  みなさん回答ありがとうございました。
  やりたい事自体は結構普遍的なことだとは思うので定石的なアルゴリズムがあるのかなーとも思ってましたが、意外に難しいものですね。
  今回の結果は自作中のネトゲ用ツールに応用したいと思います。
  

質問の情報

登録日時

2010-11-15 16:00:37

終了日時

2010-11-22 09:54:50

回答条件

1人1回まで

この質問のカテゴリ

• コンピュータ
• 科学・統計資料

この質問に含まれるキーワード

人気の質問

• キッズケータイのショートメールってあるじゃないですか。 あれって新しく誰かと番号交換(メッセージを送る…匿名質問者11日前
• 幻想交響曲の鐘でなにかおすすめのcdないでしょうか？ 山田生活118時間前
• 参考書で地学を学んでいます. 表計算 解き方 分かりません （⼤気の炭素量,?((?, ?!"!, ?) （⾵化フラック…ronpao1日前
• 戸籍法107条（氏の変更届)について質問があります。 「やむを得ない事由によつて氏を変更しようとするとき…minminjp200131日前
• マニラランウェイは、航空チケットがなくても、徒歩で通過できるのでしょうか、門番が入口と出口にいると聞…匿名質問者16時間前

メニュー

• 質問一覧
• カテゴリ一覧
• 無料ユーザー登録
• 人力検索はてなトップ

PC版

• お問い合わせ
• ヘルプ
• お知らせ
• はてなトップ