欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python中利用函數(shù)裝飾器實(shí)現(xiàn)備忘功能

 更新時(shí)間:2015年03月30日 15:11:30   作者:python-course  
這篇文章主要介紹了Python中利用函數(shù)裝飾器實(shí)現(xiàn)備忘功能,同時(shí)還降到了利用裝飾器來(lái)檢查函數(shù)的遞歸、確保參數(shù)傳遞的正確,需要的朋友可以參考下

“備忘”的定義

“memoization”(備忘)這個(gè)詞是由Donald Michie在1968年提出的,它基于拉丁語(yǔ)單詞“memorandum”(備忘錄),意思是“被記住”。雖然它和單詞“memorization”在某種程度上有些相似,但它并不是該單詞的錯(cuò)誤拼寫(xiě)。實(shí)際上,Memoisation是一種用于通過(guò)計(jì)算來(lái)加速程序的技術(shù),它通過(guò)記住輸入量的計(jì)算結(jié)果,例如函數(shù)調(diào)用結(jié)果,來(lái)實(shí)現(xiàn)其加速目的。如果遇到相同的輸入或者具有相同參數(shù)的函數(shù)調(diào)用,那么之前存儲(chǔ)的結(jié)果就可以被再次使用,從而避免一些不必要的計(jì)算。在很多情況下,可以使用一個(gè)簡(jiǎn)單的數(shù)組來(lái)存儲(chǔ)結(jié)果,但也可以使用許多其他的數(shù)據(jù)結(jié)構(gòu),例如關(guān)聯(lián)數(shù)組,它在Perl語(yǔ)言中叫做哈希,在Python語(yǔ)言中稱(chēng)為字典。

備忘功能可以由程序員顯式地編程實(shí)現(xiàn),但是一些編程語(yǔ)言如Python,都提供了自動(dòng)備忘函數(shù)的機(jī)制。
利用函數(shù)裝飾器實(shí)現(xiàn)備忘功能

在前面關(guān)于遞歸函數(shù)的那章中,我們分別使用迭代和遞歸實(shí)現(xiàn)了斐波納契數(shù)列的求解。我們已經(jīng)證明,如果直接利用斐波納契數(shù)列的數(shù)學(xué)定義,在一個(gè)遞歸函數(shù)中實(shí)現(xiàn)數(shù)列的求解,正如下面的函數(shù)一樣,那么它將具有指數(shù)級(jí)的時(shí)間復(fù)雜度:
 

def fib(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

此外,我們還提出了一種提高遞歸實(shí)現(xiàn)的時(shí)間復(fù)雜度的方法,即通過(guò)添加一個(gè)字典來(lái)記住之前函數(shù)的計(jì)算結(jié)果。這是一個(gè)顯式地使用備忘技術(shù)的例子,只是當(dāng)時(shí)我們并沒(méi)有這么稱(chēng)呼它。這種方法的缺點(diǎn)是,原始遞歸實(shí)現(xiàn)的明晰性和優(yōu)雅性丟失了。

造成以上缺點(diǎn)的原因是,我們改變了遞歸函數(shù)fib的代碼。不過(guò)下面的代碼不會(huì)改變我們的fib函數(shù),所以它的明晰性和易讀性并沒(méi)有丟失。為了實(shí)現(xiàn)該目的,我們使用自定義的函數(shù)memoize()。函數(shù)memoize()以函數(shù)作為參數(shù),并使用一個(gè)字典“memo”來(lái)存儲(chǔ)函數(shù)的結(jié)果。雖然變量“memo”和函數(shù)“f”僅僅具有局部備忘功能,但是它們通過(guò)函數(shù)“helper”被一個(gè)閉包捕獲,而memoize()將函數(shù)“helper”作為引用返回。所以,對(duì)memoize(fib)的調(diào)用將會(huì)返回一個(gè)helper()的引用,而在helper()中實(shí)現(xiàn)了fib()函數(shù)的功能以及一個(gè)用于保存還未存儲(chǔ)的結(jié)果到字典“memo”中的包裝器,并防止重新計(jì)算“memo”中已有的結(jié)果。
 

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

現(xiàn)在讓我們了解下所謂的裝飾器,首先看一下上面代碼中將備忘功能指派到fib函數(shù)的這一行:
 

fib = memoize(fib)

一種說(shuō)法是,函數(shù)memoize()裝飾了函數(shù)fib。
將Memoize封裝成類(lèi)

我們還可以將結(jié)果的緩存封裝到一個(gè)類(lèi)中,如下面的例子所示:

 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]

因?yàn)槲覀兪褂昧俗值?,所以不能使用可變參?shù),即參數(shù)必須是不可變的。
Python中的裝飾器

Python中的裝飾器是一個(gè)可調(diào)用的Python對(duì)象,用于修改一個(gè)函數(shù)、方法或者類(lèi)的定義。原始的對(duì)象,也就是即將被改變的那個(gè)對(duì)象,作為參數(shù)傳遞給一個(gè)裝飾器,而裝飾器則返回一個(gè)修改過(guò)的對(duì)象,例如一個(gè)修改過(guò)的函數(shù),它會(huì)被綁定到定義中使用的名字上。Python中的裝飾器與Java中的注解有一個(gè)相似的語(yǔ)法,即Python中的裝飾器語(yǔ)法可以看作是純粹的語(yǔ)法糖,使用“@”作為關(guān)鍵字。
示例:使用裝飾器實(shí)現(xiàn)備忘功能

