Verstehen Sie nicht Effizienz ist anders in FoldLeft und FoldRight in Scala

Question

Lesen Sie den folgenden Absatz in der Programmierung in Scala, 2nd Edition, die für mich keinen Sinn ergab.

def flattenLeft[T](xss: List[List[T]]) = 
    (List[T]() /: xss) (_ ::: _) 

def flattenRight[T](xss: List[List[T]]) = 
    (xss :\ List[T]()) (_ ::: _) 

Weil Liste Verkettung, xs ::: ys, Zeit proportional zu seinem ersten Argumente xs nimmt, ist die Umsetzung in der Falte rechts in flattenRight effizienter als die Falte links Umsetzung in flattenLeft. Das Problem ist, dass flattenLeft (xss) kopiert die erste Elementliste xss.head n - 1 mal, wobei n die Länge der Liste ist xss

Wenn also Liste Verkettungszeit proportional zu seiner ersten nimmt Argument, wäre das nicht flattenLeft ist der effizientere, da das erste Argument eine leere Liste ist und flattenRight das erste Argument ist eine Liste unbekannter Länge?

Answer 1

Das erste Argument zu foldLeft ist nur eine leere List am Anfang, das heißt, die zero für diese Falte.

Wie Sie alle List s auf eine List falten, baut sich der Zwischen fold Listen mit dem Teilergebnis auf jeder Verkettung, die dann als Argument für den nächsten Verkettung verwendet wird. Dieses Zwischenergebnis wird immer größer. Auf einem foldLeft, wird dies das erste Argument sein:

def flattenLeft[T](xss: List[List[T]]) = 
    (List[T]() /: xss) ((acc, xs) => acc ::: xs) 
         //^ this one 

Im Gegenteil, für ein foldRight Sie das Ergebnis von rechts bauen, die das Zwischenergebnis bedeutet (denjenigen, der wächst) die richtige ist, die wird das zweite Argument

def flattenRight[T](xss: List[List[T]]) = 
    (xss :\ List[T]()) ((xs, acc) => xs ::: acc) 
          //^ this one gets bigger now 

so zur Verkettungsoperation sein, wird ein flattenRight weniger Zeit in Anspruch nehmen, da das erste Argument nicht verketten nicht wachsen, wie Sie Fortschritte.

Answer 2

die Listen Abflachen durch von links verläuft Faltung als

[ [....] [....] [....] [....] [....] ] 
    [....] 
    [...........] 
    [..................] 
    [.........................] 
    [................................] 

und von rechts als

[ [....] [....] [....] [....] [....] ] 
           [....] 
         [...........] 
       [..................] 
     [.........................] 
    [................................] 

Wenn n Listen von links Falzen, jedes Element in der ersten Liste ist, verfolgt über (n-1) mal; in der zweiten Liste (n-2) mal, usw. Dies ist klassisches quadratisches Verhalten.

Beim Falten von rechts wird jedes Element über genau einmal verfolgt, für das lineare Verhalten des Gesamtbetriebs.