ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

reduce 関数の作成

MapReduce における reduce 関数の役割

mapreduce は、データのチャンクを受け取って中間結果を出力する入力 map 関数と、中間結果を読み取って最終結果を生成する入力 reduce 関数の両方を必要とします。したがって、map 関数および reduce 関数が独立して実行できるように、計算を 2 つの関係する部分に分割するのは自然なことです。たとえば、データセット内の最大値を検索する入力は、map 関数で各データのチャンク内の最大値を検索し、次に reduce 関数で、すべての中間値の最大値から単一の最大値を検索することができます。

次の図に、mapreduce アルゴリズムの Reduce フェーズを示します。

mapreduce アルゴリズムの Reduce フェーズには次のステップがあります。

  1. mapreduce アルゴリズムの Map フェーズの結果は、map 関数で追加されたすべてのキーと値のペアを含む中間 KeyValueStore オブジェクトです。mapreduce は、reduce 関数を呼び出す前に、中間 KeyValueStore オブジェクト内の値を一意なキーでグループ化します。中間 KeyValueStore オブジェクト内の一意なキーごとに、reduce 関数が一度呼び出されます。

  2. mapreduce は、各キーに対して、そのキーに関連付けられる値をすべて含む ValueIterator オブジェクトを作成します。

  3. reduce 関数は、関数 hasnext および getnext を使用して、ValueIterator オブジェクトからの値をスクロールします。これは通常、while ループの中で使用されます。

  4. 要約の計算の実行後、reduce 関数は、関数 add および addmulti を使用して、1 つ以上のキーと値のペアを最終 KeyValueStore オブジェクトに追加します。

mapreduce アルゴリズムの Reduce フェーズは、reduce 関数が一意な中間キーとそれに関連付けられた値をすべて処理した時に完了します。mapreduce アルゴリズムのこのフェーズは、(Map フェーズと同様に) reduce 関数によって追加されたすべてのキーと値のペアを含む KeyValueStore オブジェクトです。Reduce フェーズの後、mapreduce はキーと値のペアを KeyValueStore から引き出して、データ ストア (既定では KeyValueDatastore オブジェクト) に返します。出力データ ストア内のキーと値のペアは、並べ替えられた順序になっていません。reduce 関数が追加した順序のままで表示されます。

reduce 関数の要件

mapreduce は、中間の KeyValueStore オブジェクト内の一意なキーごとに reduce 関数を自動的に呼び出すため、reduce 関数はこの自動呼出しの際に適切に実行できるように、特定の基本的な要件を満たさなければなりません。これらの要件は、mapreduce アルゴリズムの Reduce フェーズ中にデータが適切に移動することを集合的に保証します。

reduce 関数への入力は、intermKeyintermValIter および outKVStore です。

  • intermKey は、map 関数によって追加された一意なキーの 1 つです。mapreduce が reduce 関数を呼び出すたびに、中間の KeyValueStore オブジェクトのキーから新しい一意のキーが指定されます。

  • intermValIter は、アクティブなキー intermKey に関連付けられた ValueIterator オブジェクトです。この ValueIterator オブジェクトには、アクティブなキーに関連付けられたすべての値が含まれます。関数 hasnextgetnext を使用して値をスクロールします。

  • outKVStore は、reduce 関数によってキーと値のペアを追加する必要のある最終的な KeyValueStore オブジェクトの名前です。関数 add および addmulti は、このオブジェクト名を使用して出力にキーと値のペアを追加します。mapreduceoutKVStore から出力のキーと値のペアを取り、出力 datastore に返します。これは既定では KeyValueDatastore オブジェクトです。reduce 関数が outKVStore にキーと値のペアをまったく追加しなかった場合は、mapreduce は空のデータ ストアを返します。

reduce 関数に関するこれらの基本要件に加えて、reduce 関数によって追加されるキーと値のペアも、以下の条件を満たさなければなりません。

  1. キーは数値スカラー、文字ベクトル、または string でなければなりません。数値キーを NaN、論理値、複素数、スパースにすることはできません。

  2. reduce 関数によって追加されるすべてのキーは同じクラスでなければなりませんが、そのクラスは map 関数によって追加されたキーのクラスとは異なっていてもかまいません。

  3. mapreduce の引数 OutputType'Binary' (既定) の場合は、reduce 関数で、有効な MATLAB® データ型を含む任意の MATLAB オブジェクトを追加できます。

  4. mapreduce の引数 OutputType'TabularText' の場合は、reduce 関数で数値スカラー、文字ベクトル、または string を追加できます。この場合、値に NaN、複素数、論理値、スパースは使用できません。

