成績統計

Reduce

数値の配列を合計したいとします。 これを実現する方法はたくさんあります。

• 多くのプログラミング言語では、この問題はアキュムレーター変数を使ったループとして表現されます。

• この問題は再帰関数として書くこともできます。 擬似コードでは、次のようになります。

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

  問題をより小さな部分に分割していくこの方法は、「基底ケースに向かってreduceしていく」とも表現できます。

Reduceは、データ構造のすべての要素を1つの値にまとめる方法です。 この処理は、データ構造を繰り返し走査し、各要素に関数を適用して、蓄積された結果を更新します。

jqでは、この処理はreduceフィルターとして実装されています。 他の言語では、"fold"、"fold-left"、"inject"、"aggregate"などと呼ばれることもあります。

jqのreduce式は次のようになります。

reduce STREAM_EXPRESSION as $var (INITIAL_VALUE; UPDATE_EXPRESSION)

• STREAM_EXPRESSIONは項目の_ストリーム_で、それぞれが順番に$var変数に格納されます。
  • 配列をストリーム化するには、イテレーターフィルター.[]を使うことを思い出してください：$myArray | .[]。
• INITIAL_VALUEは、蓄積された結果の初期値です（「アキュムレーター」と呼ばれます）。
• UPDATE_EXPRESSIONは、現在の値（$var）をアキュムレーターに統合します（「畳み込み」ます）。
  • この式の文脈では、.はアキュムレーターの値です。
  • 式の出力は、次の繰り返しで使うためにアキュムレーターに格納されます。
  • 最後の繰り返しのあと、蓄積された結果がreduceの出力になります。

例を見てみましょう。配列の数値を合計します。 addフィルターはまさにこれを行いますが、ここではその実装方法を見ていきます。

入力として[10, 20, 30, 40]を使い、初期状態を0とすると、各ステップは次のようになります。

jqの構文では、次のコードのようになります。

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

これをreduceフィルターで表現できます。

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

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

覚えておきたいこと

• 畳み込みの式では、.はアキュムレーターです。 畳み込み関数の中で参照する必要があるオブジェクトが入力にある場合は、それを変数に格納する必要があります。

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

• アキュムレーターはどんなデータ型でもかまいません。 たとえば、配列を逆順にしたい場合があります。

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