python - 关于DP的性能讨论

Question

看下面的代码，我用了两种方法来解决这个问题(简单递归和DP)。为什么DP方式比较慢？

你有什么建议？

#!/usr/local/bin/python2.7
# encoding: utf-8

问题:存在一个正整数数组。给定一个正整数 S,\找出数字之和为 S 的组合总数。

方法一:

def find_sum_recursive(number_list, sum_to_find):
    count = 0

    for i in range(len(number_list)):        
        sub_sum = sum_to_find - number_list[i]
        if sub_sum < 0:
            continue
        elif sub_sum == 0:
            count += 1
            continue
        else:            
            sub_list = number_list[i + 1:]            
            count += find_sum_recursive(sub_list, sub_sum)       
    return count

方法二:

def find_sum_DP(number_list, sum_to_find):
    count = 0

    if(0 == sum_to_find):
        count = 1
    elif([] != number_list and sum_to_find > 0):   
        count = find_sum_DP(number_list[:-1], sum_to_find) + find_sum_DP(number_list[:-1], sum_to_find - number_list[:].pop())     

    return count

运行它:

def main(argv=None):  # IGNORE:C0111
    number_list = [5, 5, 10, 3, 2, 9, 8]
    sum_to_find = 15
    input_setup = ';number_list = [5, 5, 10, 3, 2, 9, 8, 7, 6, 4, 3, 2, 9, 5, 4, 7, 2, 8, 3];sum_to_find = 15'

    print 'Calculating...'
    print 'recursive starting'
    count = find_sum_recursive(number_list, sum_to_find)
    print timeit.timeit('count = find_sum_recursive(number_list, sum_to_find)', setup='from __main__ import find_sum_recursive' + input_setup, number=10)
    cProfile.run('find_sum_recursive(' + str(number_list) + ',' + str(sum_to_find) + ')')
    print 'recursive ended:', count    
    print 'DP starting'
    count_DP = find_sum_DP(number_list, sum_to_find)
    print timeit.timeit('count_DP = find_sum_DP(number_list, sum_to_find)', setup='from __main__ import find_sum_DP' + input_setup, number=10)
    cProfile.run('find_sum_DP(' + str(number_list) + ',' + str(sum_to_find) + ')')
    print 'DP ended:', count_DP        
    print 'Finished.'    

if __name__ == '__main__':
    sys.exit(main())

我重新编码了方法二，现在是:

def find_sum_DP(number_list, sum_to_find):
    count = [[0 for i in xrange(0, sum_to_find + 1)] for j in xrange(0, len(number_list) + 1)]    

    for i in range(len(number_list) + 1):
        for j in range(sum_to_find + 1):            
            if (0 == i and 0 == j):                
                count[i][j] = 1            
            elif (i > 0 and j > 0):                
                if (j > number_list[i - 1]):                    
                    count[i][j] = count[i - 1][j] + count[i - 1][j - number_list[i - 1]]
                elif(j < number_list[i - 1]):
                    count[i][j] = count[i - 1][j]
                else:
                    count[i][j] = count[i - 1][j] + 1                                
            else:                
                count[i][j] = 0

    return count[len(number_list)][sum_to_find]

比较方法一和方法二:

Calculating...
recursive starting
0.00998711585999
         92 function calls (63 primitive calls) in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
     30/1    0.000    0.000    0.000    0.000 FindSum.py:18(find_sum_recursive)
       30    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
       30    0.000    0.000    0.000    0.000 {range}


recursive ended: 6
DP starting
0.00171685218811
         15 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 FindSum.py:33(find_sum_DP)
        3    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        9    0.000    0.000    0.000    0.000 {range}


DP ended: 6
Finished.

Answer 1

如果您使用的是 iPython，%prun 是您的 friend 。

看一下递归版本的输出:

         2444 function calls (1631 primitive calls) in 0.002 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    814/1    0.002    0.000    0.002    0.002 <ipython-input-1-7488a6455e38>:1(find_sum_recursive)
      814    0.000    0.000    0.000    0.000 {range}
      814    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.002    0.002 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

现在，对于 DP 版本:

         10608 function calls (3538 primitive calls) in 0.007 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   7071/1    0.007    0.000    0.007    0.007 <ipython-input-15-3535e3ab26eb>:1(find_sum_DP)
     3535    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects}
        1    0.000    0.000    0.007    0.007 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

7071比814高了不少!

这里的问题是您的动态规划方法不是动态规划!动态规划的要点是，当您遇到重叠子问题的问题时，就像您在这里所做的那样，您存储每个子问题的结果，然后当您再次需要结果时，您可以从该存储中获取它而不是重新计算。您的代码不会这样做:每次调用 find_sum_DP 时，您都在重新计算，即使已经完成了相同的计算。结果是你的 _DP 方法实际上不仅是递归的，而且递归的函数调用比你的递归方法更多。

(我目前正在写一个DP版来演示)

编辑:

我需要补充一点，虽然我应该了解更多关于动态规划的知识，但我很尴尬地不知道。我也在深夜快速地写这篇文章，有点像对自己的练习。不过，这里是该函数的动态编程实现:

import numpy as np
def find_sum_realDP( number_list, sum_to_find ):
    memo = np.zeros( (len(number_list),sum_to_find+1) ,dtype=np.int)-1
    # This will store our results. memo[l][n] will give us the result
    # for number_list[0:l+1] and a sum_to_find of n. If it hasn't been
    # calculated yet, it will give us -1. This is not at all efficient
    # storage, but isn't terribly bad.

    # Now that we have that, we'll call the real function. Instead of modifying
    # the list and making copies or views, we'll keep the same list, and keep
    # track of the index we're on (nli).
    return find_sum_realDP_do( number_list, len(number_list)-1, sum_to_find, memo ),memo

def find_sum_realDP_do( number_list, nli, sum_to_find, memo ):
    # Our count is 0 by default.
    ret = 0

    # If we aren't at the sum to find yet, do we have any numbers left after this one?
    if ((sum_to_find > 0) and nli>0):
        # Each of these checks to see if we've already stored the result of the calculation.
        # If so, we use that, if not, we calculate it.
        if memo[nli-1,sum_to_find]>=0:
            ret += memo[nli-1,sum_to_find]
        else:
            ret += find_sum_realDP_do(number_list, nli-1, sum_to_find, memo)

        # This one is a bit tricky, and was a bug when I first wrote it. We don't want to
        # have a negative sum_to_find, because that will be very bad; we'll start using results
        # from other places in memo because it will wrap around.
        if (sum_to_find-number_list[nli]>=0) and memo[nli-1,sum_to_find-number_list[nli]]>=0:
            ret += memo[nli-1,sum_to_find-number_list[nli]]
        elif (sum_to_find-number_list[nli]>=0):
            ret += find_sum_realDP_do(number_list, nli-1, sum_to_find-number_list[nli], memo)

    # Do we not actually have any sum to find left?     
    elif (0 == sum_to_find):
        ret = 1

    # If we only have one number left, will it get us there?
    elif (nli == 0) and (sum_to_find-number_list[nli] == 0 ):
        ret = 1

    # Store our result.
    memo[nli,sum_to_find] = ret

    # Return our result.
    return ret        

请注意，这使用了 numpy .您很可能没有安装它，但我不确定没有它如何在 Python 中编写性能合理的动态编程算法；我认为 Python 列表的性能远不及 Numpy 数组。另请注意，这与您的代码处理零的方式不同，因此与其调试它，我只想说这段代码适用于数字列表中的非零正整数。现在，使用这个算法，分析给我们:

         243 function calls (7 primitive calls) in 0.001 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    237/1    0.001    0.000    0.001    0.001 <ipython-input-155-4a624e5a99b7>:9(find_sum_realDP_do)
        1    0.000    0.000    0.001    0.001 <ipython-input-155-4a624e5a99b7>:1(find_sum_realDP)
        1    0.000    0.000    0.000    0.000 {numpy.core.multiarray.zeros}
        1    0.000    0.000    0.001    0.001 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

243 甚至比递归版本要好得多!但是您的示例数据足够小，无法真正显示动态规划算法有多好。

让我们试试 nlist2 = [7, 6, 2, 3, 7, 7, 2, 7, 4, 2, 4, 5, 6, 1, 7, 4, 6, 3, 2, 1 , 1, 1, 4,
2, 3, 5, 2, 4, 4, 2, 4, 5, 4, 2, 1, 7, 6, 6, 1, 5, 4, 5, 3, 2, 3, 7,
1, 7, 6, 6]，具有相同的 sum_to_find=15。这有 50 个值，以及 900206 种方法来获得 15...

使用find_sum_recursive:

         3335462 function calls (2223643 primitive calls) in 14.137 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1111820/1   13.608    0.000   14.137   14.137 <ipython-input-46-7488a6455e38>:1(find_sum_recursive)
  1111820    0.422    0.000    0.422    0.000 {range}
  1111820    0.108    0.000    0.108    0.000 {len}
        1    0.000    0.000   14.137   14.137 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

现在使用 find_sum_realDP:

         736 function calls (7 primitive calls) in 0.007 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    730/1    0.007    0.000    0.007    0.007 <ipython-input-155-4a624e5a99b7>:9(find_sum_realDP_do)
        1    0.000    0.000    0.007    0.007 <ipython-input-155-4a624e5a99b7>:1(find_sum_realDP)
        1    0.000    0.000    0.000    0.000 {numpy.core.multiarray.zeros}
        1    0.000    0.000    0.007    0.007 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

所以我们的调用次数不到 1/1000，运行时间不到 1/2000。当然，您使用的列表越大，DP 算法的效果就越好。在我的电脑上，sum_to_find 为 15 和从 1 到 8 的 600 个随机数列表运行，realDP 只需要 0.09 秒，函数调用不到 10,000 次；正是在这一点上，我使用的 64 位整数开始溢出，我们遇到了各种其他问题。不用说，在计算机停止运行之前，递归算法永远无法处理接近该大小的列表，无论是内部 Material 分解还是宇宙热寂。