【使用Python实现算法】05 标准库（函数式编程模块）

Python 标准库中的functools和itertools模块，提供了一些函数式编程的工具函数。

functools 高阶函数

cache 与 lru_cache

用户缓存函数值的装饰器，可以缓存函数的调用结果。其中lru_cache函数可以设置一个缓存的最大容量，使用 LRU 算法淘汰长期不用的缓存。cache函数容量没有限制，相当于lru_cache(maxsize=None)。

@lru_cache(maxsize=3)
def fib(n):
    if n = 1:
        return n
    return fib(n - 1) + fib(n - 2)

assert [fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

@cache
def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)

assert [factorial(n) for n in range(10)] == [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

partial 固定函数的一部分参数

partial() 会被“冻结了”一部分函数参数和/或关键字的部分函数应用所使用，从而得到一个具有简化签名的新对象。 例如，partial() 可用来创建一个行为类似于 int() 函数的可调用对象，其中 base 参数默认为二：

from functools import partial
basetwo = partial(int, base=2)
basetwo.__doc__ = 'Convert base 2 string to an int.'
assert basetwo('10010') == 18

reduce

Python2 中的reduce函数是一个内置函数，在 Python3 中被移入了functools模块中。 原因是reduce函数的效率没有寻常的 for 循环高，而往往使用了reduce函数的代码也不是特别容易理解（对比map和filter）。

assert reduce(lambda x, y: x + y, [1, 2, 3, 4, 5]) == 15

itertools 实用的迭代器

itertools模块是 Python 参考 APL，Haskell，SML 等编程语言的启发，实现的个快速、高效利用内存的核心工具集。 在算法实现中利用好itertools模块，可以有效提高代码编写速度、可维护性和算法的效率。

islice

首先介绍一下islice函数，可用于迭代器切片。

assert list(islice('ABCDEFG', 3)) == ['A', 'B', 'C']

无穷迭代器

count

count函数可以生成一个无穷的迭代器，每次调用返回一个整数，从 0 开始，每次增 1。 可以指定初始值，步长和生成数量。 count函数很适合替代while True:n +=1的循环。

def gen_primes():
    primes = []
    for n in count(2):
        if not any(n % p == 0 for p in primes):
            primes.append(n)
            yield n

assert list(islice(gen_primes(), 10)) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

cycle

cycle函数可以不断地迭代一个序列，直到迭代完成，然后重新开始迭代。

assert list(islice(cycle("ABC"), 6)) == ["A", "B", "C", "A", "B", "C"]

repeat

repeat函数会不断地重复生成一个元素。

assert list(map(pow, range(6), repeat(3))) == [0, 1, 8, 27, 64, 125]

有限数量的迭代器

accumulate

accumulate可以简单地理解为一个累加器。在很多需要计算列表的前缀和的算法中很有用。

assert list(islice(accumulate(count()), 5)) == [0, 1, 3, 6, 10]

chain

chain函数可以理解为合并多个序列的迭代器。

st(chain("ABC", "DEF")) == ["A", "B", "C", "D", "E", "F"]

dropwhile

dropwhile可以删除序列中的前缀元素，直到某个条件不满足。

assert list(dropwhile(lambda x: x  5, [1, 4, 6, 4, 1])) == [6, 4, 1]

filterfalse

filterfalse可以过滤出一个序列中不满足某个条件的元素。

assert list(filterfalse(lambda x: x % 2 == 0, range(10))) == [1, 3, 5, 7, 9]

pairwise

pairwise类似于一个容量为 2 的滑动窗口，每次迭代返回一对元素。

asset list(pairwise([1, 2, 3, 4, 5])) == [(1, 2), (2, 3), (3, 4), (4, 5)]

takewhile

takewhile遍历一个序列，直到第一个不满足某个条件的元素。

assert list(takewhile(lambda x: x  5, [1, 4, 6, 4, 1])) == [1, 4]

排列组合迭代器

product

product可以得到多个序列的笛卡尔积。

assert list(product("ABCD", "xy")) == [('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y'), ('C', 'x'), ('C', 'y'), ('D', 'x'), ('D', 'y')]

permutations

permutations可以得到一个序列的全排列。

assert list(permutations([1, 2, 3])) == [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
assert list(permutations([1, 2, 3], 2)) == [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

combinations

combinations可以得到一个序列的组合。

assert list(combinations(range(4),2)) == [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

combinations_with_replacement

combinations_with_replacement可以得到一个序列的可重复组合。

list(combinations_with_replacement([1,2,3],2)) == [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

总结

使用 Python 实现算法相比其他语言的一个优势就是标准库中的itertools，可以节省大量编写 for 循环和递归函数的时间。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！