4

私はアルゴリズムの紹介を読んでいて、本の練習を終わらせようとしています。

演習 4.1-3 で

4.1-3 最大部分配列問題のブルート フォース アルゴリズムと再帰アルゴリズムの両方を自分のコンピューターに実装します。どの問題サイズ n0 が、再帰アルゴリズムがブルート フォース アルゴリズムに勝るクロスオーバー ポイントを与えるか? 次に、再帰アルゴリズムの基本ケースを変更して、問題のサイズが n0 未満の場合は常にブルート フォース アルゴリズムを使用します。それはクロスオーバーポイントを変更しますか？

本の疑似コードに従って、2 つのアルゴリズムを作成しました。ただし、Theta(n*lgn) になるように設計され、より高速に実行されるはずの 2 番目のコードは、常に最初の Theta(n**2) よりも遅く実行されるため、私のコードには何か問題があるはずです。私のコードを以下に示します。

def find_maximum_subarray_bf(a): ブルート フォースの #bf
    p1 = 0
    l = 0 # 左の l
    r = 0 # r は右
    最大合計 = 0
    範囲内の p1 の場合 (len(a)-1):
        サブ合計 = 0
        範囲内の p2 の場合 (p1, len(a)):
            sub_sum += a[p2]
            sub_sum > max_sum の場合:
                max_sum = sub_sum
                l = p1
                r = p2
    l、r、max_sumを返す

def find_maximum_subarray_dc(a): 分割統治の #dc

    # サブ機能
    # 指定された配列と、配列を a[l:m] に分割できる 3 つの指標
    # と a[m+1:r] の場合、l \leq i \less m \less j \leq r" である部分配列 a[i:j] を見つけます。
    # 上記の定義によれば、対象の部分配列は
    # 2 つの部分配列 a[i:m] と a[m+1:j] で結合
    # 成長率: theta(n)

    def find_crossing_max(a、l、r、m):

        ＃ 左側
        # ls_r と ls_l は、左部分配列の右境界と左境界を示します。
        # l_max_sum は左部分配列の最大合計を示します
        # sub_sum は、現在計算中のサブ配列の合計を示します      
        ls_l = 0
        ls_r = m-1
        l_max_sum = なし
        サブ合計 = 0
        for j in range(m+1)[::-1]: # 要素を右から左に追加
            sub_sum += a[j]
            sub_sum > l_max_sum の場合:
                l_max_sum = sub_sum
                ls_l = j

        ＃ 右側
        # rs_r と rs_l は、左部分配列の右境界と左境界を示します。
        # r_max_sum は、左部分配列の最大合計を示します
        # sub_sum は、現在計算中のサブ配列の合計を示します                
        rs_l = m+1
        rs_r = 0
        r_max_sum = なし
        サブ合計 = 0
        範囲内の j の場合 (m+1,len(a)):
            sub_sum += a[j]
            sub_sum > r_max_sum の場合:
                r_max_sum = sub_sum
                rs_r = j

        ＃混ぜる
        return (ls_l, rs_r, l_max_sum+r_max_sum)

    # サブ機能
    # 成長率: theta(nlgn) のはずですが、何か問題があります
    def recursion(a,l,r): # T(n)
        r == l の場合:
            リターン (l,r,a[l])
        そうしないと：
            m = (l+r)//2 # シータ(1)
            左 = 再帰 (a、l、m) # T(n/2)
            右 = 再帰(a,m+1,r) # T(n/2)
            交差 = find_crossing_max(a,l,r,m) # theta(n)

            左[2]>=右[2]および左[2]>=交差[2]の場合:
                左に戻る
            elif right[2]>=left[2] and right[2]>=crossing[2]:
                右に戻る
            そうしないと：
                帰りの交差点

    #マスター機能に戻る
    l = 0
    r = len(a)-1
    return recursion(a,l,r)

if __name__ == "__main__":

    from time インポート時間

    a = [100,-10,1,2,-1,4,-6,2,5]
    *= 2**10

    time0 = 時間()
    find_maximum_subarray_bf(a)
    time1 = 時間()
    find_maximum_subarray_dc(a)
    time2 = 時間()
    印刷「機能1:」、time1-time0
    print "関数 2:", time2-time1
    print "ratio:", (time1-time0)/(time2-time1)
4

1 に答える 1

5

まず、ブルートフォースの間違い：

for p1 in range(len(a)-1):

それはrange(len(a))[またはxrange]である必要があります。そのままでは、の最大部分配列が見つかりません[-12,10]。

さて、再帰：

def find_crossing_max(a, l, r, m):

    # left side
    # ls_r and ls_l indicate the right and left bound of the left subarray.
    # l_max_sum indicates the max sum of the left subarray
    # sub_sum indicates the sum of the current computing subarray      
    ls_l = 0
    ls_r = m-1
    l_max_sum = None
    sub_sum = 0
    for j in range(m+1)[::-1]:      # adding elements from right to left

すべてのインデックスを 0 にチェックしていますが、インデックスのみをチェックする必要がありますl。rangeリストを作成して逆にする代わりに、xrange(m,l-1,-1)

        sub_sum += a[j]
        if sub_sum > l_max_sum:
            l_max_sum = sub_sum
            ls_l = j

右側の合計については、アナログが成り立つため、 へのインデックスのみをチェックする必要がrあるため、xrange(m+1,r+1).

さらに、合計の初期値。最大部分配列のインデックスは、左部分では疑わしく、右部分では間違っています。

