如何生成斐波那契數(shù)列

斐波那契（Fibonacci）數(shù)列是一個(gè)非常簡(jiǎn)單的遞歸數(shù)列，除第一個(gè)和第二個(gè)數(shù)外，任意一個(gè)數(shù)都可由前兩個(gè)數(shù)相加得到。用計(jì)算機(jī)程序輸出斐波那契數(shù)列的前 N 個(gè)數(shù)是一個(gè)非常簡(jiǎn)單的問(wèn)題，許多初學(xué)者都可以輕易寫(xiě)出如下函數(shù)：

清單 1. 簡(jiǎn)單輸出斐波那契數(shù)列前 N 個(gè)數(shù)

實(shí)例

#!/usr/bin/python
# -*- coding: UTF-8 -*-
def fab(max): 
 n, a, b = 0, 0, 1 
 while n < max: 
  print b 
  a, b = b, a + b 
  n = n + 1
fab(5)

執(zhí)行以上代碼，我們可以得到如下輸出：

1
1
2
3
5

結(jié)果沒(méi)有問(wèn)題，但有經(jīng)驗(yàn)的開(kāi)發(fā)者會(huì)指出，直接在 fab 函數(shù)中用 print 打印數(shù)字會(huì)導(dǎo)致該函數(shù)可復(fù)用性較差，因?yàn)?fab 函數(shù)返回 None，其他函數(shù)無(wú)法獲得該函數(shù)生成的數(shù)列。

要提高 fab 函數(shù)的可復(fù)用性，最好不要直接打印出數(shù)列，而是返回一個(gè) List。以下是 fab 函數(shù)改寫(xiě)后的第二個(gè)版本：

清單 2. 輸出斐波那契數(shù)列前 N 個(gè)數(shù)第二版

實(shí)例

#!/usr/bin/python
# -*- coding: UTF-8 -*-
def fab(max): 
 n, a, b = 0, 0, 1 
 L = [] 
 while n < max: 
  L.append(b) 
  a, b = b, a + b 
  n = n + 1 
 return L
for n in fab(5): 
 print n

可以使用如下方式打印出 fab 函數(shù)返回的 List：

1
1
2
3
5

改寫(xiě)后的 fab 函數(shù)通過(guò)返回 List 能滿足復(fù)用性的要求，但是更有經(jīng)驗(yàn)的開(kāi)發(fā)者會(huì)指出，該函數(shù)在運(yùn)行中占用的內(nèi)存會(huì)隨著參數(shù) max 的增大而增大，如果要控制內(nèi)存占用，最好不要用 List

來(lái)保存中間結(jié)果，而是通過(guò) iterable 對(duì)象來(lái)迭代。例如，在 Python2.x 中，代碼：

清單 3. 通過(guò) iterable 對(duì)象來(lái)迭代

for i in range(1000): pass

會(huì)導(dǎo)致生成一個(gè) 1000 個(gè)元素的 List，而代碼：

for i in xrange(1000): pass

則不會(huì)生成一個(gè) 1000 個(gè)元素的 List，而是在每次迭代中返回下一個(gè)數(shù)值，內(nèi)存空間占用很小。因?yàn)?xrange 不返回 List，而是返回一個(gè) iterable 對(duì)象。

利用 iterable 我們可以把 fab 函數(shù)改寫(xiě)為一個(gè)支持 iterable 的 class，以下是第三個(gè)版本的 Fab：

清單 4. 第三個(gè)版本

實(shí)例

#!/usr/bin/python
# -*- coding: UTF-8 -*-
class Fab(object): 
 def __init__(self, max): 
  self.max = max 
  self.n, self.a, self.b = 0, 0, 1 
 def __iter__(self): 
  return self 
 def next(self): 
  if self.n < self.max: 
r = self.b 
self.a, self.b = self.b, self.a + self.b 
self.n = self.n + 1 
return r 
  raise StopIteration()
for n in Fab(5): 
 print n

Fab 類(lèi)通過(guò) next() 不斷返回?cái)?shù)列的下一個(gè)數(shù)，內(nèi)存占用始終為常數(shù)：

1
1
2
3
5

然而，使用 class 改寫(xiě)的這個(gè)版本，代碼遠(yuǎn)遠(yuǎn)沒(méi)有第一版的 fab 函數(shù)來(lái)得簡(jiǎn)潔。如果我們想要保持第一版 fab 函數(shù)的簡(jiǎn)潔性，同時(shí)又要獲得 iterable 的效果，yield 就派上用場(chǎng)了：

清單 5. 使用 yield 的第四版

實(shí)例

#!/usr/bin/python
# -*- coding: UTF-8 -*-
def fab(max): 
 n, a, b = 0, 0, 1 
 while n < max: 
  yield b# 使用 yield
  # print b 
  a, b = b, a + b 
  n = n + 1
for n in fab(5): 
 print n

第四個(gè)版本的 fab 和第一版相比，僅僅把 print b 改為了 yield b，就在保持簡(jiǎn)潔性的同時(shí)獲得了 iterable 的效果。

調(diào)用第四版的 fab 和第二版的 fab 完全一致：

1
1
2
3
5

簡(jiǎn)單地講，yield 的作用就是把一個(gè)函數(shù)變成一個(gè) generator，帶有 yield 的函數(shù)不再是一個(gè)普通函數(shù)，Python 解釋器會(huì)將其視為一個(gè) generator，調(diào)用 fab(5) 不會(huì)執(zhí)行 fab 函數(shù)，而是返回一個(gè) iterable 對(duì)象！在 for 循環(huán)執(zhí)行時(shí)，每次循環(huán)都會(huì)執(zhí)行 fab 函數(shù)內(nèi)部的代碼，執(zhí)行到 yield b 時(shí)，fab 函數(shù)就返回一個(gè)迭代值，下次迭代時(shí)，代碼從 yield b 的下一條語(yǔ)句繼續(xù)執(zhí)行，而函數(shù)的本地變量看起來(lái)和上次中斷執(zhí)行前是完全一樣的，于是函數(shù)繼續(xù)執(zhí)行，直到再次遇到 yield。

