python內(nèi)置了許多非常有用的數(shù)據(jù)結(jié)構(gòu)，比如列表(list)、集合(set)以及字典(dictionary)。就絕大部分情況而言，我們可以直接使用這些數(shù)據(jù)結(jié)構(gòu)。但是，通常我們還需要考慮比如搜索、排序、排列以及篩選等這一類常見的問題。

本篇文章將介紹3種常見的數(shù)據(jù)結(jié)構(gòu)和同數(shù)據(jù)有關(guān)的算法。此外，在collections模塊中也包含了針對各種數(shù)據(jù)結(jié)構(gòu)的解決方案。

1.將序列分解為單獨(dú)的變量

(1)問題

我們有一個包含N個元素的元組或序列，現(xiàn)在想將它分解為N個單獨(dú)的變量。

(2)解決方案

任何序列(或可迭代的對象)都可以通過一個簡單的賦值操作來分解為單獨(dú)的變量。唯一的要求是變量的總數(shù)和結(jié)構(gòu)要與序列相吻合。例如：

>>>p=(4,5)

>>>x,y=p

>>>x

4

>>>y

5

>>>

>>>data=['ACME',50,91.1,(2012,12,21)]

>>>name,shares,price,date=data

>>>name

'ACME'

>>>date

(2012,12,21)

>>>name,shares,price,(year,mon,day)=data

>>>name

'ACME'

>>>year

2012

>>>mon

12

>>>day

21

>>>

如果元素的數(shù)量不匹配，將得到一個錯誤提示。例如：

>>>p=(4,5)

>>>x,y,z=p

Traceback(mostrecentcalllast):

File"",line1,in

ValueError:needmorethan2valuestounpack

>>>

(3)討論

實(shí)際上不僅僅只是元組或列表，只要對象恰好是可迭代的，那么就可以執(zhí)行分解操作。這包括字符串、文件、迭代器以及生成器。比如：

>>>s='Hello'

>>>a,b,c,d,e=s

>>>a

'H'

>>>b

'e'

>>>e

'o'

>>>

當(dāng)做分解操作時(shí)，有時(shí)候可能想丟棄某些特定的值。Python并沒有提供特殊的語法來實(shí)現(xiàn)這一點(diǎn)，但是通?？梢赃x一個用不到的變量名，以此來作為要丟棄的值的名稱。例如：

>>>data=['ACME',50,91.1,(2012,12,21)]

>>>_,shares,price,_=data

>>>shares

50

>>>price

91.1

>>>

但是請確保選擇的變量名沒有在其他地方用到過。

2.從任意長度的可迭代對象中分解元素

(1)問題

需要從某個可迭代對象中分解出N個元素，但是這個可迭代對象的長度可能超過N，這會導(dǎo)致出現(xiàn)“分解的值過多(toomanyvaluestounpack)”的異常。

(2)解決方案

Python的“*表達(dá)式”可以用來解決這個問題。例如，假設(shè)開設(shè)了一門課程，并決定在期末的作業(yè)成績中去掉第一個和最后一個，只對中間剩下的成績做平均分統(tǒng)計(jì)。如果只有4個成績，也許可以簡單地將4個都分解出來，但是如果有24個呢?*表達(dá)式使這一切都變得簡單：

defdrop_first_last(grades):

first,*middle,last=grades

returnavg(middle)

另一個用例是假設(shè)有一些用戶記錄，記錄由姓名和電子郵件地址組成，后面跟著任意數(shù)量的電話號碼。則可以像這樣分解記錄：

>>>record=('Dave','dave@example.com','773-555-1212','847-555-1212')

>>>name,email,*phone_numbers=user_record

>>>name

'Dave'

>>>email

'dave@example.com'

>>>phone_numbers

['773-555-1212','847-555-1212']

>>>

不管需要分解出多少個電話號碼(甚至沒有電話號碼)，變量phone_numbers都一直是列表，而這是毫無意義的。如此一來，對于任何用到了變量phone_numbers的代碼都不必對它可能不是一個列表的情況負(fù)責(zé)，或者額外做任何形式的類型檢查。

由*修飾的變量也可以位于列表的第一個位置。例如，比方說用一系列的值來代表公司過去8個季度的銷售額。如果想對最近一個季度的銷售額同前7個季度的平均值做比較，可以這么做：

*trailing_qtrs,current_qtr=sales_record

trailing_avg=sum(trailing_qtrs)/len(trailing_qtrs)

returnavg_comparison(trailing_avg,current_qtr)

從Python解釋器的角度來看，這個操作是這樣的：

>>>*trailing,current=[10,8,7,1,9,5,10,3]

>>>trailing

[10,8,7,1,9,5,10]

>>>current

3

(3)討論

對于分解未知或任意長度的可迭代對象，這種擴(kuò)展的分解操作可謂是量身定做的工具。通常，這類可迭代對象中會有一些已知的組件或模式(例如，元素1之后的所有內(nèi)容都是電話號碼)，利用*表達(dá)式分解可迭代對象使得開發(fā)者能夠輕松利用這些模式，而不必在可迭代對象中做復(fù)雜花哨的操作才能得到相關(guān)的元素。

*式的語法在迭代一個變長的元組序列時(shí)尤其有用。例如，假設(shè)有一個帶標(biāo)記的元組序列：