左の部分については、空の合計から始めますが、 を含める必要がありますa[m]。これl_max_sum = Noneは、最初に設定するか、 index を設定して省略さl_max_sum = a[m]せることで実行できます。いずれにせよ、 の初期値は であってはならず、 であってはなりません。である必要があり、の初期値が であるかのように開始し、で開始するかのように開始する必要があります。jmls_l0ls_rm-1ls_rmls_lm+1l_max_sumNoneml_max_suma[m]

右の部分はr_max_sum0 から開始する必要があり、次のように開始する必要がありrs_rますm(これはそれほど重要ではありませんが、間違ったインデックスが返されるだけです)。右側の合計が負でない場合、右側の合計は0負の合計の最大ではなく、最大である必要があります。

ではrecursion、少し重複しています

left = recursion(a,l,m)         # T(n/2)

を含む合計a[m]は、 ですでに処理またはメジャー化されているfind_crossing_maxため、

left = recursion(a,l,m-1)

r < lしかし、その場合はの可能性も扱わなければならずrecursion、繰り返しは少ないので、そのままにしておきます。

では常にリスト全体をトラバースするため、これは timesfind_crossing_maxと呼ばれO(n)ます。分割統治の実装も実際にはO(n²)そうです。

チェックインされた範囲find_crossing_maxが に制限されて[l,r]いる場合は、そうあるべきですが、長さ の範囲で (およそ)の2^k呼び出しがあり、総コストはです。n/2^k0 <= k <= log_2 nO(n*log n)

これらの変更 (およびいくつかのランダムな配列の生成) により、

def find_maximum_subarray_bf(a):        #bf for brute force
    p1 = 0
    l = 0           # l for left
    r = 0           # r for right
    max_sum = 0
    for p1 in xrange(len(a)):
        sub_sum = 0
        for p2 in xrange(p1, len(a)):
            sub_sum += a[p2]
            if sub_sum > max_sum:
                max_sum  = sub_sum
                l = p1
                r = p2
    return l, r, max_sum

def find_maximum_subarray_dc(a):        #dc for divide and conquer

    # subfunction
    # given an arrary and three indices which can split the array into a[l:m]
    # and a[m+1:r], find out a subarray a[i:j] where l \leq i \less m \less j \leq r".
    # according to the definition above, the target subarray must
    # be combined by two subarray, a[i:m] and a[m+1:j]
    # Growing Rate: theta(n)

    def find_crossing_max(a, l, r, m):

        # left side
        # ls_r and ls_l indicate the right and left bound of the left subarray.
        # l_max_sum indicates the max sum of the left subarray
        # sub_sum indicates the sum of the current computing subarray      
        ls_l = m+1
        ls_r = m
        l_max_sum = None
        sub_sum = 0
        for j in xrange(m,l-1,-1):      # adding elements from right to left
            sub_sum += a[j]
            if sub_sum > l_max_sum:
                l_max_sum = sub_sum
                ls_l = j

        # right side
        # rs_r and rs_l indicate the right and left bound of the left subarray.
        # r_max_sum indicates the max sum of the left subarray
        # sub_sum indicates the sum of the current computing subarray                
        rs_l = m+1
        rs_r = m
        r_max_sum = 0
        sub_sum = 0
        for j in range(m+1,r+1):
            sub_sum += a[j]
            if sub_sum > r_max_sum:
                r_max_sum = sub_sum
                rs_r = j

        #combine
        return (ls_l, rs_r, l_max_sum+r_max_sum)

    # subfunction
    # Growing Rate:  theta(nlgn)
    def recursion(a,l,r):           # T(n)
        if r == l:
            return (l,r,a[l])
        else:
            m = (l+r)//2                    # theta(1)
            left = recursion(a,l,m)         # T(n/2)
            right = recursion(a,m+1,r)      # T(n/2)
            crossing = find_crossing_max(a,l,r,m)   # theta(r-l+1)

            if left[2]>=right[2] and left[2]>=crossing[2]:
                return left
            elif right[2]>=left[2] and right[2]>=crossing[2]:
                return right
            else:
                return crossing

    #back to master function
    l = 0
    r = len(a)-1
    return recursion(a,l,r)

if __name__ == "__main__":

    from time import time
    from sys import argv
    from random import randint
    alen = 100
    if len(argv) > 1:
        alen = int(argv[1])
    a = [randint(-100,100) for i in xrange(alen)]

    time0 = time()
    print find_maximum_subarray_bf(a)
    time1 = time()
    print find_maximum_subarray_dc(a)
    time2 = time()
    print "function 1:", time1-time0
    print "function 2:", time2-time1 
    print "ratio:", (time1-time0)/(time2-time1)

期待どおりの結果が得られます。

$ python subarrays.py 50
(3, 48, 1131)
(3, 48, 1131)
function 1: 0.000184059143066
function 2: 0.00020382
ratio: 0.902923976608
$ python subarrays.py 100
(29, 61, 429)
(29, 61, 429)
function 1: 0.000745058059692
function 2: 0.000561952590942
ratio: 1.32583792957
$ python subarrays.py 500
(35, 350, 3049)
(35, 350, 3049)
function 1: 0.0115859508514
function 2: 0.00170588493347
ratio: 6.79175401817
$ python subarrays.py 1000
(313, 572, 3585)
(313, 572, 3585)
function 1: 0.0537149906158
function 2: 0.00334000587463
ratio: 16.082304233
$ python osubarrays.py 10000
(901, 2055, 4441)
(901, 2055, 4441)
function 1: 4.20316505432
function 2: 0.0381460189819
ratio: 110.186204655
于 2012-12-09T20:42:25.490 に答える