也可以手動(dòng)調(diào)用 fab(5) 的 next() 方法（因?yàn)?fab(5) 是一個(gè) generator 對(duì)象，該對(duì)象具有 next() 方法），這樣我們就可以更清楚地看到 fab 的執(zhí)行流程：

清單 6. 執(zhí)行流程

>>>f = fab(5) 
>>> f.next() 
1 
>>> f.next() 
1 
>>> f.next() 
2 
>>> f.next() 
3 
>>> f.next() 
5 
>>> f.next() 
Traceback (most recent call last): 
 File "<stdin>", line 1, in <module> 
StopIteration

當(dāng)函數(shù)執(zhí)行結(jié)束時(shí)，generator 自動(dòng)拋出 StopIteration 異常，表示迭代完成。在 for 循環(huán)里，無(wú)需處理 StopIteration 異常，循環(huán)會(huì)正常結(jié)束。

我們可以得出以下結(jié)論：

一個(gè)帶有 yield 的函數(shù)就是一個(gè) generator，它和普通函數(shù)不同，生成一個(gè) generator 看起來(lái)像函數(shù)調(diào)用，但不會(huì)執(zhí)行任何函數(shù)代碼，直到對(duì)其調(diào)用 next()（在 for 循環(huán)中會(huì)自動(dòng)調(diào)用 next()）才開(kāi)始執(zhí)行。雖然執(zhí)行流程仍按函數(shù)的流程執(zhí)行，但每執(zhí)行到一個(gè) yield 語(yǔ)句就會(huì)中斷，并返回一個(gè)迭代值，下次執(zhí)行時(shí)從 yield 的下一個(gè)語(yǔ)句繼續(xù)執(zhí)行。看起來(lái)就好像一個(gè)函數(shù)在正常執(zhí)行的過(guò)程中被 yield 中斷了數(shù)次，每次中斷都會(huì)通過(guò) yield 返回當(dāng)前的迭代值。

yield 的好處是顯而易見(jiàn)的，把一個(gè)函數(shù)改寫(xiě)為一個(gè) generator 就獲得了迭代能力，比起用類(lèi)的實(shí)例保存狀態(tài)來(lái)計(jì)算下一個(gè) next() 的值，不僅代碼簡(jiǎn)潔，而且執(zhí)行流程異常清晰。

如何判斷一個(gè)函數(shù)是否是一個(gè)特殊的 generator 函數(shù)？可以利用 isgeneratorfunction 判斷：

清單 7. 使用 isgeneratorfunction 判斷

>>>from inspect import isgeneratorfunction 
>>> isgeneratorfunction(fab) 
True

要注意區(qū)分 fab 和 fab(5)，fab 是一個(gè) generator function，而 fab(5) 是調(diào)用 fab 返回的一個(gè) generator，好比類(lèi)的定義和類(lèi)的實(shí)例的區(qū)別：

清單 8. 類(lèi)的定義和類(lèi)的實(shí)例

>>>import types 
>>> isinstance(fab, types.GeneratorType) 
False 
>>> isinstance(fab(5), types.GeneratorType) 
True

fab 是無(wú)法迭代的，而 fab(5) 是可迭代的：

>>>from collections import Iterable 
>>> isinstance(fab, Iterable) 
False 
>>> isinstance(fab(5), Iterable) 
True

每次調(diào)用 fab 函數(shù)都會(huì)生成一個(gè)新的 generator 實(shí)例，各實(shí)例互不影響：

>>>f1 = fab(3) 
>>> f2 = fab(5) 
>>> print 'f1:', f1.next() 
f1: 1 
>>> print 'f2:', f2.next() 
f2: 1 
>>> print 'f1:', f1.next() 
f1: 1 
>>> print 'f2:', f2.next() 
f2: 1 
>>> print 'f1:', f1.next() 
f1: 2 
>>> print 'f2:', f2.next() 
f2: 2 
>>> print 'f2:', f2.next() 
f2: 3 
>>> print 'f2:', f2.next() 
f2: 5

return 的作用

在一個(gè) generator function 中，如果沒(méi)有 return，則默認(rèn)執(zhí)行至函數(shù)完畢，如果在執(zhí)行過(guò)程中 return，則直接拋出 StopIteration 終止迭代。

另一個(gè)例子

另一個(gè) yield 的例子來(lái)源于文件讀取。如果直接對(duì)文件對(duì)象調(diào)用 read() 方法，會(huì)導(dǎo)致不可預(yù)測(cè)的內(nèi)存占用。好的方法是利用固定長(zhǎng)度的緩沖區(qū)來(lái)不斷讀取文件內(nèi)容。通過(guò) yield，我們不再需要編寫(xiě)讀文件的迭代類(lèi)，就可以輕松實(shí)現(xiàn)文件讀取：

清單 9. 另一個(gè) yield 的例子

實(shí)例

def read_file(fpath): 
 BLOCK_SIZE = 1024 
 with open(fpath, 'rb') as f: 
  while True: 
block = f.read(BLOCK_SIZE) 
if block: 
 yield block 
else: 
 return

以上僅僅簡(jiǎn)單介紹了 yield 的基本概念和用法，yield 在 Python 3 中還有更強(qiáng)大的用法，我們會(huì)在后續(xù)文章中討論。

注：本文的代碼均在 Python 2.7 中調(diào)試通過(guò)

總結(jié)

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注本站的更多內(nèi)容!

版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。