cari
Rumahpembangunan bahagian belakangTutorial PythonPython中利用函数装饰器实现备忘功能

“备忘”的定义

“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")

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Python vs C: Lengkung pembelajaran dan kemudahan penggunaanPython vs C: Lengkung pembelajaran dan kemudahan penggunaanApr 19, 2025 am 12:20 AM

Python lebih mudah dipelajari dan digunakan, manakala C lebih kuat tetapi kompleks. 1. Sintaks Python adalah ringkas dan sesuai untuk pemula. Penaipan dinamik dan pengurusan memori automatik menjadikannya mudah digunakan, tetapi boleh menyebabkan kesilapan runtime. 2.C menyediakan kawalan peringkat rendah dan ciri-ciri canggih, sesuai untuk aplikasi berprestasi tinggi, tetapi mempunyai ambang pembelajaran yang tinggi dan memerlukan memori manual dan pengurusan keselamatan jenis.

Python vs C: Pengurusan dan Kawalan MemoriPython vs C: Pengurusan dan Kawalan MemoriApr 19, 2025 am 12:17 AM

Python dan C mempunyai perbezaan yang signifikan dalam pengurusan dan kawalan memori. 1. Python menggunakan pengurusan memori automatik, berdasarkan pengiraan rujukan dan pengumpulan sampah, memudahkan kerja pengaturcara. 2.C memerlukan pengurusan memori manual, memberikan lebih banyak kawalan tetapi meningkatkan risiko kerumitan dan kesilapan. Bahasa mana yang harus dipilih harus berdasarkan keperluan projek dan timbunan teknologi pasukan.

Python untuk pengkomputeran saintifik: rupa terperinciPython untuk pengkomputeran saintifik: rupa terperinciApr 19, 2025 am 12:15 AM

Aplikasi Python dalam pengkomputeran saintifik termasuk analisis data, pembelajaran mesin, simulasi berangka dan visualisasi. 1.Numpy menyediakan susunan pelbagai dimensi yang cekap dan fungsi matematik. 2. Scipy memanjangkan fungsi numpy dan menyediakan pengoptimuman dan alat algebra linear. 3. Pandas digunakan untuk pemprosesan dan analisis data. 4.Matplotlib digunakan untuk menghasilkan pelbagai graf dan hasil visual.

Python dan C: Mencari alat yang betulPython dan C: Mencari alat yang betulApr 19, 2025 am 12:04 AM

Sama ada untuk memilih Python atau C bergantung kepada keperluan projek: 1) Python sesuai untuk pembangunan pesat, sains data, dan skrip kerana sintaks ringkas dan perpustakaan yang kaya; 2) C sesuai untuk senario yang memerlukan prestasi tinggi dan kawalan asas, seperti pengaturcaraan sistem dan pembangunan permainan, kerana kompilasi dan pengurusan memori manualnya.

Python untuk sains data dan pembelajaran mesinPython untuk sains data dan pembelajaran mesinApr 19, 2025 am 12:02 AM

Python digunakan secara meluas dalam sains data dan pembelajaran mesin, terutamanya bergantung pada kesederhanaannya dan ekosistem perpustakaan yang kuat. 1) PANDAS digunakan untuk pemprosesan dan analisis data, 2) Numpy menyediakan pengiraan berangka yang cekap, dan 3) SCIKIT-Learn digunakan untuk pembinaan dan pengoptimuman model pembelajaran mesin, perpustakaan ini menjadikan Python alat yang ideal untuk sains data dan pembelajaran mesin.

Pembelajaran Python: Adakah 2 jam kajian harian mencukupi?Pembelajaran Python: Adakah 2 jam kajian harian mencukupi?Apr 18, 2025 am 12:22 AM

Adakah cukup untuk belajar Python selama dua jam sehari? Ia bergantung pada matlamat dan kaedah pembelajaran anda. 1) Membangunkan pelan pembelajaran yang jelas, 2) Pilih sumber dan kaedah pembelajaran yang sesuai, 3) mengamalkan dan mengkaji semula dan menyatukan amalan tangan dan mengkaji semula dan menyatukan, dan anda secara beransur-ansur boleh menguasai pengetahuan asas dan fungsi lanjutan Python dalam tempoh ini.

Python untuk Pembangunan Web: Aplikasi UtamaPython untuk Pembangunan Web: Aplikasi UtamaApr 18, 2025 am 12:20 AM

Aplikasi utama Python dalam pembangunan web termasuk penggunaan kerangka Django dan Flask, pembangunan API, analisis data dan visualisasi, pembelajaran mesin dan AI, dan pengoptimuman prestasi. 1. Rangka Kerja Django dan Flask: Django sesuai untuk perkembangan pesat aplikasi kompleks, dan Flask sesuai untuk projek kecil atau sangat disesuaikan. 2. Pembangunan API: Gunakan Flask atau DjangorestFramework untuk membina Restfulapi. 3. Analisis Data dan Visualisasi: Gunakan Python untuk memproses data dan memaparkannya melalui antara muka web. 4. Pembelajaran Mesin dan AI: Python digunakan untuk membina aplikasi web pintar. 5. Pengoptimuman Prestasi: Dioptimumkan melalui pengaturcaraan, caching dan kod tak segerak

Python vs C: Meneroka Prestasi dan KecekapanPython vs C: Meneroka Prestasi dan KecekapanApr 18, 2025 am 12:20 AM

Python lebih baik daripada C dalam kecekapan pembangunan, tetapi C lebih tinggi dalam prestasi pelaksanaan. 1. Sintaks ringkas Python dan perpustakaan yang kaya meningkatkan kecekapan pembangunan. 2. Ciri-ciri jenis kompilasi dan kawalan perkakasan meningkatkan prestasi pelaksanaan. Apabila membuat pilihan, anda perlu menimbang kelajuan pembangunan dan kecekapan pelaksanaan berdasarkan keperluan projek.

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SecLists

SecLists

SecLists ialah rakan penguji keselamatan muktamad. Ia ialah koleksi pelbagai jenis senarai yang kerap digunakan semasa penilaian keselamatan, semuanya di satu tempat. SecLists membantu menjadikan ujian keselamatan lebih cekap dan produktif dengan menyediakan semua senarai yang mungkin diperlukan oleh penguji keselamatan dengan mudah. Jenis senarai termasuk nama pengguna, kata laluan, URL, muatan kabur, corak data sensitif, cangkerang web dan banyak lagi. Penguji hanya boleh menarik repositori ini ke mesin ujian baharu dan dia akan mempunyai akses kepada setiap jenis senarai yang dia perlukan.

PhpStorm versi Mac

PhpStorm versi Mac

Alat pembangunan bersepadu PHP profesional terkini (2018.2.1).

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa