6

私には問題があり、OKっぽい解決策があります。私はそこにもっと良い解決策があることを望んでいます。

問題

約200,000個の整数の配列があります。2つのインデックスi1とi2が与えられた場合、i1とi2の間のすべての要素の合計を計算する必要があります。配列内の各整数は1から4までです。例えば：

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

この操作は約20万回実行されるため、かなり高速である必要があります。forループの単純なカウンターはO（n）であり、遅すぎます。アレイは構築後に変更されることはないため、比較的高価な前処理段階があっても問題ありません。

これまでの私の最善の解決策

このアルゴリズムはO（log n）時間で機能します。

最初に、元の配列の長さが2の累乗になるまで、元の配列にゼロを埋め込みます。次に、配列を2つの等しい部分に分割し、それぞれの合計を格納します。次に、配列を4分の1に分割し、それぞれの合計を格納します。それから8分の1。配列が2要素の長さのセクションに分割されるまでこれを続けます。上記の8要素配列の場合、これには2つの手順が必要です。

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

次に、2つのインデックスが与えられると、O（log n）時間でsubsection_sumを計算できるようになります。たとえば、subsection_sum（a、2、7）== Quarters [1] +halves[1]です。

4

2 に答える 2

14

累積合計を含む補助配列を導入します。つまりi、補助配列の要素には、元の配列の要素0から要素の合計が含まれますi。サブ配列の合計は、補助配列からの2つの要素の差にすぎません。これにより、一定の時間で結果が得られO(1)ます。

subsection_sumこれは、質問で与えられた関数の不変量に​​依存します。

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2)

私が想定しているところi1 <= i2。再配置すると、次のようになります。

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)

右側の合計は両方とも。から始まることに注意してください0。subsection_sum(a, 0, i)補助配列は、すべてののゼロからの合計の値をキャッシュしていると見なすことができますi。

于 2011-05-22T14:26:02.957 に答える
3

追加の記憶域を確保できる場合は、入力配列内のインデックス (両端を含む) までの要素の合計が th 要素でO(n)あるルックアップ テーブルを作成できます。擬似コード:i0i

def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i] + lookupTable[i-1]

    return lookupTable

次に、このテーブルを使用して、その間にあるすべての要素の合計を計算しarray、差i1をi2取ることができます

lookupTable[i2] - lookupTable[i1]

これには一定の時間がかかります。

于 2011-05-22T14:33:52.357 に答える