2

配列のリストと多くのセットアップ時間が与えられた場合、各配列の一部のサブスパンで最小値をすばやく見つける必要があります。コンセプト:

class SpanThing
{
     int Data;
     SpanThing(int[][] data) /// must be rectangulare
     {
         Data = data;
         //// process, can take a while
     }

     int[] MinsBruteForce(int from, int to)
     {
         int[] result = new int[data.length];
         foreach(int index, int[] dat; Data)
         {
             result[i] = int.max;
             foreach(int v; dat[from .. to]);
                result[i] = min(result[i], v);
         }
         return result;
     }
     int[] MinsSmart(int from, int to)
     {
          // same as MinsBruteForce but faster
     }
}

これを行う方法についての私の現在の考えは、各ノードが関連するスパンの最小値を含むデータ上にバイナリ ツリーを構築することです。そのようにして、1 つの行のスパンの最小値を見つけることは、それを構成するツリー ノードのみの最小値を見つけることで構成されます。このセットは各行で同じになるため、一度計算できます。

このアイデアに問題があるか、より良い方法が知られている人はいますか?

明確にするために、私が話しているツリーは、ルートノードに行全体の最小値が含まれ、各ノードの左側の子が親のスパンの左半分の最小値を持ち、右も同様。

 0   5   6  2   7   9   4   1   7   2   8   4   2
 ------------------------------------------------
   | 5 | 6|   | 7 | 9 |   | 1 | 7 | 2 | 8 | 4 | 2  
 0 |   5  | 2 |   7   | 4 |   1   |   2   |   2  
   0      |   2       |   1       |       2
          0           |           1
                      0

このツリーを配列にマップし、セグメントの境界を計算して検索を高速化できるように定義することができます。

私が最適化しているケースは、入力セットが固定されており、事前に多くの時間を費やしているが、さまざまなスパンで多くの高速テストを実行する必要がある場合です。

4

3 に答える 3

2

提案されたソリューションは、一定のスペースオーバーヘッド、一定の時間のセットアップ、およびクエリの対数時間を使用して答えを与えるように見えます。二次空間 (つまり、すべての間隔を事前に計算) を支払う意思がある場合は、一定時間で答えを得ることができます。対数スキームが優先されることはほぼ確実です。

より良い結果が得られたとしても驚くことではありませんが、より良い結果が得られる単純なデータ構造があったとしても、私はショックを受けます。実際には、対数時間はほとんどの場合十分に高速です。頑張れ。

于 2009-02-07T22:56:06.803 に答える
2

説明されているアプローチは、ある種のメモ化またはキャッシュを実行しようとしているように聞こえますが、同じスパンまたはネストされたスパンを繰り返しチェックしている場合にのみ役立ちます。

min([0..n])の一般的なケースはO (n)になります。これは既に取得したものです。

あなたのコードは、配列内の順序よりも配列内の実際の数値を気にしているようです。これらのスパンを繰り返しチェックする場合、最初にデータをソートすることは可能ですか?これは、単一のO(n log n)操作の後に一連のO(1)操作が続く可能性がありますか? ほとんどの言語には、標準ライブラリに何らかのソート アルゴリズムが組み込まれています。

于 2009-02-07T20:13:29.080 に答える
0

あなたが説明したツリーアプローチを使用して、間隔の階層を効率的に表現する方法は明確ではありません。間隔を分割するには多くの方法があります --- すべての可能性を考慮する必要がありますか?

このような単純なアプローチで十分でしょうか:dataが N x M 配列であるとします。(i,j,k)エントリが の「最小」を与えるM x M x N 配列を作成しますdata(k,i:j)。配列エントリはオンデマンドで設定されます。

int[] getMins(int from, int to)
{
    assert to >= from;

    if (mins[from][to] == null)
    {
        mins[from][to] = new int[N];

        // populate all entries (from,:,:)
        for (int k = 0; k < N; k++)
        {
            int t = array[k][from];

            for (int j = from; j < M; j++)
            {
                if (array[k][j] < t)
                    t = array[k][j];

                mins[from][j][k] = t;
            }
        }
    }

    return mins[from][to];
}
于 2009-02-07T20:44:29.440 に答える