Python - Präfixsumme Algorithmus

Question

Ich versuche, die Idee hinter dem Präfixsumme Konzept zu begreifen am Beispiel in der Präfixsumme Lektion von Codility here (Der Pilzsammler Problem)

Mein Verständnis präsentiert suchen ist, dass die Das gesamte Konzept basiert auf der einfachen Eigenschaft, dass zum Finden einer Summe aller Elemente zwischen zwei Positionen A (pos_left, pos_right) eines Arrays A ein zweites Array P verwendet wird, bei dem alle Elemente nacheinander summiert werden und die gesuchte Summe als
berechnet wird Wert (P (pos_right + 1)) - Wert (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 

Das Problem
Es ist eine Straße mit Pilze an jedem Ort durch einen nicht leeren Vektor dargestellt. Angesichts der ursprünglichen Position eines Pflückers und seines Bewegungsbereichs wird die maximale Anzahl an zu sammelnden Pilzen gesucht.

Mit Blick auf das Beispiel verstehe ich nicht die Logik hinter der Konstruktion der Schleifen. Kann jemand die Mechanik dieses Algorithmus klären?

Zweitens fand ich die Positionsindexierung in diesem Beispiel sehr verwirrend und umständlich. Ist es üblich, den Vektor mit Präfix-Summen mit der Null am Anfang "zu verschieben"? (Die Tatsache, dass das Zählen von Elementen in Vektoren in Python mit 0 beginnt, führt bereits zu Verwirrung).

Die Lösung

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 

I einige Beispiel für ein kleines Array ausgeführt haben A= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] wählten die Position k = 5 und den Bereich m = 3. Ich verstehe nicht die Logik der Bereiche der Schaffung durch die zwei Schleifen zu überprüfen.

ich die folgenden Parameter für die Schleifen

(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) 

Die rangies variieren. Warum?

Version für das Debuggen

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 

Answer 1

Sie sind nicht allein die Schleife Konstruktion bei der Betrachtung kontraintuitiv sein, da ich auch ein paar Minuten damit verbringen musste. Hier ist, was ich herausgefunden habe.

Nun, die Lösung in der Verknüpfung, die Sie weitere Details zur Verfügung gestellt die optimale Strategie ist auf Pfad so gehen, dass man Richtungen nur einmal ändert. Auf diese Weise kann man einen Bereich mit linken und rechten Endpunkten abdecken, die left_pos und right_pos darzustellen scheinen.

Was die Einzelheiten der Schleifen, anstatt zu denken, der Schleife in Bezug auf die Schleifenvariablen (dh p), ist es leichter, herauszufinden, was den Verlauf der Schleife ändert sich durch, und wie p wird eingesetzt. Ansonsten scheint es zu eigenartig zu sein, herauszufinden, was in diesen minimalen und maximalen Ausdrücken ist.

Zum Beispiel in der ersten Schleife, statt herauszufinden, was dieser Bereich darstellt, versuchen Sie, wie left_pos durch unterschiedliche Werte beeinflusst wird p bekommt. Nach ein wenig Nachdenken fällt auf, dass sich left_pos in einer Weise ändert, die den möglichen linken Endpunkten entspricht.

Insbesondere wenn p 0, linker Endpunkt ist der Ausgangsindex (dh k), und wenn p ist min (m, k), dann ist es entweder 0 (das heißt, wenn k < m) oder (k - m). Im ersteren Fall ist das so weit, wie der linke Endpunkt gehen kann, da er außerhalb des gültigen Bereichs von Punkten auf der Straße liegen würde. Im letzteren Fall verhindert die Anzahl der Züge jede Lösung mit einem kleineren Wert als (k - m), da es unmöglich ist, von k zu diesen Indizes in m Zügen zu gehen.

Die Zuordnung zu right_pos in der ersten Schleife kann ähnlich erklärt werden. Die min-Anweisung enthält (n-1), was der am weitesten rechts erreichbare Index ist, der dazu dient, den rechten Endpunkt in den erlaubten Grenzen zu halten. Die innere max-Anweisung weist k auf, da es der niedrigst mögliche Wert für right_pos ist. (d. h. weil k der Startpunkt ist). Es hat auch einen Ausdruck (k + m - 2 * p). Dieser Ausdruck stellt den folgenden Prozess dar:

• Gehe nach links für p Züge.
• Ändern Sie die Richtung, und gehen Sie für p Bewegungen nach rechts, um den Startpunkt zu erreichen.
• Mit den verbleibenden (m - 2p) Bewegungen nach rechts gehen.

Die zweite Schleife ist nur die Reflexion dieser ersten Schleife, und Sie können es einfach erklären durch meine Erklärung der ersten Schleife anzupassen.

Was Ihre zweite Frage anbelangt, glaube ich nicht, dass es üblich ist, die Indizes für Präfix-Summen-Arrays zu verschieben. Ich verwende diese Methode normalerweise in der Wettbewerbsprogrammierung in Online-Wettbewerben, und meine Implementierung des Präfix-Summen-Arrays, das Sie in Python verwenden, wäre wie folgt.

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] 

Meine Intuition für die Umsetzung oben ist: bei P [x], haben wir die inklusive Summe A [0] + A [1] + ... + A [x].