Python - 前缀和算法

Question

Python - 前缀和算法

15

我正在尝试理解前缀和概念，参考Codility的前缀和课程中提供的例子here（蘑菇采摘者问题）。我的理解是，整个概念基于一个简单的属性，即为了找到数组A中两个位置A（pos_left，pos_right）之间所有元素的总和，使用第二个数组P，其中所有元素都被连续求和，并且所搜索的总和计算为
value（P（pos_right + 1））-value（P（pos_left））。

A 1 2 3 4 5  6
P 0 1 3 6 10 15 21
sum of all elements between A[2] and A[5] = 3+ 4 + 5 = 12
or using the prefix sums"   P[5+1] - P[2] = 15 -3 = 12

问题
有一条街道，每个位置都有蘑菇，用非空向量表示。给出采摘者的初始位置和移动范围，寻找可能收集的最大蘑菇数量。

看了这个例子，我不理解循环结构的逻辑。有人能澄清算法的机制吗？

此外，我觉得这个例子中的位置索引非常令人困惑和繁琐。将向量与前缀和移位到开始的零点是常见做法吗？（在Python中，计算向量元素从0开始默认会导致一些混乱）。

解决方案

def prefix_sums(A):
  n = len(A)
  P = [0] * (n + 1)
  for k in xrange(1, n + 1):
      P[k] = P[k - 1] + A[k - 1]
  return P


def count_total(P, x, y):
    return P[y + 1] - P[x]

# A mushroom picker is at spot number k on the road and should perform m moves
def mushrooms(A, k, m):
    n = len(A)
    result = 0
    pref = prefix_sums(A)
    for p in xrange(min(m, k) + 1):   # going left
        left_pos = k - p
        right_pos = min(n - 1, max(k, k + m - 2 * p))
        result = max(result, count_total(pref, left_pos, right_pos))
    for p in xrange(min(m + 1, n - k)):
        right_pos = k + p
        left_pos = max(0, min(k, k - (m - 2 * p)))
        result = max(result, count_total(pref, left_pos, right_pos))
    return result

我已经运行了一个小数组的示例 A=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]，选择位置 k=5 和范围 m=3。我不理解通过两个循环创建检查范围的逻辑。

我得到了以下循环参数：

(p=, left_pos=, right_pos=)   
loop 1  (0,5,8), (1,4,6),(2,3,5),(3,2,5)
loop 2  (0,2,5), (1,4,6), (2,5,7), (3,5,8)

范围不同。为什么？

用于调试的版本

def mushrooms2(A, k, m):
    n = len(A)
    result = 0
    pref = prefix_sums(A)
    l1 =min(m, k) + 1
    print 'loop p in xrange(min(m, k) + 1): %d' % l1
    for p in xrange(min(m, k) + 1):
        print 'p %d' % p
        print 'A= %r' % A
        print 'pref= %r' % pref
        left_pos = k - p
        right_pos = min(n - 1, max(k, k + m - 2 * p))
        result = max(result, count_total(pref, left_pos, right_pos))
        print 'left_pos = k - p= %d' % left_pos
        print 'right_pos= min(n-1,max(k,k+m-2*p))= %d' % right_pos
        print 'max'
        print '(result %d' % result
        print 'count_total(pref, left_pos, right_pos)) %r, %r, %r, %r' % (pref,left_pos, right_pos,count_total(pref, left_pos, right_pos))
        print 'result= %d' % result
        print 'next p'
    l2=min(m + 1, n - k)
    print   'loop xrange(min(m + 1, n - k)): %d' % l2
    for p in xrange(min(m + 1, n - k)):
        print 'p %d' % p
        print 'A= %r' % A
        print 'pref= %r' % pref
        right_pos = k + p
        left_pos = max(0, min(k, k - (m - 2 * p)))
        result = max(result, count_total(pref, left_pos, right_pos))
        print 'right_pos = k + p= %d' % right_pos
        print 'left_pos = max(0, min(k, k - (m - 2 * p)))= %d' % left_pos
        print 'max'
        print '(result %d' % result
        print 'count_total(pref, left_pos, right_pos)) %r, %r, %r, %r' % (pref,left_pos, right_pos,count_total(pref, left_pos, right_pos))
        print 'result= %d' % result
        print 'next p'
    print 'result %d' % result
    return result

- Chris

Python的索引/切片是从零开始的。根据您想要实现的目标，使用计算的“循环变量”来进行切片或索引可能会更有效率。 - wwii

2个回答

2

