あらまし
技術論文や教育用資料においてアルゴリズムを説明するときに、しばしば疑似コードを示します。
Map、Filter、Reduceを疑似コードでどう書いたらよいのだろう、と悩む人へ。
結論を先に言うと下記です。
- MapやFilterはリスト内包表記(集合内包表記)で書く。
- Reduceは、LaTeXで言うところの大きな記号を使って書く。
Map
具体例があると話がイメージしやすいので、下記のようなPythonのコードについて考えます。
関数square_setは、mapとlambdaを使って、リストintsの各要素を2乗したリストを求める例です。
これは、関数square_set2のように、リスト内包表記で書けます。
このように、mapとlambdaのプログラムはリスト内包表記で書けることが多いです。
def square_set(ints):
return map(lambda i: i ** 2, ints)
def square_set2(ints):
return [i ** 2 for i in ints]
それなら、疑似コードでも、リスト内包表記(集合内包表記)で書けばよいのです。
疑似コード例は下記です。
原始的な書き方よりも、内包表記による書き方の方がわかりやすいですね。
同様に、Filterもリスト内包表記で書けばよいです。
Reduce
reduceの具体例は下記のPythonコードです。
mapのときにやったsquare_setを実行してその結果を全部加算するようなプログラムです。
addをreduceすることで、リストの要素を加算しています。
加算ならPythonにはsumがあるじゃん。というツッコミはごもっともです。
イメージしやすい例として出したものです。
一般にはaddのところには、とにかく何らかの2項演算が入ります。
sum_of_square_setとsum_of_square_set2の違いは、mapで書いたかリスト内包表記で書いたかだけです。
from functools import reduce
from operator import add
def sum_of_square_set(ints):
return reduce(add, map(lambda i: i ** 2, ints), 0)
def sum_of_square_set2(ints):
return reduce(add, [i ** 2 for i in ints], 0)
何らかの2項演算をreduceするというところがポイントです。
すると、疑似コードでは、LaTeXで言うところの2項演算の大きな記号で書けばよいです。
疑似コード例は下記です。
原始的な書き方よりも、大きな記号による書き方の方がすっきりですね。
もし2項演算のところが一般的な演算ではなくて自前のPythonコードで用意したものなど特殊な演算なら、それを表す大きな記号の表記を論文中で別途定義して、それを擬似コードで使えばよいでしょう。
