【アルゴリズムを教えてください】

要素数 m の配列が n 個あるとします。
一つめの配列のそれぞれの要素が全体で小さいほうから何番目に
あるかを算出するアルゴリズムで、O(nm^2) より小さいものを教えてください。
ただし、同順位の場合は順位の平均を求めるものとします。

例:(m = 4, n = 3)
[21, 11, 16, 19]
[20, 15, 12, 17]
[14, 21, 18, 13]
が与えられたとき、[11.5, 1, 6, 9] を求めたい。

回答の条件
  • 1人2回まで
  • 登録:2009/05/08 14:48:04
  • 終了:2009/05/08 18:28:45

ベストアンサー

id:cdaotg No.1

cdaotg回答回数84ベストアンサー獲得回数202009/05/08 15:18:26

ポイント100pt

アルゴリズムとして名前があるかは不明ですが、今思い付いたアルゴリズムを書きます。

(質問文のO(nm^2)はO((nm)^2)だと考えて、要求を満たすものだと考えました。私の思い違いでしたら申し訳ありません。)


1. 全ての配列を1つの(mn要素の)配列にまとめる(O(mn))

2. 上記の配列をソートする(適切なアルゴリズムを使えばO(mn log(mn)))

3. ソート済みの配列から必要な順位を計算する(大体O((m^2)n)?)


質問文の例だと

1. [21, 11, 16, 19, 20, 15, 12, 17, 14, 21, 18, 13]

2. [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21]

3. ソート済みの配列から、21の平均順位は11.5、11の順位は1、…


3.の処理ですが、ソート済みの配列から任意の一要素(例えば11)を見つけるのは二分探索でO(m log(mn))。そこから同順位の要素を探すのが(1個あたりのワーストケースが)O(mn)なので、3.のオーダーはO((m^2)n)ではないかと。

という訳で、全体のオーダーは3.のO((m^2)n)になります。

id:akagi_paon

えーと、O(nm^2) は O(n×m×m) の意味です。

単純に全体をなめるアルゴリズムでも O(n×m×m) でできますよね?

とりあえず実装してみて使えそうならポイント差し上げます。

----

実装してみました。

ハッキリ言って、むちゃくちゃ速くなりました!

今まで20分ほどかかっていた処理が50秒で終わりました\(^o^)/

ありがとうございました!