阅读完该主题后，直到我实施了朴素解决方案（即在Codility文档中的第一个解决方案）之后，才得以理解这个想法，仍然很难理解难以理解的解决方案#2，它简单地模拟向左和向右移动以及所有这些奇怪的计算，只为获得区域的左右极限（就像您真正移动其中一样）。因此，每次迭代意味着使用6步骤的完整循环。

如果您向左移动然后向右移动（P=0…M），则有：

- 0步向左，6步向右（实际上是0步和2步，因为超出了数组边界），因此区域的左边界位于索引4，右边界位于索引6 - 1步向左，5步向右（实际上是1步和3步），因此左边界位于索引3，右边界位于索引6 - 2步向左，4步向右（实际上是2步和4步）......继续计算

这是我的PHP版本，其中包含简化的代码和额外的变量，以便更容易理解。

function prefix_sums(array $a)
{
    $n = count($a);
    $p = array_fill(0, $n + 1, 0);
    for ($i = 1; $i <= $n; $i++) {
        $p[$i] = $p[$i - 1] + $a[$i - 1];
    }
    return $p;
}

function count_total($p, $x, $y)
{
    return $p[$y + 1] - $p[$x];
}

function mushrooms(array $a, int $k, int $m)
{
    $n = count($a) - 1;
    $max = 0;
    $sums = prefix_sums($a);
    //start  moving to the left and then the right
    for ($p = 0; $p < $m; $p++) {
        $stepsLeft = $p;
        $realStepsLeft = min($k, $stepsLeft);
        $leftBorder = $k - $realStepsLeft;

        $stepsRight = $m - $stepsLeft;
        $realStepsRight = min($n - $leftBorder, $stepsRight);
        $rightBorder = $leftBorder + $realStepsRight;

        $max = max($max, count_total($sums, $leftBorder, $rightBorder));
    }
    //moving to the right and then the left
    for ($p = 0; $p < $m; $p++) {
        $stepsRight = $p;
        $realStepsRight = min($p, $n - $k);
        $rightBorder = $k + $realStepsRight;

        $stepsLeft = $m - $stepsRight;
        $realStepsLeft = min(($k + $realStepsRight), $stepsLeft);
        $leftBorder = $rightBorder - $realStepsLeft;

        $max = max($max, count_total($sums, $leftBorder, $rightBorder));
    }
    return $max;
}

assert(ASSERT_EXCEPTION, 1);
assert(mushrooms([2, 3, 7, 5, 1, 3, 9], 4, 6) == 25);

echo 'Success';

- illia permiakov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ilim · Accepted Answer

在考虑循环结构时，你并不孤单，我也花了几分钟时间才理解它。以下是我所理解的内容。

现在，你提供的链接中进一步详细说明了最佳策略是以只改变方向一次的方式沿路径行走。这样，一个人就能够用左右端点覆盖一个范围，而left_pos和right_pos似乎代表着这个范围。

至于循环的细节，与其从循环变量（即p）的角度思考循环，不妨想想循环过程中发生了哪些变化，以及如何使用p。否则，在开始时弄清楚那些min和max表达式中的东西似乎有点奇怪。

例如，在第一个循环中，不要试图弄清楚那个范围代表什么，而是尝试看看不同值的p如何影响left_pos。经过一番思考，人们会注意到left_pos按照可能的左端点发生变化。

具体来说，当p == 0时，左端点是起始索引（即k），当p为min(m，k)时，则为0（即如果k < m）或(k - m)。在前一种情况下，这就是左端点所能到达的最远处，因为它将走出道路上有效范围之外。在后一种情况下，由于移动次数不足，任何小于(k-m)的left_pos都无法得到解决方案，因为无法在m步内从k到达这些索引。

第一个循环中对right_pos的赋值也可以类似地解释。min语句包括(n-1)，它是可以到达的最右侧合法索引，并用于保持右端点在允许的限制范围内。内部max语句包括k，因为它是right_pos可能的最小值。（即由于k是起始点）它还有一个表达式(k + m - 2 * p)。这个表达式表示以下过程：

向左移动p步。
改变方向，向右移动p步以到达起始点。
使用剩余的(m-2p)步向右移动。

第二个循环只是这个第一个循环的镜像，你可以通过调整我对第一个循环的解释来简单地解释它。

至于你的第二个问题，我认为在前缀和数组中不常使用索引位移。我通常在在线编程竞赛中使用这种方法，我的Python实现如下：

def prefix_sums(A):
    n = len(A)
    P = [0] * n
    P[0] = A[0]
    for k in xrange(1, n):
        P[k] = P[k - 1] + A[k]
    return P

def count_total(P, x, y):
    return (P[y] - P[x - 1] if x > 0 else P[y])

上述实现背后的基本思想是，在P[x]处，我们有和为A[0] + A[1] + ... + A[x]。