メモ

上記のキーと値のペアの要件は、mapreduce を使用する製品によって異なる場合があります。使用する製品のドキュメンテーションで、キーと値のペアに関する製品固有の要件を確認してください。

reduce 関数の例

以下の例には、toolbox/matlab/demos フォルダーの mapreduce の例で使用される reduce 関数が含まれます。

単純な reduce 関数

リデューサーの最も簡単な例の 1 つに maxArrivalDelayReducer.m があります。これは、サンプル ファイル MaxMapReduceExample.m のリデューサーです。この例の map 関数は、入力データの各チャンクの最大到着遅延時間を検索します。次に、reduce 関数が、すべての中間値の最大値から単一の最大値を見つけることによってタスクを終了します。最大値を検索するために、リデューサーは ValueIterator オブジェクト内の値を確認し、各値を現在の最大値と比較します。マッパーは単一の一意なキーを中間オブジェクト KeyValueStore に追加するため、mapreduce はこのリデューサー関数を一度だけ呼び出します。reduce 関数は、出力にキーと値のペアを 1 つ追加します。

type maxArrivalDelayReducer.m
function maxArrivalDelayReducer(intermKey, intermValIter, outKVStore)
% Reducer function for the MaxMapreduceExample.

% Copyright 2014 The MathWorks, Inc.

% intermKey is 'PartialMaxArrivalDelay'. intermValIter is an iterator of
% all values that has the key 'PartialMaxArrivalDelay'.
maxVal = -inf;
while hasnext(intermValIter)
   maxVal = max(getnext(intermValIter), maxVal);
end
% The key-value pair added to outKVStore will become the output of mapreduce 
add(outKVStore,'MaxArrivalDelay',maxVal);

高度な reduce 関数

より高度なリデューサーの例として、statsByGroupReducer.m があります。これは、サンプル ファイル StatisticsByGroupMapReduceExample.m のリデューサーです。この例の map 関数は、追加のパラメーター (航空会社、月など) を使用して各入力のデータをグループ化し、データのグループごとにいくつかの統計量を計算します。reduce 関数は、統計量を取得してそれらを長いベクトルに連結し、そのベクトルを使用してカウント、平均、分散、傾斜、尖度の最終的な統計量を計算し、タスクを完了します。リデューサーはこれらの値を構造体のフィールドとして格納するため、それぞれの一意のキーは出力に統計量の構造体をもちます。

type statsByGroupReducer.m
function statsByGroupReducer(intermKey, intermValIter, outKVStore)
% Reducer function for the StatisticsByGroupMapReduceExample.

% Copyright 2014 The MathWorks, Inc.

n = [];
m = [];
v = [];
s = [];
k = [];

% get all sets of intermediate statistics
while hasnext(intermValIter)
    value = getnext(intermValIter);
    n = [n; value(1)];
    m = [m; value(2)];
    v = [v; value(3)];
    s = [s; value(4)];
    k = [k; value(5)];
end
% Note that this approach assumes the concatenated intermediate values fit
% in memory. Refer to the reducer function, covarianceReducer,  of the
% CovarianceMapReduceExample for an alternative pairwise reduction approach

% combine the intermediate results
count = sum(n);
meanVal = sum(n.*m)/count;
d = m - meanVal;
variance = (sum(n.*v) + sum(n.*d.^2))/count;
skewnessVal = (sum(n.*s) + sum(n.*d.*(3*v + d.^2)))./(count*variance^(1.5));
kurtosisVal = (sum(n.*k) + sum(n.*d.*(4*s + 6.*v.*d +d.^3)))./(count*variance^2);

outValue = struct('Count',count, 'Mean',meanVal, 'Variance',variance,...
                 'Skewness',skewnessVal, 'Kurtosis',kurtosisVal);

% add results to the output datastore
add(outKVStore,intermKey,outValue);

その他の reduce 関数

map 関数または reduce 関数の一般的なプログラミング パターンについての詳細は、MapReduce での効果的なアルゴリズムの構築を参照してください。

参考

| | | | |

関連するトピック