リストの合計をとるときは、アキュムレータ（memo）を指定してから、リストをウォークスルーし、各要素とアキュムレータに2進関数「x+y」を適用します。手順的には、これは次のようになります。
def mySum(list):
memo = 0
for e in list:
memo = memo + e
return memo
これは一般的なパターンであり、合計をとる以外の場合に役立ちます。これを任意のバイナリ関数に一般化して、パラメーターとして提供し、呼び出し元に初期値を指定させることもできます。reduceこれにより、、、foldlまたはinject[1]として知られる関数が得られます。
def myReduce(function, list, initial):
memo = initial
for e in list:
memo = function(memo, e)
return memo
def mySum(list):
return myReduce(lambda memo, e: memo + e, list, 0)
Python 2ではreduce組み込み関数でしたが、Python3ではfunctools次のモジュールに移動されました。
from functools import reduce
reduce最初の引数として提供する関数に応じて、あらゆる種類のクールな処理を実行できます。「sum」を「listconcatenation」に置き換え、「zero」を「empty list」に置き換えると、（浅い）copy関数が得られます。
def myCopy(list):
return reduce(lambda memo, e: memo + [e], list, [])
myCopy(range(10))
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
transformに別のパラメーターとして関数を追加し、copy連結する前にそれを適用すると、次のようになりますmap。
def myMap(transform, list):
return reduce(lambda memo, e: memo + [transform(e)], list, [])
myMap(lambda x: x*2, range(10))
> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
predicateパラメータとしてブール値を返す関数を追加し、eそれを使用して連結するかどうかを決定すると、次のようになりますfilter。
def myFilter(predicate, list):
return reduce(lambda memo, e: memo + [e] if predicate(e) else memo, list, [])
myFilter(lambda x: x%2==0, range(10))
> [0, 2, 4, 6, 8]
mapとfilterは、リスト内包表記を書くための一種の不気味な方法[x*2 for x in range(10)]です[x for x in range(10) if x%2==0]。に対応するリスト内包構文はありません。これは、リストを返す必要がまったくないreduceためです（前述のように、Pythonも組み込み関数として提供します）。reducesum
ランニングサムを計算するためのリスト作成機能はreduce、まさに私たちが望んでいるものであり、この問題を解決するためのおそらく最もエレガントな方法lambdaです。そのバージョンはreduce、実行時に古い値のコピーを残す、reductionsまたはscanl[1]と呼ばれ、次のようになります。
def reductions(function, list, initial):
return reduce(lambda memo, e: memo + [function(memo[-1], e)], list, [initial])
装備が整ったので、次のように定義できます。
def running_sum(list):
first, rest = list[0], list[1:]
return reductions(lambda memo, e: memo + e, rest, first)
running_sum(range(10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
概念的にはエレガントですが、この正確なアプローチは、Pythonでは実際にはうまくいきません。Pythonlist.append()はリストをその場で変更しますが、それを返さないため、ラムダで効果的に使用することはできず、+代わりに演算子を使用する必要があります。これにより、まったく新しいリストが作成されます。これには、これまでに蓄積されたリストの長さに比例した時間がかかります（つまり、O（n）操作）。forこれを行うときのO（n）ループ内にすでにいるためreduce、全体的な時間計算量はO（n 2）になります。
Ruby [2]のような言語でarray.push eは、変異を返しますがarray、同等の言語はO（n）時間で実行されます。
class Array
def reductions(initial, &proc)
self.reduce [initial] do |memo, e|
memo.push proc.call(memo.last, e)
end
end
end
def running_sum(enumerable)
first, rest = enumerable.first, enumerable.drop(1)
rest.reductions(first, &:+)
end
running_sum (0...10)
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
JavaScript [2]でも同じですが、そのarray.push(e)戻り値e（ではありませんarray）ですが、無名関数を使用して複数のステートメントを含めることができます。これを使用して、戻り値を個別に指定できます。
function reductions(array, callback, initial) {
return array.reduce(function(memo, e) {
memo.push(callback(memo[memo.length - 1], e));
return memo;
}, [initial]);
}
function runningSum(array) {
var first = array[0], rest = array.slice(1);
return reductions(rest, function(memo, e) {
return x + y;
}, first);
}
function range(start, end) {
return(Array.apply(null, Array(end-start)).map(function(e, i) {
return start + i;
}
}
runningSum(range(0, 10));
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
では、ランニングサム関数を作成するためにreductions渡す関数の概念的な単純さを維持しながら、これをどのように解決できるでしょうか。手続き的にlambda x, y: x + y書き直してみましょう。誤って二次reductions問題を修正することができます。問題が発生している間は、ヒープのスラッシングを回避するために結果リストを事前に割り当ててください[3]：
def reductions(function, list, initial):
result = [None] * len(list)
result[0] = initial
for i in range(len(list)):
result[i] = function(result[i-1], list[i])
return result
def running_sum(list):
first, rest = list[0], list[1:]
return reductions(lambda memo, e: memo + e, rest, first)
running_sum(range(0,10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
これは私にとってのスイートスポットです。O（n）パフォーマンスであり、最適化された手続き型コードは意味のある名前で隠されており、次に中間値をリストに累積する関数を作成する必要があるときに再利用できます。
- 名前は
reduce/ reductionsLISPの伝統、foldl/ scanlMLの伝統、およびinjectSmalltalkの伝統に由来します。
- Python
ListとRubyArrayはどちらも、「動的配列」（またはstd::vectorC ++）と呼ばれる自動的にサイズ変更されるデータ構造の実装です。JavaScriptArrayはもう少しバロック的ですが、範囲外のインデックスに割り当てたり、変更したりしない限り、同じように動作しますArray.length。
- Pythonランタイムでリストのバッキングストアを形成する動的配列は、リストの長さが2の累乗を超えるたびにサイズを変更します。リストのサイズ変更とは、古いリストの2倍のサイズのヒープに新しいリストを割り当て、古いリストの内容を新しいリストにコピーし、古いリストのメモリをシステムに戻すことを意味します。これはO（n）演算ですが、リストが大きくなるにつれて発生する頻度が少なくなるため、平均的な場合、リストに追加する時間の複雑さはO（1）になります。ただし、古いリストに残された「穴」は、ヒープ内の位置によっては、リサイクルが難しい場合があります。ガベージコレクションと堅牢なメモリアロケータを使用しても、既知のサイズの配列を事前に割り当てることで、基盤となるシステムの作業を節約できます。