“备忘”的定义
“memoization”(备忘)这个词是由Donald Michie在1968年提出的,它基于拉丁语单词“memorandum”(备忘录),意思是“被记住”。虽然它和单词“memorization”在某种程度上有些相似,但它并不是该单词的错误拼写。实际上,Memoisation是一种用于通过计算来加速程序的技术,它通过记住输入量的计算结果,例如函数调用结果,来实现其加速目的。如果遇到相同的输入或者具有相同参数的函数调用,那么之前存储的结果就可以被再次使用,从而避免一些不必要的计算。在很多情况下,可以使用一个简单的数组来存储结果,但也可以使用许多其他的数据结构,例如关联数组,它在Perl语言中叫做哈希,在Python语言中称为字典。
备忘功能可以由程序员显式地编程实现,但是一些编程语言如Python,都提供了自动备忘函数的机制。
利用函数装饰器实现备忘功能
在前面关于递归函数的那章中,我们分别使用迭代和递归实现了斐波纳契数列的求解。我们已经证明,如果直接利用斐波纳契数列的数学定义,在一个递归函数中实现数列的求解,正如下面的函数一样,那么它将具有指数级的时间复杂度:
def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2)
此外,我们还提出了一种提高递归实现的时间复杂度的方法,即通过添加一个字典来记住之前函数的计算结果。这是一个显式地使用备忘技术的例子,只是当时我们并没有这么称呼它。这种方法的缺点是,原始递归实现的明晰性和优雅性丢失了。
造成以上缺点的原因是,我们改变了递归函数fib的代码。不过下面的代码不会改变我们的fib函数,所以它的明晰性和易读性并没有丢失。为了实现该目的,我们使用自定义的函数memoize()。函数memoize()以函数作为参数,并使用一个字典“memo”来存储函数的结果。虽然变量“memo”和函数“f”仅仅具有局部备忘功能,但是它们通过函数“helper”被一个闭包捕获,而memoize()将函数“helper”作为引用返回。所以,对memoize(fib)的调用将会返回一个helper()的引用,而在helper()中实现了fib()函数的功能以及一个用于保存还未存储的结果到字典“memo”中的包装器,并防止重新计算“memo”中已有的结果。
def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) fib = memoize(fib) print(fib(40))
现在让我们了解下所谓的装饰器,首先看一下上面代码中将备忘功能指派到fib函数的这一行:
fib = memoize(fib)
一种说法是,函数memoize()装饰了函数fib。
将Memoize封装成类
我们还可以将结果的缓存封装到一个类中,如下面的例子所示:
class Memoize: def __init__(self, fn): self.fn = fn self.memo = {} def __call__(self, *args): if args not in self.memo: self.memo[args] = self.fn(*args) return self.memo[args]
因为我们使用了字典,所以不能使用可变参数,即参数必须是不可变的。
Python中的装饰器
Python中的装饰器是一个可调用的Python对象,用于修改一个函数、方法或者类的定义。原始的对象,也就是即将被改变的那个对象,作为参数传递给一个装饰器,而装饰器则返回一个修改过的对象,例如一个修改过的函数,它会被绑定到定义中使用的名字上。Python中的装饰器与Java中的注解有一个相似的语法,即Python中的装饰器语法可以看作是纯粹的语法糖,使用“@”作为关键字。
示例:使用装饰器实现备忘功能
其实,前面我们已经使用了装饰器,只是没有这么称呼它而已。实际上,本章开头例子中的memoize函数就是一个装饰器,我们使用它来记住fib函数的结果,只是我们没有使用Python中装饰器特殊的语法而已,即艾特字符“@”。
相比于写成下面的形式
fib = memoize(fib)
我们可以这样写
@memoize
但这一行必须直接写在被装饰的函数之前,在我们的例子fib()中,如下所示:
def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper @memoize def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) #fib = memoize(fib) print(fib(40))
利用装饰器检查参数
在讲解递归函数的那章中我们介绍了阶乘函数,在那里我们希望保持函数尽可能简单,而不想掩盖基本理念,所以代码中没有包含任何参数检查代码。然而,如果别人以负数或者浮点数作为参数来调用我们的函数,那么函数将会陷入一个死循环。
下面的程序使用一个装饰器函数来确保传给函数“factorial”的参数是一个正整数:
def argument_test_natural_number(f): def helper(x): if type(x) == int and x > 0: return f(x) else: raise Exception("Argument is not an integer") return helper @argument_test_natural_number def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) for i in range(1,10): print(i, factorial(i)) print(factorial(-1))
练习
1、我们的练习是一个古老的谜题。1612年,法国耶稣会士Claude-Gaspar Bachet提出了该谜题,即使用一个天平称出从1磅到40磅的所有整数重量的东西(例如,糖或者面粉),求最少的砝码数量。
第一个方法可能是使用1、2、4、8、16和32磅重量的这些砝码。如果我们将砝码放在天平的一端,而将物品放在另一端,那么这种方法用到的砝码数量将是最小的。然而,我们也可以将砝码同时放在天平的两端,此时我们仅仅需要重量为1、3、9、27的砝码。
编写一个Python函数weigh(),该函数计算需要的砝码以及它们在天平盘中的分布,以此来称量1磅到40磅中任何一个整数重量的物品。
解决方法
1、我们需要前面章节“Linear Combinations”中的函数linear_combination()。
def factors_set(): factors_set = ( (i,j,k,l) for i in [-1,0,1] for j in [-1,0,1] for k in [-1,0,1] for l in [-1,0,1]) for factor in factors_set: yield factor def memoize(f): results = {} def helper(n): if n not in results: results[n] = f(n) return results[n] return helper @memoize def linear_combination(n): """ returns the tuple (i,j,k,l) satisfying n = i*1 + j*3 + k*9 + l*27 """ weighs = (1,3,9,27) for factors in factors_set(): sum = 0 for i in range(len(factors)): sum += factors[i] * weighs[i] if sum == n: return factors
2、利用上面的代码,就能很容易写出我们的函数weigh()。
def weigh(pounds): weights = (1,3,9,27) scalars = linear_combination(pounds) left = "" right = "" for i in range(len(scalars)): if scalars[i] == -1: left += str(weights[i]) + " " elif scalars[i] == 1: right += str(weights[i]) + " " return (left,right) for i in [2,3,4,7,8,9,20,40]: pans = weigh(i) print("Left pan: " + str(i) + " plus " + pans[0]) print("Right pan: " + pans[1] + "n")

