Notenstatistik

Reduzieren

Angenommen, wir möchten ein Array von Zahlen summieren. Es gibt viele Möglichkeiten, dieses Ziel zu erreichen.

• In vielen Sprachen drückt man dieses Problem als Schleife mit einer Akkumulatorvariable aus.

• Man kann dieses Problem als rekursive Funktion schreiben. In Pseudocode könnte das so aussehen.

  function Add(X, Sum=0):
    if X is empty then
      return Sum
    else
      return Add(rest(X), Sum + first(X))
    end
  end
  

  Diese Methode, das Problem in kleinere Teile zu zerlegen, kann man auch als „Reduzieren auf den Basisfall“ beschreiben.

Reduzieren ist eine Möglichkeit, alle Elemente einer Datenstruktur zu einem einzigen Wert zusammenzufassen. Der Prozess iteriert über die Datenstruktur und wendet auf jedes Element eine Funktion an, um das akkumulierte Ergebnis zu aktualisieren.

In jq ist dieser Prozess im reduce-Filter implementiert. In anderen Sprachen wird es vielleicht „fold“, „fold-left“, „inject“ oder „aggregate“ genannt.

Der reduce-Ausdruck in jq sieht so aus.

reduce STREAM_EXPRESSION as $var (INITIAL_VALUE; UPDATE_EXPRESSION)

• STREAM_EXPRESSION ist ein Stream von Elementen, die nacheinander in der Variable $var gespeichert werden.
  • Zur Erinnerung: Um ein Array zu streamen, verwendest du den Iterator-Filter .[]: $myArray | .[].
• INITIAL_VALUE ist der Startwert des akkumulierten Ergebnisses (bekannt als der „Akkumulator“).
• Der UPDATE_EXPRESSION kombiniert („faltet“) den aktuellen Wert ($var) in den Akkumulator.
  • Im Kontext dieses Ausdrucks ist . der Wert des Akkumulators.
  • Die Ausgabe des Ausdrucks wird für die nächste Iteration im Akkumulator gespeichert.
  • Nach der letzten Iteration ist das akkumulierte Ergebnis die Ausgabe von reduce.

Schauen wir uns ein Beispiel an: die Zahlen in einem Array addieren. Der Filter add macht genau das, aber wir werden sehen, wie man ihn implementiert.

Wenn wir [10, 20, 30, 40] als Eingabe verwenden und null als Anfangszustand nehmen, sieht jeder Schritt so aus.

In der jq-Syntax sieht das wie dieser Code aus.

0 + 10 | . + 20 | . + 30 | . + 40

Wir können das mit dem reduce-Filter ausdrücken.

[10, 20, 30, 40] | reduce .[] as $n (0; . + $n)     # => 100

def add: reduce .[] as $x (null; . + $x);

Ein paar Dinge, die du beachten solltest

• Im reduzierenden Ausdruck ist . der Akkumulator. Wenn die Eingabe ein Objekt ist, auf das du innerhalb der reduzierenden Funktion verweisen musst, musst du es in einer Variable speichern.

  {"apple": 10, "banana": 16, "carrot": 4}
  | . as $obj
  | reduce (keys | .[]) as $key (0; . + $obj[$key])     # => 30
  

• Der Akkumulator kann von jedem Datentyp sein. Zum Beispiel möchtest du vielleicht ein Array umkehren.

  ["A", "B", "C", "D"]
  | reduce .[] as $elem ([]; [$elem] + .)       # => ["D", "C", "B", "A"]