records=[

('foo',1,2),

('bar','hello'),

('foo',3,4),

]

defdo_foo(x,y):

print('foo',x,y)

defdo_bar(s):

print('bar',s)

fortag,*argsinrecords:

iftag=='foo':

do_foo(*args)

eliftag=='bar':

do_bar(*args)

當(dāng)和某些特定的字符串處理操作相結(jié)合，比如做拆分(splitting)操作時(shí)，這種*式的語法所支持的分解操作也非常有用。例如：

>>>line='nobody:*:-2:-2:UnprivilegedUser:/var/empty:/usr/bin/false'

>>>uname,*fields,homedir,sh=line.split(':')

>>>uname

'nobody'

>>>homedir

'/var/empty'

>>>sh

'/usr/bin/false'

>>>

有時(shí)候可能想分解出某些值然后丟棄它們。在分解的時(shí)候，不能只是指定一個單獨(dú)的*，但是可以使用幾個常用來表示待丟棄值的變量名，比如_或者ign(ignored)。例如：

>>>record=('ACME',50,123.45,(12,18,2012))

>>>name,*_,(*_,year)=record

>>>name

'ACME'

>>>year

2012

>>>

*分解操作和各種函數(shù)式語言中的列表處理功能有著一定的相似性。例如，如果有一個列表，可以像下面這樣輕松將其分解為頭部和尾部：

>>>items=[1,10,7,4,5,9]

>>>head,*tail=items

>>>head

1

>>>tail

[10,7,4,5,9]

>>>

在編寫執(zhí)行這類拆分功能的函數(shù)時(shí)，人們可以假設(shè)這是為了實(shí)現(xiàn)某種精巧的遞歸算法。例如：

>>>defsum(items):

...head,*tail=items

...returnhead+sum(tail)iftailelsehead

...

>>>sum(items)

36

>>>

但是請注意，遞歸真的不算是Python的強(qiáng)項(xiàng)，這是因?yàn)槠鋬?nèi)在的遞歸限制所致。因此，最后一個例子在實(shí)踐中沒太大的意義，只不過是一點(diǎn)學(xué)術(shù)上的好奇罷了。

3.保存最后N個元素

(1)問題

我們希望在迭代或是其他形式的處理過程中對最后幾項(xiàng)記錄做一個有限的歷史記錄統(tǒng)計(jì)。

(2)解決方案

保存有限的歷史記錄可算是collections.deque的完美應(yīng)用場景了。例如，下面的代碼對一系列文本行做簡單的文本匹配操作，當(dāng)發(fā)現(xiàn)有匹配時(shí)就輸出當(dāng)前的匹配行以及最后檢查過的N行文本。

fromcollectionsimportdeque

defsearch(lines,pattern,history=5):

previous_lines=deque(maxlen=history)

forlineinlines:

ifpatterninline:

yieldline,previous_lines

previous_lines.append(line)

#Exampleuseonafile

if__name__=='__main__':

withopen('somefile.txt')asf:

forline,prevlinesinsearch(f,'python',5):

forplineinprevlines:

print(pline,end='')

print(line,end='')

print('-'*20)

(3)討論

如同上面的代碼片段中所做的一樣，當(dāng)編寫搜索某項(xiàng)記錄的代碼時(shí)，通常會用到含有yield關(guān)鍵字的生成器函數(shù)。這將處理搜索過程的代碼和使用搜索結(jié)果的代碼成功解耦開來。如果對生成器還不熟悉，請參見4.3節(jié)。

deque(maxlen=N)創(chuàng)建了一個固定長度的隊(duì)列。當(dāng)有新記錄加入而隊(duì)列已滿時(shí)會自動移除最老的那條記錄。例如：

>>>q=deque(maxlen=3)

>>>q.append(1)

>>>q.append(2)

>>>q.append(3)

>>>q

deque([1,2,3],maxlen=3)

>>>q.append(4)

>>>q

deque([2,3,4],maxlen=3)

>>>q.append(5)

>>>q

deque([3,4,5],maxlen=3)

盡管可以在列表上手動完成這樣的操作(append、del)，但隊(duì)列這種解決方案要優(yōu)雅得多，運(yùn)行速度也快得多。

更普遍的是，當(dāng)需要一個簡單的隊(duì)列結(jié)構(gòu)時(shí)，deque可祝你一臂之力。如果不指定隊(duì)列的大小，也就得到了一個無界限的隊(duì)列，可以在兩端執(zhí)行添加和彈出操作，例如：

>>>q=deque()

>>>q.append(1)

>>>q.append(2)

>>>q.append(3)

>>>q

deque([1,2,3])

>>>q.appendleft(4)

>>>q

deque([4,1,2,3])

>>>q.pop()

3

>>>q

deque([4,1,2])

>>>q.popleft()

4

從隊(duì)列兩端添加或彈出元素的復(fù)雜度都是O(1)。這和列表不同，當(dāng)從列表的頭部插入或移除元素時(shí)，列表的復(fù)雜度為O(N)。

以上內(nèi)容為大家介紹了Python編程中3個常用的數(shù)據(jù)結(jié)構(gòu)和算法，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。http://www.parentadvocate.org/