pythonのmap, reduce, filterが好き。階乗計算してみるよ

2017年3月12日

※ダラダラ長文書いているので注意

pythonにあるmap関数とreduce関数が好き。

def f1(x):
    return x * x * x


def f2(x, y):
    return x - y


def f3(x):
    return x % 2 == 0


print map(f1, [1, 2, 3, 4, 5])
print [f1(1), f1(2), f1(3), f1(4), f1(5)]
#=> [1, 2^3, 3^3, 4^3, 5^3] = [1, 8, 27, 64, 125]

print map(f2, [1, 2, 3, 4, 5], [2, 3, 1, 4, 5])
print [f2(1, 2), f2(2, 3), f2(3, 1), f2(4, 4), f2(5, 5)]
#=> [-1, -1, 2, 0, 0]

print reduce(f2, [1, 2, 3, 4, 5])
print f2(f2(f2(f2(1, 2), 3), 4), 5)
#=> ((((1-2) - 3) - 4) - 5) = -13

print filter(f3, [1, 2, 3, 4, 5])
print [x for x in [1, 2, 3, 4, 5] if f3(x)]
#=> [False, True, False, True, False] => [2, 4]

reduceは3つ目の引数をオプションに取る。

def f2(x, y):
    return x - y

print reduce(f2, [1, 2, 3, 4, 5])
print f2(f2(f2(f2(1, 2), 3), 4), 5)
#=>  ((((1-2) - 3) - 4) - 5) = -13

print reduce(f2, [1, 2, 3, 4, 5], -6)
print f2(f2(f2(f2(f2(-6, 1), 2), 3), 4), 5)
#=>  (((((-6-1)-2) - 3) - 4) - 5) = -21

print reduce(f2, [1, 2, 3, 4, 5], 7)
print f2(f2(f2(f2(f2(7, 1), 2), 3), 4), 5)
#=>  (((((7-1)-2) - 3) - 4) - 5) = -8

こんな感じで、最初の引数として3つ目のオプションが入るので、初期値与えたい時に使える…。
2. Built-in Functions — Python v2.7.3 documentationここのドキュメントに載ってるコードを見ると、3つ目に引数を与える場合、本質的には以下と同じようなことをやっているみたいですね。

def myreduce(function, lists, initializer):
    accum_value = initializer
    for x in lists:
        accum_value = function(accum_value, x)
    return accum_value

だから3つ目は初期値みたいな感じっぽい。

map, reduce, filterはここまでで、こっから先はもはや階乗をグダグダ書いているだけなので悪しからずです…
何で急にこんなコードを書いてみたのかというとTSpython 発言さんの記事をみたから。ここでpythonの階乗計算をしているんですが、「pythonで階乗計算」と聞いて、自分が最初に思いついたコード2つがかかれていなかったから。
まず一番最初に思いついたコードがコレ。

import math
print math.factorial(10)

そんなアホな!って感じだけど、やっぱりライブラリにあるならありがたく利用するのが基本ですもんね。自分で書くよりライブラリを利用したほうが大抵良いコードになりますしね。

2つめに思いついていたのがコレ

def fact1(n):
    return reduce(lambda x, y: x*y, xrange(1, n+1), 1)

print fact1(10), fact1(0)

自分はreduce関数を使いたいなぁと真っ先に思ったんですが、さっきのサイトに載ってなかったの。0の階乗って1なので、0!=1を作るために3つ目のオプション使ってます。この場合は、マイナスの値突っ込んだ場合も0突っ込んだ場合もリストは空リストになりますよね。

さきほどの

def myreduce(function, lists, initializer):
    accum_value = initializer
    for x in lists:
        accum_value = function(accum_value, x)
    return accum_value

をみてみると、空リストだとfor分は実行されないですから、accum_value=initializerで入った値のままreturnされる。 だから、マイナス入れた時も0入れた時も1が返りますね。

あと階乗だと、例えば

def fact2(n):
    return 1 if n == 0 else n*fact2(n-1)

print fact2(10), fact2(0)

こんなのとかもどうだろう…マイナス入れた時は、呼ばれ続けちゃう感じですが。やってることは、さきほどのリンクにある

def fact2_other(n):
    if n == 0:
        return 1
    else:
        return n * fact2_other(n-1)

これと一緒なんですけど、コレを一行で書くとこうなる感じです…。

これはCやC++でいう

unsigned int fact2(unsigned int n) {
    return n == 0 ? 1 : n * fact2(n - 1)
}

みたいに三項演算子使った時と同じ挙動をさせてるんですけど、なんかpythonに同じ事させようとすると、条件式部分が真ん中にあって読みにくくて好きじゃないなぁ。 この3項的なノリのif elseを使うって意味だと、

def fact3(x,init=1):
    return fact3(x-1, init*x) if x else init

こんなのも面白いかもしれない。関数の引数を2つにしちゃって、第二引数の方で計算していっちゃうみたいな。 あと、このコードの場合だと

def fact4(n):
    return n == 0 and 1 or n * fact4(n-1)

コレとかもいけるかな・・・? このand,orはpythonで三項演算っぽい挙動をさせたい時によくやられていたらしいです。 自分だったらこんなわかりにくいコード書いてくる人のソース読みたくないけどなぁ…w andとorの挙動をう~んと頭ひねって考えてみると、いわゆる

def fact4_other(n):
    if n == 0:
        return 1
        if not 1:
            return n * fact4_other(n-1)
    else:
        return n * fact4_other(n-1)

こんな動作をするコードになっているはず…。あってる…よね…(自信が…w)。 数字の場合、pythonは0以外がTrueなので、not 1を評価するとFalse。だからこの場合if not 1は実行されないんですよね。 結局fact2で書いたコードと一緒になりますから、コレでもおkなはず。。 わっかりにくーい。 ほぼ同じだけど

