聲明
本文基于Python2.7語(yǔ)言，給出判斷列表是否已排序的多種方法，并在作者的Windows XP主機(jī)(Pentium G630 2.7GHz主頻2GB內(nèi)存)上對(duì)比和分析其性能表現(xiàn)。
一. 問(wèn)題提出
Haskell培訓(xùn)老師提出一個(gè)問(wèn)題：如何判斷列表是否已經(jīng)排序？
排序與否實(shí)際只是相鄰元素間的某種二元關(guān)系，即a->a->Bool。所以第一步可以把二元組列表找出來(lái)；第二步是把這個(gè)函數(shù)作用于每個(gè)元組，然后用and操作。老師給出的實(shí)現(xiàn)代碼如下：
pair lst = zip lst ( tail lst )
sorted lst predict = and [ predict x y | (x,y) <- pair lst]
Haskell中，等號(hào)前面是函數(shù)的名稱(chēng)和參數(shù)，后面是函數(shù)的定義體。pair函數(shù)將列表lst錯(cuò)位一下(tail除去列表的第一個(gè)元素)后，和原列表在zip的作用下形成前后相鄰元素二元組列表。predict函數(shù)接受兩個(gè)數(shù)字，根據(jù)大小返回True或False。and對(duì)類(lèi)型為[Bool]的列表中所有元素求與，其語(yǔ)義類(lèi)似Python的all()函數(shù)。
隨后，老師請(qǐng)大家思考性能問(wèn)題。作者提出，若準(zhǔn)確性要求不高，可生成三組隨機(jī)數(shù)排序后作為下標(biāo)，提取原列表相應(yīng)的三組元素組成三個(gè)新的子列表("采樣")。若判斷三個(gè)子列表遵循同樣的排序規(guī)則時(shí)，則認(rèn)為原列表已排序。當(dāng)列表很大且前段已排序時(shí)，選取適當(dāng)數(shù)目的隨機(jī)數(shù)，可在保障一定準(zhǔn)確率的同時(shí)顯著地降低運(yùn)算規(guī)模。
此外，實(shí)際應(yīng)用中還應(yīng)考慮數(shù)據(jù)來(lái)源。例如，Python語(yǔ)言的os.listdir()方法在Windows系統(tǒng)中返回的列表?xiàng)l目滿足字母序，在Linux系統(tǒng)中則返回亂序條目。因此，若判斷系統(tǒng)平臺(tái)(os.platform)為win32，則條目必然已經(jīng)排序。
為對(duì)比驗(yàn)證隨機(jī)采樣方式的可行性，作者先在網(wǎng)上搜集判斷列表排序的現(xiàn)有方法，主要參考Stack Overflow網(wǎng)站上"Pythonic way to check if a list is sorted or not"問(wèn)題的答案，并在本文第二節(jié)給出相關(guān)的代碼示例。注意，本文所述的"排序"不要求嚴(yán)格排序，即相鄰元素允許相等。例如，[1,2,2,3]視為升序，[3,3,2,2]視為降序。
二. 代碼實(shí)現(xiàn)
本節(jié)判斷列表排序的函數(shù)名格式為IsListSorted_XXX()。為簡(jiǎn)潔起見(jiàn)，除代碼片段及其輸出外，一律以_XXX()指代。
2.1 guess
def IsListSorted_guess(lst):
listLen = len(lst)
if listLen <= 1:
return True
#由首個(gè)元素和末尾元素猜測(cè)可能的排序規(guī)則
if lst[0] == lst[-1]: #列表元素相同
for elem in lst:
if elem != lst[0]: return False
elif lst[0] < lst[-1]: #列表元素升序
for i, elem in enumerate(lst[1:]):
if elem < lst[i]: return False
else: #列表元素降序
for i, elem in enumerate(lst[1:]):
if elem > lst[i]: return False
return True
_guess()是最通用的實(shí)現(xiàn)，幾乎與語(yǔ)言無(wú)關(guān)。值得注意的是，該函數(shù)內(nèi)會(huì)猜測(cè)給定列表可能的排序規(guī)則，因此無(wú)需外部調(diào)用者指明排序規(guī)則。
2.2 sorted
def IsListSorted_sorted(lst):
return sorted(lst) == lst or sorted(lst, reverse=True) == lst
_sorted()使用Python內(nèi)置函數(shù)sorted()。由于sorted()會(huì)對(duì)未排序的列表排序，_sorted()函數(shù)主要適用于已排序列表。
若想判斷列表未排序后再對(duì)其排序，不如直接調(diào)用列表的sort()方法，因?yàn)樵摲椒▋?nèi)部會(huì)判斷列表是否排序。對(duì)于已排序列表，該方法的時(shí)間復(fù)雜度為線性階O(n)――判斷為O(n)而排序?yàn)镺(nlgn)。
2.3 for-loop
def IsListSorted_forloop(lst, key=lambda x, y: x <= y):
for i, elem in enumerate(lst[1:]): #注意，enumerate默認(rèn)迭代下標(biāo)從0開(kāi)始
if not key(lst[i], elem): #if elem > lst[i]更快，但通用性差
return False
return True
無(wú)論列表是否已排序，本函數(shù)的時(shí)間復(fù)雜度均為線性階O(n)。注意，參數(shù)key表明缺省的排序規(guī)則為升序。
2.4 all
def IsListSorted_allenumk(lst, key=lambda x, y: x <= y):
return all(key(lst[i], elem) for i, elem in enumerate(lst[1:]))
import operator
def IsListSorted_allenumo(lst, oCmp=operator.le):
return all(oCmp(lst[i], elem) for i, elem in enumerate(lst[1:]))
def IsListSorted_allenumd(lst):
return all((lst[i] <= elem) for i, elem in enumerate(lst[1:]))
def IsListSorted_allxran(lst, key=lambda x,y: x <= y):
return all(key(lst[i],lst[i+1]) for i in xrange(len(lst)-1))
def IsListSorted_allzip(lst, key=lambda x,y: x <= y):
from itertools import izip #Python 3中zip返回生成器(generator)，而izip被廢棄
return all(key(a, b) for (a, b) in izip(lst[:-1],lst[1:]))
lambda表達(dá)式與operator運(yùn)算符速度相當(dāng)，前者簡(jiǎn)單靈活，后者略為高效(實(shí)測(cè)并不一定)。但兩者速度均不如列表元素直接比較(可能存在調(diào)用開(kāi)銷(xiāo))。亦即，_allenumd()快于_allenumo()快于_allenumk()。
若使用lambda表達(dá)式指示排序規(guī)則，更改規(guī)則時(shí)只需要改變x和y之間的比較運(yùn)算符；若使用operator模塊指示排序規(guī)則，更改規(guī)則時(shí)需要改變對(duì)象比較方法。具體地，lt(x, y)等效于x < y，le(x, y)等效于x <= y，eq(x, y)等效于x == y，ne(x, y)等效于x != y，gt(x, y)等效于x > y，ge(x, y)等效于x >= y。例如，_allenumo()函數(shù)若要嚴(yán)格升序可設(shè)置oCmp=operator.lt。
此外，由all()函數(shù)的幫助信息可知，_allenumk()其實(shí)是_forloop()的等效形式。
2.5 numpy
def IsListSorted_numpy(arr, key=lambda dif: dif >= 0):
import numpy
try:
if arr.dtype.kind == 'u': #無(wú)符號(hào)整數(shù)數(shù)組執(zhí)行np.diff時(shí)存在underflow風(fēng)險(xiǎn)
arr = numpy.int64(lst)
except AttributeError:
pass #無(wú)dtype屬性，非數(shù)組
return (key(numpy.diff(arr))).all() #numpy.diff(x)返回相鄰數(shù)組元素的差值構(gòu)成的數(shù)組
NumPy是用于科學(xué)計(jì)算的Python基礎(chǔ)包，可存儲(chǔ)和處理大型矩陣。它包含一個(gè)強(qiáng)大的N維數(shù)組對(duì)象，比Python自身的嵌套列表結(jié)構(gòu)(nested list structure)高效得多。第三節(jié)的實(shí)測(cè)數(shù)據(jù)表明，_numpy()處理大型列表時(shí)性能非常出色。
在Windows系統(tǒng)中可通過(guò)pip install numpy命令安裝NumPy包，不建議登錄官網(wǎng)下載文件自行安裝。
2.6 reduce
def IsListSorted_reduce(iterable, key=lambda x, y: x <= y):
cmpFunc = lambda x, y: y if key(x, y) else float('inf')
return reduce(cmpFunc, iterable, .0) < float('inf')
reduce實(shí)現(xiàn)是all實(shí)現(xiàn)的變體。累加器(accumulator)中僅存儲(chǔ)最后一個(gè)檢查的列表元素，或者Infinity(若任一元素小于前個(gè)元素值)。
前面2.1~2.5小節(jié)涉及下標(biāo)操作的函數(shù)適用于列表等可迭代對(duì)象(Iterable)。對(duì)于通用迭代器(Iterator)對(duì)象，即可以作用于next()函數(shù)或方法的對(duì)象，可使用_reduce()及后面除_rand()外各小節(jié)的函數(shù)。迭代器的計(jì)算是惰性的，只有在需要返回下一個(gè)數(shù)據(jù)時(shí)才會(huì)計(jì)算，以避免不必要的計(jì)算。而且，迭代器方式無(wú)需像列表那樣切片為兩個(gè)迭代對(duì)象。
2.7 imap
def IsListSorted_itermap(iterable, key=lambda x, y: x <= y):
from itertools import imap, tee
a, b = tee(iterable) #為單個(gè)iterable創(chuàng)建兩個(gè)獨(dú)立的iterator
next(b, None)
return all(imap(key, a, b))
2.8 izip
def IsListSorted_iterzip(iterable, key=lambda x, y: x <= y):
from itertools import tee, izip
a, b = tee(iterable)
next(b, None)
return all(key(x, y) for x, y in izip(a, b))
def pairwise(iterable):
from itertools import tee, izip
a, b = tee(iterable)
next(b, None)
return izip(a, b) #"s -> (s0,s1), (s1,s2), (s2, s3), ..."
def IsListSorted_iterzipf(iterable, key=lambda x, y: x <= y):
return all(key(a, b) for a, b in pairwise(iterable))
第三節(jié)的實(shí)測(cè)數(shù)據(jù)表明，雖然存在外部函數(shù)調(diào)用，_iterzipf()卻比_iterzip()略為高效。
2.9 fast
def IsListSorted_fastd(lst):
it = iter(lst)
try:
prev = it.next()
except StopIteration:
return True
for cur in it:
if prev > cur:
return False
prev = cur
return True
def IsListSorted_fastk(lst, key=lambda x, y: x <= y):
it = iter(lst)
try:
prev = it.next()
except StopIteration:
return True
for cur in it:
if not key(prev, cur):
return False
prev = cur
return True
_fastd()和_fastk()是Stack Overflow網(wǎng)站回答里據(jù)稱(chēng)執(zhí)行最快的。實(shí)測(cè)數(shù)據(jù)表明，在列表未排序時(shí)，它們的性能表現(xiàn)確實(shí)優(yōu)異。
2.10 random
import random
def IsListSorted_rand(lst, randNum=3, randLen=100):
listLen = len(lst)
if listLen <= 1:
return True
#由首個(gè)元素和末尾元素猜測(cè)可能的排序規(guī)則
if lst[0] < lst[-1]: #列表元素升序
key = lambda dif: dif >= 0
else: #列表元素降序或相等
key = lambda dif: dif <= 0
threshold, sortedFlag = 10000, True
import numpy
if listLen <= threshold or listLen <= randLen*2 or not randNum:
return (key(numpy.diff(numpy.array(lst)))).all()
from random import sample
for i in range(randNum):
sortedRandList = sorted(sample(xrange(listLen), randLen))
flag = (key(numpy.diff(numpy.array([lst[x] for x in sortedRandList])))).all()
sortedFlag = sortedFlag and flag
return sortedFlag
_rand()借助隨機(jī)采樣降低運(yùn)算規(guī)模，并融入其他判斷函數(shù)的優(yōu)點(diǎn)。例如，猜測(cè)列表可能的排序規(guī)則，并在隨機(jī)采樣不適合時(shí)使用相對(duì)快速的判斷方式，如NumPy。
通過(guò)line_profiler分析可知，第20行和第21行與randLen有關(guān)，但兩者耗時(shí)接近。因此randLen應(yīng)小于listLen的一半，以抵消sorted開(kāi)銷(xiāo)。除內(nèi)部限制外，用戶可以調(diào)節(jié)隨機(jī)序列個(gè)數(shù)和長(zhǎng)度，如定制單個(gè)但較長(zhǎng)的序列。
注意，_rand()不適用于存在微量異常數(shù)據(jù)的長(zhǎng)列表。因?yàn)檫@些數(shù)據(jù)很可能被隨機(jī)采樣遺漏，從而影響判斷結(jié)果的準(zhǔn)確性。
三. 性能分析
本節(jié)借助Python標(biāo)準(zhǔn)庫(kù)random模塊，生成各種隨機(jī)列表，以對(duì)比和分析上節(jié)列表排序判斷函數(shù)的性能。
可通過(guò)sample()、randint()等方法生成隨機(jī)列表。例如：
>>>import random
>>> random.sample(range(10), 10); random.sample(range(10), 5)
[9, 1, 6, 3, 0, 8, 4, 2, 7, 5]
[1, 2, 5, 6, 0]
>>> rand = [random.randint(1,10) for i in range(10)]; rand
[7, 3, 7, 5, 7, 2, 4, 4, 9, 8]
>>> random.sample(rand, 5); random.sample(rand, 5)
[4, 7, 7, 9, 8]
[3, 9, 2, 5, 7]
>>> randGen = (random.randint(1,10) for i in range(10)); randGen
at 0x0192C878>
sample()方法從列表中隨機(jī)選擇數(shù)字，結(jié)合range()函數(shù)可生產(chǎn)不含重復(fù)元素的隨機(jī)列表；而randint()方法結(jié)合列表解析生成的隨機(jī)列表可能包含重復(fù)元素。Python文檔規(guī)定，首次導(dǎo)入random模塊時(shí)使用當(dāng)前系統(tǒng)時(shí)間作為種子初始化隨機(jī)數(shù)生成器。因此，本文并未顯式地調(diào)用seed()方法設(shè)置種子。
為度量性能表現(xiàn)，定義如下計(jì)時(shí)裝飾器：
from time import clock
TimeList = []
def FuncTimer(repeats=1000):
def decorator(func):
def wrapper(*args, **kwargs):
try:
startTime = clock()
for i in xrange(repeats):
ret = func(*args, **kwargs)
except Exception, e:
print '%s() Error: %s!' %(func.__name__, e)
ret = None
finally: #當(dāng)目標(biāo)函數(shù)發(fā)生異常時(shí)，仍舊輸出計(jì)時(shí)信息
endTime = clock()
timeElasped = (endTime-startTime)*1000.0
msg = '%21s(): %s =>Time Elasped: %.3f msec, repeated %d time(s).' \
%(func.__name__, ret, timeElasped, repeats)
global TimeList; TimeList.append([timeElasped, msg])
return ret
return wrapper
return decorator
def ReportTimer():
global TimeList; TimeList.sort(key=lambda x:x[0])
for entry in TimeList:
print entry[1]
TimeList = [] #Flush
該裝飾器允許對(duì)輸出進(jìn)行排序，以便更直觀地觀察性能。基于該裝飾器，下文將分別測(cè)試不同的排序場(chǎng)景。注意，第二節(jié)各函數(shù)頭部需添加FuncTimer()裝飾。
3.1 列表前段亂序
測(cè)試代碼如下：
def TestHeadUnorderedList():
TEST_NAME = 'HeadUnorderedList'; scale = int(1e5)
List = random.sample(xrange(scale), scale) + range(scale)
print 'Test 1: %s, list len: %d' %(TEST_NAME, len(List))
IsListSorted_guess(List)
IsListSorted_sorted(List)
IsListSorted_allenumk(List)
IsListSorted_allenumo(List)
IsListSorted_allenumd(List)
IsListSorted_allxran(List)
IsListSorted_allzip(List)
IsListSorted_forloop(List)
IsListSorted_itermap(List)
IsListSorted_iterzipf(List)
IsListSorted_iterzip(List)
IsListSorted_reduce(List)
IsListSorted_numpy(numpy.array(List)) #若不先轉(zhuǎn)換為數(shù)組，則耗時(shí)驟增
IsListSorted_fastd(List)
IsListSorted_fastk(List)
ReportTimer()
運(yùn)行輸出如下：
Test 1: HeadUnorderedList, list len: 200
IsListSorted_fastd(): False =>Time Elasped: 0.757 msec, repeated 1000 time(s).
IsListSorted_fastk(): False =>Time Elasped: 1.091 msec, repeated 1000 time(s).
IsListSorted_forloop(): False =>Time Elasped: 2.080 msec, repeated 1000 time(s).
IsListSorted_guess(): False =>Time Elasped: 2.123 msec, repeated 1000 time(s).
IsListSorted_allxran(): False =>Time Elasped: 2.255 msec, repeated 1000 time(s).
IsListSorted_allenumd(): False =>Time Elasped: 2.672 msec, repeated 1000 time(s).
IsListSorted_allenumo(): False =>Time Elasped: 3.021 msec, repeated 1000 time(s).
IsListSorted_allenumk(): False =>Time Elasped: 3.207 msec, repeated 1000 time(s).
IsListSorted_itermap(): False =>Time Elasped: 5.845 msec, repeated 1000 time(s).
IsListSorted_allzip(): False =>Time Elasped: 7.793 msec, repeated 1000 time(s).
IsListSorted_iterzip(): False =>Time Elasped: 9.667 msec, repeated 1000 time(s).
IsListSorted_iterzipf(): False =>Time Elasped: 9.969 msec, repeated 1000 time(s).
IsListSorted_numpy(): False =>Time Elasped: 16.203 msec, repeated 1000 time(s).
IsListSorted_sorted(): False =>Time Elasped: 45.742 msec, repeated 1000 time(s).
IsListSorted_reduce(): False =>Time Elasped: 145.447 msec, repeated 1000 time(s).
Test 1: HeadUnorderedList, list len: 200000
IsListSorted_fastd(): False =>Time Elasped: 0.717 msec, repeated 1000 time(s).
IsListSorted_fastk(): False =>Time Elasped: 0.876 msec, repeated 1000 time(s).
IsListSorted_allxran(): False =>Time Elasped: 2.104 msec, repeated 1000 time(s).
IsListSorted_itermap(): False =>Time Elasped: 6.062 msec, repeated 1000 time(s).
IsListSorted_iterzip(): False =>Time Elasped: 7.244 msec, repeated 1000 time(s).
IsListSorted_iterzipf(): False =>Time Elasped: 8.491 msec, repeated 1000 time(s).
IsListSorted_numpy(): False =>Time Elasped: 801.916 msec, repeated 1000 time(s).
IsListSorted_forloop(): False =>Time Elasped: 2924.755 msec, repeated 1000 time(s).
IsListSorted_guess(): False =>Time Elasped: 2991.756 msec, repeated 1000 time(s).
IsListSorted_allenumo(): False =>Time Elasped: 3025.864 msec, repeated 1000 time(s).
IsListSorted_allenumk(): False =>Time Elasped: 3062.792 msec, repeated 1000 time(s).
IsListSorted_allenumd(): False =>Time Elasped: 3190.896 msec, repeated 1000 time(s).
IsListSorted_allzip(): False =>Time Elasped: 6586.183 msec, repeated 1000 time(s).
IsListSorted_sorted(): False =>Time Elasped: 119974.955 msec, repeated 1000 time(s).
IsListSorted_reduce(): False =>Time Elasped: 154747.659 msec, repeated 1000 time(s).
可見(jiàn)，對(duì)于前段亂序的列表，無(wú)論其長(zhǎng)短_fastd()和_fastk()的表現(xiàn)均為最佳。對(duì)于未排序列表，_sorted()需要進(jìn)行排序，故性能非常差。然而，_reduce()性能最差。
實(shí)際上除_guess()和_sorted()外，其他函數(shù)都按升序檢查列表。為安全起見(jiàn)，可仿照_guess()實(shí)現(xiàn)，先猜測(cè)排序方式，再進(jìn)一步檢查。
因?yàn)槎塘斜砗臅r(shí)差異大多可以忽略，后續(xù)測(cè)試將不再包含短列表(但作者確實(shí)測(cè)試過(guò))，僅關(guān)注長(zhǎng)列表。除非特別說(shuō)明，列表長(zhǎng)度為10萬(wàn)級(jí)，重復(fù)計(jì)時(shí)1000次。
3.2 列表中段亂序
測(cè)試代碼及結(jié)果如下：
def TestMiddUnorderedList():
TEST_NAME = 'MiddUnorderedList'; scale = int(1e5)
List = range(scale) + random.sample(xrange(scale), scale) + range(scale)
print 'Test 2: %s, list len: %d' %(TEST_NAME, len(List))
IsListSorted_numpy(numpy.array(List)) # 1572.295 msec
IsListSorted_guess(List) # 14540.637 msec
IsListSorted_itermap(List) # 21013.096 msec
IsListSorted_fastk(List) # 23840.582 msec
IsListSorted_allxran(List) # 31014.215 msec
IsListSorted_iterzip(List) # 33386.059 msec
IsListSorted_forloop(List) # 34228.006 msec
IsListSorted_allenumk(List) # 34416.802 msec
IsListSorted_allzip(List) # 42370.528 msec
IsListSorted_sorted(List) # 142592.756 msec
IsListSorted_reduce(List) # 187514.967 msec
ReportTimer()
為節(jié)省篇幅，已根據(jù)運(yùn)行輸出調(diào)整函數(shù)的調(diào)用順序。下文也作如此處理。
3.3 列表后段亂序
測(cè)試代碼及結(jié)果如下：
def TestTailUnorderedList():
TEST_NAME = 'TailUnorderedList'; scale = int(1e5)
List = range(scale, 0, -1) + random.sample(xrange(scale), scale)
print 'Test 3: %s, list len: %d' %(TEST_NAME, len(List))
IsListSorted_numpy(numpy.array(List), key=lambda dif: dif <= 0) # 980.789 msec
IsListSorted_guess(List) # 13273.862 msec
IsListSorted_itermap(List, key=lambda x, y: x >= y) # 21603.315 msec
IsListSorted_fastk(List, key=lambda x, y: x >= y) # 24183.548 msec
IsListSorted_allxran(List, key=lambda x, y: x >= y) # 32850.254 msec
IsListSorted_forloop(List, key=lambda x, y: x >= y) # 33918.848 msec
IsListSorted_iterzip(List, key=lambda x, y: x >= y) # 34505.809 msec
IsListSorted_allenumk(List, key=lambda x, y: x >= y) # 35631.625 msec
IsListSorted_allzip(List, key=lambda x, y: x >= y) # 40076.330 msec
ReportTimer()
3.4 列表完全亂序
測(cè)試代碼及結(jié)果如下：
def TestUnorderedList():
TEST_NAME = 'UnorderedList'; scale = int(1e5)
List = random.sample(xrange(scale), scale)
print 'Test 4: %s, list len: %d' %(TEST_NAME, len(List))
IsListSorted_fastk(List) # 0.856 msec
IsListSorted_allxran(List) # 3.438 msec
IsListSorted_iterzip(List) # 7.233 msec
IsListSorted_itermap(List) # 7.595 msec
IsListSorted_numpy(numpy.array(List)) # 207.222 msec
IsListSorted_allenumk(List) # 953.423 msec
IsListSorted_guess(List) # 1023.575 msec
IsListSorted_forloop(List) # 1076.986 msec
IsListSorted_allzip(List) # 2062.821 msec
ReportTimer()
3.5 列表元素相同
測(cè)試代碼及結(jié)果如下：
```python def TestSameElemList(): TEST_NAME = 'SameElemList'; scale = int(1e5) List = [5]*scale print 'Test 5: %s, list len: %d' %(TEST_NAME, len(List)) IsListSorted_numpy(numpy.array(List)) # 209.324 msec IsListSorted_sorted(List) # 2760.139 msec IsListSorted_guess(List) # 5843.942 msec IsListSorted_itermap(List) # 20609.704 msec IsListSorted_fastk(List) # 23035.760 msec IsListSorted_forloop(List) # 29043.206 msec IsListSorted_allenumk(List) # 29553.716 msec IsListSorted_allxran(List) # 30348.549 msec IsListSorted_iterzip(List) # 32806.217 msec ReportTimer()
3.6 列表升序
測(cè)試代碼及結(jié)果如下：
def TestAscendingList():
TEST_NAME = 'AscendingList'; scale = int(1e5)
List = range(scale)
print 'Test 6: %s, list len: %d' %(TEST_NAME, len(List))
IsListSorted_numpy(numpy.array(List)) # 209.217 msec
IsListSorted_sorted(List) # 2845.166 msec
IsListSorted_fastd(List) # 5977.520 msec
IsListSorted_guess(List) # 10408.204 msec
IsListSorted_allenumd(List) # 15812.754 msec
IsListSorted_itermap(List) # 21244.476 msec
IsListSorted_fastk(List) # 23900.196 msec
IsListSorted_allenumo(List) # 28607.724 msec
IsListSorted_forloop(List) # 30075.538 msec
IsListSorted_allenumk(List) # 30274.017 msec
IsListSorted_allxran(List) # 31126.404 msec
IsListSorted_reduce(List) # 32940.108 msec
IsListSorted_iterzip(List) # 34188.312 msec
IsListSorted_iterzipf(List) # 34425.097 msec
IsListSorted_allzip(List) # 37967.447 msec
ReportTimer()
可見(jiàn)，列表已排序時(shí)，_sorted()的性能較占優(yōu)勢(shì)。
3.7 列表降序
剔除不支持降序的函數(shù)，測(cè)試代碼及結(jié)果如下：
def TestDescendingList():
TEST_NAME = 'DescendingList'; scale = int(1e2)
List = range(scale, 0, -1)
print 'Test 7: %s, list len: %d' %(TEST_NAME, len(List))
IsListSorted_numpy(numpy.array(List), key=lambda dif: dif <= 0) # 209.318 msec
IsListSorted_sorted(List) # 5707.067 msec
IsListSorted_guess(List) # 10549.928 msec
IsListSorted_itermap(List, key=lambda x, y: x >= y) # 21529.547 msec
IsListSorted_fastk(List, key=lambda x, y: x >= y) # 24264.465 msec
import operator; IsListSorted_allenumo(List, oCmp=operator.ge) # 28093.035 msec
IsListSorted_forloop(List, key=lambda x, y: x >= y) # 30745.943 msec
IsListSorted_allenumk(List, key=lambda x, y: x >= y) # 32696.205 msec
IsListSorted_allxran(List, key=lambda x, y: x >= y) # 33431.473 msec
IsListSorted_allzip(List, key=lambda x, y: x >= y) # 34837.019 msec
IsListSorted_iterzip(List, key=lambda x, y: x >= y) # 35237.475 msec
IsListSorted_reduce(List, key=lambda x, y: x >= y) # 37035.270 msec
ReportTimer()
3.8 迭代器測(cè)試
參數(shù)為列表的函數(shù)，需要先將列表???過(guò)iter()函數(shù)轉(zhuǎn)換為迭代器。注意，當(dāng)iterable參數(shù)為iterator時(shí)，只能計(jì)時(shí)一次，因?yàn)樵摯螆?zhí)行將用盡迭代器。
測(cè)試代碼如下：
def TestIter():
TEST_NAME = 'Iter'; scale = int(1e7)
List = range(scale) #升序
# List = random.sample(xrange(scale), scale) #亂序
print 'Test 8: %s, list len: %d' %(TEST_NAME, len(List))
iterL = iter(List); IsListSorted_guess(list(iterL))
iterL = iter(List); IsListSorted_sorted(iterL)
iterL = iter(List); IsListSorted_itermap(iterL)
iterL = iter(List); IsListSorted_iterzipf(iterL)
iterL = iter(List); IsListSorted_iterzip(iterL)
iterL = iter(List); IsListSorted_reduce(iterL)
iterL = iter(List); IsListSorted_fastd(iterL)
iterL = iter(List); IsListSorted_fastk(iterL, key=lambda x, y: x >= y)
ReportTimer()
運(yùn)行結(jié)果如下：
Test 8: Iter, list len: 10000000 ---升序
IsListSorted_fastd(): True =>Time Elasped: 611.028 msec, repeated 1 time(s).
IsListSorted_sorted(): False =>Time Elasped: 721.751 msec, repeated 1 time(s).
IsListSorted_guess(): True =>Time Elasped: 1142.065 msec, repeated 1 time(s).
IsListSorted_itermap(): True =>Time Elasped: 2097.696 msec, repeated 1 time(s).
IsListSorted_fastk(): True =>Time Elasped: 2337.233 msec, repeated 1 time(s).
IsListSorted_reduce(): True =>Time Elasped: 3307.361 msec, repeated 1 time(s).
IsListSorted_iterzipf(): True =>Time Elasped: 3354.034 msec, repeated 1 time(s).
IsListSorted_iterzip(): True =>Time Elasped: 3442.520 msec, repeated 1 time(s).
Test 8: Iter, list len: 10000000 ---亂序
IsListSorted_fastk(): False =>Time Elasped: 0.004 msec, repeated 1 time(s).
IsListSorted_fastd(): False =>Time Elasped: 0.010 msec, repeated 1 time(s).
IsListSorted_iterzip(): False =>Time Elasped: 0.015 msec, repeated 1 time(s).
IsListSorted_itermap(): False =>Time Elasped: 0.055 msec, repeated 1 time(s).
IsListSorted_iterzipf(): False =>Time Elasped: 0.062 msec, repeated 1 time(s).
IsListSorted_guess(): False =>Time Elasped: 736.810 msec, repeated 1 time(s).
IsListSorted_reduce(): False =>Time Elasped: 8919.611 msec, repeated 1 time(s).
IsListSorted_sorted(): False =>Time Elasped: 12273.018 msec, repeated 1 time(s).
其中，_itermap()、_iterzip()、_iterzipf()、_reduce()、_fastd()、_fastk()可直接判斷迭代器是否已排序。其他函數(shù)需將迭代器轉(zhuǎn)換為列表后才能處理。_sorted()雖然接受迭代器參數(shù)，但sorted()返回列表，故無(wú)法正確判斷迭代器順序。
3.9 隨機(jī)采樣測(cè)試
綜合以上測(cè)試，可知_fastk()和_numpy()性能較為突出，而且_rand()內(nèi)置numpy方式。因此，以_fastk()和_numpy()為參照對(duì)象，測(cè)試代碼如下(計(jì)時(shí)1次)：
def TestRandList():
scale = int(1e6)
List = random.sample(xrange(scale), scale) + range(scale)
print 'Test 1: %s, list len: %d' %('HeadUnorderedList', len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = range(scale) + random.sample(xrange(scale), scale) + range(scale)
print 'Test 2: %s, list len: %d' %('MiddUnorderedList', len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = range(scale, 0, -1) + random.sample(xrange(scale), scale)
print 'Test 3: %s, list len: %d' %('TailUnorderedList', len(List))
IsListSorted_fastk(List, key=lambda x, y: x >= y)
IsListSorted_numpy(numpy.array(List), key=lambda dif: dif <= 0)
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = [random.randint(1,scale) for i in xrange(scale)] #random.sample(xrange(scale), scale)
print 'Test 4: %s, list len: %d' %('UnorderedList', len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = [5]*scale
print 'Test 5: %s, list len: %d' %('SameElemList', len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = range(scale)
print 'Test 6: %s, list len: %d' %('AscendingList', len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = range(scale, 0, -1)
print 'Test 7: %s, list len: %d' %('DescendingList', len(List))
IsListSorted_fastk(List, key=lambda x, y: x >= y)
IsListSorted_numpy(numpy.array(List), key=lambda dif: dif <= 0)
IsListSorted_rand(List, randNum=1)
ReportTimer()
List = range(scale, 0, -1); List[scale/2]=0
print 'Test 8: %s, list len: %d' %('MiddleNotchList', len(List))
IsListSorted_fastk(List, key=lambda x, y: x >= y)
IsListSorted_numpy(numpy.array(List), key=lambda dif: dif <= 0)
IsListSorted_rand(List, randNum=1)
IsListSorted_rand(List, randNum=1, randLen=scale/2)
ReportTimer()
運(yùn)行輸出如下：
Test 1: HeadUnorderedList, list len: 2000000
IsListSorted_fastk(): False =>Time Elasped: 0.095 msec, repeated 1 time(s).
IsListSorted_rand(): False =>Time Elasped: 0.347 msec, repeated 1 time(s).
IsListSorted_numpy(): False =>Time Elasped: 7.893 msec, repeated 1 time(s).
Test 2: MiddUnorderedList, list len: 3000000
IsListSorted_rand(): False =>Time Elasped: 0.427 msec, repeated 1 time(s).
IsListSorted_numpy(): False =>Time Elasped: 11.868 msec, repeated 1 time(s).
IsListSorted_fastk(): False =>Time Elasped: 210.842 msec, repeated 1 time(s).
Test 3: TailUnorderedList, list len: 2000000
IsListSorted_rand(): False =>Time Elasped: 0.355 msec, repeated 1 time(s).
IsListSorted_numpy(): False =>Time Elasped: 7.548 msec, repeated 1 time(s).
IsListSorted_fastk(): False =>Time Elasped: 280.416 msec, repeated 1 time(s).
Test 4: UnorderedList, list len: 1000000
IsListSorted_fastk(): False =>Time Elasped: 0.074 msec, repeated 1 time(s).
IsListSorted_rand(): False =>Time Elasped: 0.388 msec, repeated 1 time(s).
IsListSorted_numpy(): False =>Time Elasped: 3.757 msec, repeated 1 time(s).
Test 5: SameElemList, list len: 1000000
IsListSorted_rand(): True =>Time Elasped: 0.304 msec, repeated 1 time(s).
IsListSorted_numpy(): True =>Time Elasped: 3.955 msec, repeated 1 time(s).
IsListSorted_fastk(): True =>Time Elasped: 210.977 msec, repeated 1 time(s).
Test 6: AscendingList, list len: 1000000
IsListSorted_rand(): True =>Time Elasped: 0.299 msec, repeated 1 time(s).
IsListSorted_numpy(): True =>Time Elasped: 4.822 msec, repeated 1 time(s).
IsListSorted_fastk(): True =>Time Elasped: 214.171 msec, repeated 1 time(s).
Test 7: DescendingList, list len: 1000000
IsListSorted_rand(): True =>Time Elasped: 0.336 msec, repeated 1 time(s).
IsListSorted_numpy(): True =>Time Elasped: 3.867 msec, repeated 1 time(s).
IsListSorted_fastk(): True =>Time Elasped: 279.322 msec, repeated 1 time(s).
Test 8: MiddleNotchList, list len: 1000000
IsListSorted_rand(): True =>Time Elasped: 0.387 msec, repeated 1 time(s).
IsListSorted_numpy(): False =>Time Elasped: 4.792 msec, repeated 1 time(s).
IsListSorted_rand(): False =>Time Elasped: 78.903 msec, repeated 1 time(s).
IsListSorted_fastk(): False =>Time Elasped: 110.444 msec, repeated 1 time(s).
可見(jiàn)，在絕大部分測(cè)試場(chǎng)景中，_rand()性能均為最佳，且不失正確率。注意測(cè)試8，當(dāng)降序列表中間某個(gè)元素被置0(開(kāi)槽)時(shí)，隨機(jī)采樣很容易遺漏該元素，導(dǎo)致誤判。然而，這種場(chǎng)景在實(shí)際使用中非常罕見(jiàn)。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