其實(shí),前面我們已經(jīng)使用了裝飾器,只是沒(méi)有這么稱(chēng)呼它而已。實(shí)際上,本章開(kāi)頭例子中的memoize函數(shù)就是一個(gè)裝飾器,我們使用它來(lái)記住fib函數(shù)的結(jié)果,只是我們沒(méi)有使用Python中裝飾器特殊的語(yǔ)法而已,即艾特字符“@”。

相比于寫(xiě)成下面的形式
 

fib = memoize(fib)

我們可以這樣寫(xiě)
 

@memoize

但這一行必須直接寫(xiě)在被裝飾的函數(shù)之前,在我們的例子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))

利用裝飾器檢查參數(shù)

在講解遞歸函數(shù)的那章中我們介紹了階乘函數(shù),在那里我們希望保持函數(shù)盡可能簡(jiǎn)單,而不想掩蓋基本理念,所以代碼中沒(méi)有包含任何參數(shù)檢查代碼。然而,如果別人以負(fù)數(shù)或者浮點(diǎn)數(shù)作為參數(shù)來(lái)調(diào)用我們的函數(shù),那么函數(shù)將會(huì)陷入一個(gè)死循環(huán)。

下面的程序使用一個(gè)裝飾器函數(shù)來(lái)確保傳給函數(shù)“factorial”的參數(shù)是一個(gè)正整數(shù):
 

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


練習(xí)

1、我們的練習(xí)是一個(gè)古老的謎題。1612年,法國(guó)耶穌會(huì)士Claude-Gaspar Bachet提出了該謎題,即使用一個(gè)天平稱(chēng)出從1磅到40磅的所有整數(shù)重量的東西(例如,糖或者面粉),求最少的砝碼數(shù)量。

第一個(gè)方法可能是使用1、2、4、8、16和32磅重量的這些砝碼。如果我們將砝碼放在天平的一端,而將物品放在另一端,那么這種方法用到的砝碼數(shù)量將是最小的。然而,我們也可以將砝碼同時(shí)放在天平的兩端,此時(shí)我們僅僅需要重量為1、3、9、27的砝碼。

編寫(xiě)一個(gè)Python函數(shù)weigh(),該函數(shù)計(jì)算需要的砝碼以及它們?cè)谔炱奖P(pán)中的分布,以此來(lái)稱(chēng)量1磅到40磅中任何一個(gè)整數(shù)重量的物品。
解決方法

1、我們需要前面章節(jié)“Linear Combinations”中的函數(shù)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、利用上面的代碼,就能很容易寫(xiě)出我們的函數(shù)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")

相關(guān)文章

  • Pycharm配置lua編譯環(huán)境過(guò)程圖解

    Pycharm配置lua編譯環(huán)境過(guò)程圖解

    這篇文章主要介紹了Pycharm配置lua編譯環(huán)境過(guò)程圖解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-11-11
  • python mac下安裝虛擬環(huán)境的圖文教程

    python mac下安裝虛擬環(huán)境的圖文教程

    這篇文章主要介紹了python mac下安裝虛擬環(huán)境 的相關(guān)資料,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2019-04-04
  • python密碼學(xué)一次性密碼的實(shí)現(xiàn)

    python密碼學(xué)一次性密碼的實(shí)現(xiàn)

    這篇文章主要為大家介紹了python密碼學(xué)一次性密碼的實(shí)現(xiàn),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-05-05
  • python基礎(chǔ)操作列表推導(dǎo)式

    python基礎(chǔ)操作列表推導(dǎo)式

    列表推導(dǎo)式形式較為簡(jiǎn)潔,是利用其它列表創(chuàng)建新列表的一種方式,它的工作方式類(lèi)似于for循環(huán),也可以嵌套if條件判斷語(yǔ)句,需要的朋友可以參考下
    2023-04-04
  • Python之reload流程實(shí)例代碼解析

    Python之reload流程實(shí)例代碼解析

    這篇文章主要介紹了Python之reload流程實(shí)例代碼解析,分享了相關(guān)代碼示例,小編覺(jué)得還是挺不錯(cuò)的,具有一定借鑒價(jià)值,需要的朋友可以參考下
    2018-01-01
  • Python基本數(shù)據(jù)類(lèi)型之字符串str

    Python基本數(shù)據(jù)類(lèi)型之字符串str

    字符串是編程中最重要的數(shù)據(jù)類(lèi)型,也是最常見(jiàn)的,今天小編抽空給大家講解下Python基本數(shù)據(jù)類(lèi)型之字符串str的實(shí)例代碼,感興趣的朋友跟隨小編一起看看吧
    2021-07-07
  • 詳解Python用戶(hù)登錄接口的方法

    詳解Python用戶(hù)登錄接口的方法

    這篇文章主要介紹了Python用戶(hù)登錄接口的方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-04-04
  • Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法

    Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法

    這篇文章主要介紹了Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法,需要的朋友可以參考下
    2019-07-07
  • Python編程基礎(chǔ)之類(lèi)和對(duì)象

    Python編程基礎(chǔ)之類(lèi)和對(duì)象

    這篇文章主要為大家詳細(xì)介紹了Python的類(lèi)和對(duì)象,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2022-01-01
  • Python 數(shù)據(jù)可視化之Bokeh詳解

    Python 數(shù)據(jù)可視化之Bokeh詳解

    這篇文章主要介紹了Python數(shù)據(jù)可視化庫(kù)Bokeh的使用總結(jié),小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2021-11-11

最新評(píng)論