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

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

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

(1)問(wèn)題

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

(2)解決方案

任何序列(或可迭代的對(duì)象)都可以通過(guò)一個(gè)簡(jiǎn)單的賦值操作來(lái)分解為單獨(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ù)量不匹配，將得到一個(gè)錯(cuò)誤提示。例如：

>>>p=(4,5)

>>>x,y,z=p

Traceback(mostrecentcalllast):

File"",line1,in

ValueError:needmorethan2valuestounpack

>>>

(3)討論

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

>>>s='Hello'

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

>>>a

'H'

>>>b

'e'

>>>e

'o'

>>>

當(dāng)做分解操作時(shí)，有時(shí)候可能想丟棄某些特定的值。Python并沒(méi)有提供特殊的語(yǔ)法來(lái)實(shí)現(xiàn)這一點(diǎn)，但是通常可以選一個(gè)用不到的變量名，以此來(lái)作為要丟棄的值的名稱(chēng)。例如：

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

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

>>>shares

50

>>>price

91.1

>>>

但是請(qǐng)確保選擇的變量名沒(méi)有在其他地方用到過(guò)。

2.從任意長(zhǎng)度的可迭代對(duì)象中分解元素

(1)問(wèn)題

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

(2)解決方案

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

defdrop_first_last(grades):

first,*middle,last=grades

returnavg(middle)

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

>>>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']

>>>

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

由*修飾的變量也可以位于列表的第一個(gè)位置。例如，比方說(shuō)用一系列的值來(lái)代表公司過(guò)去8個(gè)季度的銷(xiāo)售額。如果想對(duì)最近一個(gè)季度的銷(xiāo)售額同前7個(gè)季度的平均值做比較，可以這么做：

*trailing_qtrs,current_qtr=sales_record

trailing_avg=sum(trailing_qtrs)/len(trailing_qtrs)

returnavg_comparison(trailing_avg,current_qtr)

從Python解釋器的角度來(lái)看，這個(gè)操作是這樣的：

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

>>>trailing

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

>>>current

3

(3)討論

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

*式的語(yǔ)法在迭代一個(gè)變長(zhǎng)的元組序列時(shí)尤其有用。例如，假設(shè)有一個(gè)帶標(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í)，這種*式的語(yǔ)法所支持的分解操作也非常有用。例如：

>>>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í)候，不能只是指定一個(gè)單獨(dú)的*，但是可以使用幾個(gè)常用來(lái)表示待丟棄值的變量名，比如_或者ign(ignored)。例如：

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

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

>>>name

'ACME'

>>>year

2012

>>>

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

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

>>>head,*tail=items

>>>head

1

>>>tail

[10,7,4,5,9]

>>>

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

>>>defsum(items):

...head,*tail=items

...returnhead+sum(tail)iftailelsehead

...

>>>sum(items)

36

>>>

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

3.保存最后N個(gè)元素

(1)問(wèn)題

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

(2)解決方案

保存有限的歷史記錄可算是collections.deque的完美應(yīng)用場(chǎng)景了。例如，下面的代碼對(duì)一系列文本行做簡(jiǎn)單的文本匹配操作，當(dāng)發(fā)現(xiàn)有匹配時(shí)就輸出當(dāng)前的匹配行以及最后檢查過(guò)的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ě)搜索某項(xiàng)記錄的代碼時(shí)，通常會(huì)用到含有yield關(guān)鍵字的生成器函數(shù)。這將處理搜索過(guò)程的代碼和使用搜索結(jié)果的代碼成功解耦開(kāi)來(lái)。如果對(duì)生成器還不熟悉，請(qǐng)參見(jiàn)4.3節(jié)。

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

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

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

更普遍的是，當(dāng)需要一個(gè)簡(jiǎn)單的隊(duì)列結(jié)構(gòu)時(shí)，deque可祝你一臂之力。如果不指定隊(duì)列的大小，也就得到了一個(gè)無(wú)界限的隊(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個(gè)常用的數(shù)據(jù)結(jié)構(gòu)和算法，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。http://m.2667701.com/