Python의 유연성은 다중 파리가 지원 및 동적 유형 시스템에 반영되며, 사용 편의성은 간단한 구문 및 풍부한 표준 라이브러리에서 나옵니다. 유연성 : 객체 지향, 기능 및 절차 프로그래밍을 지원하며 동적 유형 시스템은 개발 효율성을 향상시킵니다. 2. 사용 편의성 : 문법은 자연 언어에 가깝고 표준 라이브러리는 광범위한 기능을 다루며 개발 프로세스를 단순화합니다.

Python은 초보자부터 고급 개발자에 이르기까지 모든 요구에 적합한 단순성과 힘에 호의적입니다. 다목적 성은 다음과 같이 반영됩니다. 1) 배우고 사용하기 쉽고 간단한 구문; 2) Numpy, Pandas 등과 같은 풍부한 라이브러리 및 프레임 워크; 3) 다양한 운영 체제에서 실행할 수있는 크로스 플랫폼 지원; 4) 작업 효율성을 향상시키기위한 스크립팅 및 자동화 작업에 적합합니다.

예, 하루에 2 시간 후에 파이썬을 배우십시오. 1. 합리적인 학습 계획 개발, 2. 올바른 학습 자원을 선택하십시오. 3. 실습을 통해 학습 된 지식을 통합하십시오. 이 단계는 짧은 시간 안에 Python을 마스터하는 데 도움이 될 수 있습니다.

Python은 빠른 개발 및 데이터 처리에 적합한 반면 C는 고성능 및 기본 제어에 적합합니다. 1) Python은 간결한 구문과 함께 사용하기 쉽고 데이터 과학 및 웹 개발에 적합합니다. 2) C는 고성능과 정확한 제어를 가지고 있으며 게임 및 시스템 프로그래밍에 종종 사용됩니다.

Python을 배우는 데 필요한 시간은 개인마다 다릅니다. 주로 이전 프로그래밍 경험, 학습 동기 부여, 학습 리소스 및 방법 및 학습 리듬의 영향을받습니다. 실질적인 학습 목표를 설정하고 실용적인 프로젝트를 통해 최선을 다하십시오.

파이썬은 자동화, 스크립팅 및 작업 관리가 탁월합니다. 1) 자동화 : 파일 백업은 OS 및 Shutil과 같은 표준 라이브러리를 통해 실현됩니다. 2) 스크립트 쓰기 : PSUTIL 라이브러리를 사용하여 시스템 리소스를 모니터링합니다. 3) 작업 관리 : 일정 라이브러리를 사용하여 작업을 예약하십시오. Python의 사용 편의성과 풍부한 라이브러리 지원으로 인해 이러한 영역에서 선호하는 도구가됩니다.

제한된 시간에 Python 학습 효율을 극대화하려면 Python의 DateTime, Time 및 Schedule 모듈을 사용할 수 있습니다. 1. DateTime 모듈은 학습 시간을 기록하고 계획하는 데 사용됩니다. 2. 시간 모듈은 학습과 휴식 시간을 설정하는 데 도움이됩니다. 3. 일정 모듈은 주간 학습 작업을 자동으로 배열합니다.

Python은 게임 및 GUI 개발에서 탁월합니다. 1) 게임 개발은 Pygame을 사용하여 드로잉, 오디오 및 기타 기능을 제공하며 2D 게임을 만드는 데 적합합니다. 2) GUI 개발은 Tkinter 또는 PYQT를 선택할 수 있습니다. Tkinter는 간단하고 사용하기 쉽고 PYQT는 풍부한 기능을 가지고 있으며 전문 개발에 적합합니다.


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

PhpStorm 맥 버전
최신(2018.2.1) 전문 PHP 통합 개발 도구

안전한 시험 브라우저
안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

SublimeText3 Linux 새 버전
SublimeText3 Linux 최신 버전

MinGW - Windows용 미니멀리스트 GNU
이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.