2009/05/08 18:18:56
  • id:akagi_paon
    補足ですが、配列の要素は実際は整数とは限りませんので注意してください。
  • id:cdaotg
    >O(nm^2) は O(n×m×m) の意味です
    そうでしたか、失礼しました。
  • id:SALINGER
    全体をソートしてしまうと、全体を走査するO(nm^2)よりも時間が掛かってしまいますね。
    そこで、考えた方法は、
    まず例では、21を全体から走査して順位を出します。
    そのときに、各要素を21より大きい物と小さい物の2つの要素分けます。
    次に、11の順位を出すときに21より小さいので先ほどの小さい物を集めた要素から順位を出します。
    このように、一つ前の要素を利用して短縮することで、O(nm^2)より早くなります。
  • id:Mook
    締め切りになっていますが、せっかく作ってみたのでサンプルです。
    対象となる先頭の配列のみソートしていますが、あとは1回のスキャンで
    終わっているので、計算量としては O(mn)になります。
    n が十分大きい場合には有効かと思います。

    <html>
    <head>
    <script type="text/javascript">
    <!--
    function arrayRanking(){
    var ar1=document.getElementsByName("ar1");
    var ars=document.getElementsByName("ar");
    var ans=document.getElementsByName("ans");

    var backet = Array( ar1.length * 2 );
    var base = Array( ar1.length );

    for ( var i=0 ; i< ar1.length ; i++ ) {
    if ( isNaN( ar1[i].value ) ) {
    alert("未入力データがあります。" );
    return;
    }
    base[i] = ar1[i].value;
    }
    base.sort( cmp );

    // データの初期化
    for ( var i=0 ; i< ar1.length ; i++ ) {
    backet[2*i] = 0;
    backet[2*i + 1] = 1;
    }


    // データのチェック
    for ( var i=0 ; i< ars.length ; i++ ) {
    if ( isNaN( ars[i].value ) ) {
    alert("未入力データがあります。" );
    return;
    }
    }


    // 集計処理
    for ( var i=0 ; i< ars.length ; i++ ) {
    for( var j=0 ; j<base.length ; j++ ) {
    if ( ars[i].value < base[j] ) {
    ( backet[2 * j] )++;
    break;
    }
    if ( ars[i].value == base[j] ) {
    backet[2 * j + 1]++;
    break;
    }
    }
    }

    // 結果の集計
    var sum = 0;
    for ( var i=0 ; i<base.length ; i++ ) {
    sum += backet[2*i];
    for( var j=0 ; j<ar1.length ; j++ ) {
    if ( Number( ar1[j].value ) == base[i] ) {
    ans[j].value = sum + 1 + (backet[2*i+1] == 1 ? 0 : 1 ) / backet[2*i+1];
    }
    }
    sum += backet[2*i + 1];
    }
    }

    function cmp( a, b ){
    return ( a > b ) ? 1 : -1;
    }

    -->
    </script>
    </head>
    <body>
    <input type="text" name="ar1" value="21">
    <input type="text" name="ar1" value="11">
    <input type="text" name="ar1" value="16">
    <input type="text" name="ar1" value="19">
    <br>

    <input type="text" name="ar" value="20">
    <input type="text" name="ar" value="15">
    <input type="text" name="ar" value="12">
    <input type="text" name="ar" value="17">
    <br>

    <input type="text" name="ar" value="14">
    <input type="text" name="ar" value="21">
    <input type="text" name="ar" value="18">
    <input type="text" name="ar" value="13">
    <br>
    <br>
    <br>
    <input type="button" value="実行" onclick="arrayRanking();">
    <br>
    <br>
    <input type="text" name="ans">
    <input type="text" name="ans">
    <input type="text" name="ans">
    <input type="text" name="ans">
    <br>
    </body>
    </html>
  • id:akagi_paon
    SALINGER さん、Mook さん、コメントありがとうございます。
    特に Mook さんのは休みが明けたら実装してみようかと思います
    (JavaScriptはあんまりわかんないんですよね・・・)
  • id:akagi_paon
    Mook さん・・・これ・・・
    一番上の段を[1,2,3,4]にすると結果が[1,8,11,12]になるんですけど・・・
    なにか間違ってませんか?
  • id:Mook
    数値が文字列として処理されている部分があったようです。

    // 集計処理
    for ( var i=0 ; i< ars.length ; i++ ) {
    for( var j=0 ; j<base.length ; j++ ) {
    if ( Number(ars[i].value) < base[j] ) {
    ( backet[2 * j] )++;
    break;
    }
    if ( Number(ars[i].value) == base[j] ) {
    backet[2 * j + 1]++;
    break;
    }
    }
    }

    のように
      ars[i].value

      Number(ars[i].value)
    に変えてください。
  • id:cdaotg
    今更回答1の補足ですが「そこから同順位の要素を探すのが(1個あたりのワーストケースが)O(mn)なので」の部分は、本当にワーストケース(要素の重複がかなり多いケース)を想定して書いたので、実際はそこまで遅くはないかもしれません。
    SALINGERさんのアイデアは面白いですね。一度処理した結果を流用するというのは私には思い付きませんでした。
  • id:Mook
    JavaScript がお得意ではないということなので、
    とりあえずアルゴリズムの説明です。

    (1)計測対象の配列(1列目:サイズ N)だけをソートした配列を用意します。
      (このとき元の順番を示す情報を作成しておくと結果の処理が楽になりそうです)。
       DataArray[N] (JavaScript では base[N] )

    (2)計測用の配列(サイズ N)を二つ用意します(例示では面倒なので 2Nの配列にしました)。  
       LessThanArray[N]   (JavaScript では backet[2N] ・・・・正しい綴りは bucket でした。)
       SameArray[N]

    (3)すべてのデータを先頭配列のN番目のデータより小さい、N番目のデータに等しい、に応じてカウントします。
       LessThanArray[i] は DataArray[i-1] より大きく DataArray[i] より小さいものの数
       SameArray[i] は DataArray[i] と等しいものの数

    (4)DataArray[i] の順位は 次の式になります。
       DataArray[i] の順位 =( LessThanArray[0] から LessThanArray[i] までの和 )+ 1 +(※ 同じものがある場合の勘案分)

      ※の処理があいまいな部分があるのですが、11番目のものが4つあったら 11.25 になるのですか?
      であれば、JavaScript にあるように、SameArray[i] が2以上の場合のみ、
       (4)に ( 1 / SameArray[i] )を足します。

    各データを処理する部分は(3)のデータを計数する部分のみですので、O(mn)になるかと思います。


    どうでもよい話ですが、
    O(...)というのは係数を無視した計算量のオーダーを示す表現なので
    実際の計算量が 100 × m × n でも 1/100 × m × n でも O(mn) となります。

    例えばバブルソートの平均計算量は 1/2 n × n ですが、O(n^2) というように表現します。
  • id:akagi_paon
    Mookさん、アルゴリズムの解説ありがとうございます。
    だいたいつかめました。
    ところで(3)の処理って O(nm^2) かかるような気がするんですけどどうでしょう?
    テーブル全体をなめるのに O(mn)、LessThanArray の添字を出すのに(上のプログラムでは) O(m) かかっている気がします。
    添字を求めるのにバイナリサーチを使えば O(nm*log(m)) くらいにはできそうですけど。
  • id:Mook
    うーん、確かにそうですね。
    考え違いをしていたようです。

    ただ、負け惜しみですが、m×n の要素全体をソートするコストは
    クイックソートでもO(nm・log(mn))ですから、それよりは高速だと
    思います。

    mが大きいのであれば、バイナリサーチを使用したほうが良いかも
    しれませんが、実例のように4程度であれば、単純な比較でも性能に
    影響はなさそうな気もします。

    実際の、m、nはどのくらいの数値なのでしょうか。
  • id:akagi_paon
    >実際の、m、nはどのくらいの数値なのでしょうか。
    m=300~100000, n=30~100 くらいです。

    実装してみましたが、速度に関しては cdaotg さんのアルゴリズムも Mook さんのアルゴリズムもたいした違いは出ませんでした(Mook さんの方がちょっとだけ遅かった)
    しかし、cdaotg さんのアルゴリズムでは配列を最初にすべて取り込んでおかないといけないのに対し、Mook さんのアルゴリズムでは逐次的に取り込めばいいので、消費メモリ量に格段に差が出ました。
    よって、Mook さんのアルゴリズムを使おうと思います。
    Mook さんありがとうございました。あとでポイント送信させていただきます。
  • id:Mook
    >m=300~100000, n=30~100 くらいです。
    あらら、期待していた状態とは逆に m の方がずっと大きいのですか。
    であれば、cdaotg さんのアルゴリズムとさほど性能差はないですね。

    実際にどの言語で実装されているのか、入出力のデータ形式がなんであるのか、
    またデータ運用がどうであるかも興味のあるところですが、単純にアルゴリズムを
    考えるだけでも興味深い問題で、こちらも楽しませていただきました。

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

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

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

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