昨天偶然看见一个算法题,要求返回一个包含给定英文字符串(小写)中所有最长的升序字符串的列表,比如:
findmax('abc')-->['abc']findmax('afz')-->['afz']findmax('cba')-->['c','b','a']findmax('zfa')-->['z','f','a']findmax('abczabc')-->['abcz']findmax('abcabc')-->['abc','abc']
其实用常规思路来解还是没什么难度的.不过最近在学Scheme,便总是想着用函数式风格该怎么搞.最好能够完全避开赋值语句.
现在终于彻彻底底搞出来了,还是2种版本的函数式风格.纯的那种就是完全没有任何赋值语句的,甚至连方法语句都没有的(比如list.append(1)之类的).
感觉函数式编程很考验"倒推"以及"把复杂问题分解为简单问题'的能力.所谓"倒推",就是事先心中要设计好一个算法框架和数据结构(字典,列表,集合等等).命令式编程很难体会到设计的概念,大概是因为可以把一个变量改来改去,比较容易.
有时候我们需要的是某种值,这些值直接求是非常难的.但是把它转化成某种常见数据结构的衍生品,往往会变得简单.
# -*- coding:utf-8 -*-from collections import defaultdict#常规命令式 def findmax_c(s): buf=defaultdict(list) string=s if len(s)<2 else s[0] for i in range(1,len(s)): if s[i-1]<=s[i]: string+=s[i] else: buf[len(string)].append(string) string=s[i] buf[len(string)].append(string) return buf[max(buf)]#不是那么纯的函数式:def findmax_f(s): def recur(s,mbr='',buf=defaultdict(list)): if s=='': buf[len(mbr)].append(mbr) return buf[max(buf)] if mbr=='' or mbr[-1]<=s[0]: return recur(s[1:],mbr+s[0]) buf[len(mbr)].append(mbr) return recur(s[1:],s[0]) return recur(s)def memory(function): cache = {} def memofunc(*nkw,**kw): key=str(nkw)+str(kw) if key not in cache: cache[key] = function(*nkw,**kw) return cache[key] return memofunc#纯函数式:def findmax_pf(s): @memory def recur(s,mbr=''): if s=='': return [mbr] if mbr=='' or mbr[-1]<=s[0]: return recur(s[1:],mbr+s[0]) return [mbr]+recur(s[1:],s[0]) return filter(lambda x:len(x)==len(max(recur(s),key=len)) ,recur(s))if __name__ == '__main__' : for x in ['','a','aggz','abcaggza','abcabc','zfa','zfa']: print '字符:{}命令式:{}函数式:{}纯函数:{}'.format( x.ljust(10), str(findmax_c(x)).ljust(16), str(findmax_f(x)).ljust(16), str(findmax_pf(x)).ljust(16))
最终结果:
>>> 字符: 命令式:[''] 函数式:[''] 纯函数:[''] 字符:a 命令式:['a'] 函数式:['a'] 纯函数:['a'] 字符:aggz 命令式:['aggz'] 函数式:['aggz'] 纯函数:['aggz'] 字符:abcaggza 命令式:['aggz'] 函数式:['aggz'] 纯函数:['aggz'] 字符:abcabc 命令式:['abc', 'abc'] 函数式:['abc', 'abc'] 纯函数:['abc', 'abc'] 字符:zfa 命令式:['z', 'f', 'a'] 函数式:['z', 'f', 'a'] 纯函数:['z', 'f', 'a'] 字符:zfa 命令式:['z', 'f', 'a'] 函数式:['z', 'f', 'a'] 纯函数:['z', 'f', 'a']
其中,装饰器memory主要是让Python避免重复计算相同参数的函数..这是提高性能必须采取的手段,因为函数式编程要求你不能对一个值建立引用.
函数式编程要在默认参数上大做文章..通常命令式编程中的一些变量可以把它转化为默认参数来处理.