python - алгоритм суммирования префиксов
Я пытаюсь понять идею, лежащую в основе концепции суммы префикса, глядя на пример, представленный здесь в уроке суммы префиксов по Codility (проблема выбора грибов)
Насколько я понимаю, вся концепция основана на простом свойстве, где для нахождения суммы всех элементов между двумя позициями A(pos_left, pos_right) массива A используется второй массив P, где все элементы последовательно суммируются и где ищется сумма рассчитывается как
значение (P(pos_right + 1)) - значение (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
Эта проблема
В каждом месте есть улица с грибами, представленная непустым вектором. Учитывая начальную позицию сборщика и диапазон его перемещения, ищется максимальное количество собираемых грибов.
Глядя на пример, я не понимаю логику построения циклов. Кто-нибудь может прояснить механику этого алгоритма?
Во-вторых, я обнаружил, что индексация по положению в этом примере очень запутанная и громоздкая. Является ли обычной практикой "сдвигать" вектор с суммой префикса с нуля в начале? (Тот факт, что подсчет элементов в векторах начинается с defualt с 0 в python, уже вызывает некоторую путаницу).
Решение
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
1 ответ
Вы не одиноки, считая конструкцию петли нелогичной, поскольку мне пришлось также потратить на это несколько минут. Вот что я понял.
Теперь, решение, которое вы предоставили по ссылке, более подробно описывает оптимальную стратегию, которая заключается в том, чтобы идти по пути таким образом, что человек меняет направление только один раз. Таким образом, каждый может покрыть диапазон левой и правой конечными точками, которые, кажется, представляют left_pos и right_pos.
Что касается особенностей циклов, то вместо того, чтобы думать о цикле в терминах переменных цикла (т. Е. P), легче выяснить, что меняется в ходе цикла и как используется p. В противном случае, выяснение того, что находится в этих выражениях min и max, поначалу кажется слишком странным.
Например, в первом цикле, вместо того, чтобы выяснить, что представляет этот диапазон, попробуйте, как left_pos зависит от различных значений p. Подумав немного, можно заметить, что left_pos изменяется таким образом, чтобы соответствовать возможным левым конечным точкам.
В частности, когда p равно 0, левая конечная точка является начальным индексом (то есть k), а когда p равно min (m, k), то это либо 0(то есть, если 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]
Моя интуиция для реализации выше: в P[x] у нас есть включающая сумма A[0] + A[1] + ... + A[x].
После прочтения темы все еще было трудно понять идею, пока я не реализовал наивное решение (которое первое в документе 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';