def fact5(x):
    return x > 1 and x * fact5(x - 1) or 1

こんな感じに書いたほうがいいのかな… うん。

やっぱり私はreduce関数が一番素直で好きだ。 あと好きなのは、サイトにも書いてありましたが、有名な以下の実装。

def fact6(n):
    result = 1
    for i in xrange(1, n+1):
        result *= i
    return result
def fact7(n):
    result = 1
    while n > 0:
        result *= n
        n -= 1
    return result

この2つ!

よく「短いコードがいい」っていうけど、いや早いコードがいいんだよ!! ということで、timeitモジュール使って50!を15000回計算させた時の速さを3回分みてみます。

import timeit


def fact_module(n):
    import math
    return math.factorial(n)


def fact1(n):
    return reduce(lambda x, y: x*y, xrange(1, n+1), 1)


def fact2(n):
    return 1 if n == 0 else n*fact2(n-1)


def fact2_other(n):
    if n == 0:
        return 1
    else:
        return n * fact2_other(n-1)


def fact3(x, init=1):
    return fact3(x-1, init*x) if x else init


def fact4(n):
    return n == 0 and 1 or n * fact4(n-1)


def fact4_other(n):
    if n == 0:
        return 1
        if not 1:
            return n * fact4_other(n-1)
    else:
        return n * fact4_other(n-1)


def fact5(x):
    return x > 1 and x * fact5(x - 1) or 1


def fact6(n):
    result = 1
    for i in xrange(1, n+1):
        result *= i
    return result


def fact6_notx(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result


def fact7(n):
    result = 1
    while n > 0:
        result *= n
        n -= 1
    return result


if __name__ == "__main__":
    functionlist = [
    "fact_module", "fact1", "fact2", "fact2_other", "fact3", 
    "fact4", "fact4_other", "fact5", "fact6", "fact6_notx", "fact7",
    ]

    x = 50  # fact(x)
    repeat_count = 15000  # time.timeit(repeat_count)

    results = {}
    for name in functionlist:
        timeit_first_arg = name + '(%d)' % (x)
        timeit_second_arg = 'from %s import %s' % (__name__, name)

        results[name] = timeit.Timer(timeit_first_arg, timeit_second_arg)
        results[name] = results[name].repeat(3, repeat_count)
        print name, results[name]

としてみると、出力は

fact_module [0.07655851469225951, 0.07918853891311373, 0.07584634661345338]
fact1 [0.1762450893422887, 0.17482744649368775, 0.171279546497079]
fact2 [0.21122030625012267, 0.20733149371453663, 0.2085144245271402]
fact2_other [0.21064602033695, 0.209365813433382, 0.20667465699022403]
fact3 [0.25979364974538655, 0.25028111897847616, 0.2588476620717848]
fact4 [0.20971297306076986, 0.2119837896980159, 0.21550536267917986]
fact4_other [0.2092288237089499, 0.2126611525699631, 0.20739574948104522]
fact5 [0.2221723446750712, 0.21591767051427802, 0.21430949146915523]
fact6 [0.11070509994449029, 0.10617149864081199, 0.10197880987611185]
fact6_notx [0.11001747399872563, 0.11222849707546967, 0.110821117300687]
fact7 [0.13919985506754884, 0.13190950289240178, 0.13079305894931093]

こうなった。当然モジュールはええええなんですが、fact6がなかなかいい線言ってる気がする。

xrangeが速いと聞くので、xrangeじゃないヤツも作ってみましたがゆーほどは変わらないですね。

プログラミングで、アルゴリズムを解説したサイトや本って色々ありますけれど、標準ライブラリにあるなら1行だけでも触れといてほしいよねやっぱり。

でもなんだかんだでアルゴリズムを知ると、自分でちょこちょこ書き換えられるのがいいですよね。だから今回早かったfact6を改造して気持ち程度に多重階乗計算ができるようにしました…w

標準ライブラリにあるのと同じ動作するヤツ作ってもなぁ…って感じなので…。あと、負の値を入れられた時は、一応0を出力するようにします。

def factmulti(n, k=1):
    if n < 1 - k:
        return 0
    if n <= 0:
        return 1
    result = 1
    for i in xrange(n, 0, -k):
        result *= i
    return result

これで、二重階乗とか多重階乗とかができるかな? 二重階乗が合ってるかどうかの軽い確認を、せっかくなのでmapとfilterを無理やり使ってみてみようかな・・

import math


def factmulti(n, k=1):
    if n < 1 - k:
        return 0
    if n <= 0:
        return 1
    result = 1
    for i in xrange(n, 0, -k):
        result *= i
    return result

if __name__ == '__main__':
    a = 10
    print map(factmulti, range(a))
    print map(math.factorial, range(a))

    # 2a!! = (x^a) * (a!)
    print map(factmulti, filter(lambda x: x%2==0, range(a*2)), [2 for i in range(0, a*2, 2)])
    print map(lambda x: pow(2, x/2)*math.factorial(x/2), [i for i in range(0, a*2, 2)])

79行余裕で超えてる/(^o^)\

一応二重階乗って、偶数の二重階乗の時は(2n)!!(2n)!! = 2nn!2nn!という関係式があるので、偶数の時にこの公式と適合するかチェックしてます

右辺の普通の階乗部分は標準ライブラリに行わせていますが、ちゃんと同じ値でてますね!

階乗でこの公式を使うと思い出してしまうのはガンマ関数なのですが、ガンマ関数はpython3.2からmathモジュールに入ってるらしいです。


PAGE TOP