Python判断列表是否已排序的各种方法及其性能分析

2024-03-16 18:38:03 39

声明

本文基于Python2.7语言，给出判断列表是否已排序的多种方法，并在作者的WindowsXP主机(PentiumG6302.7GHz主频2GB内存)上对比和分析其性能表现。

一.问题提出

Haskell培训老师提出一个问题：如何判断列表是否已经排序？

排序与否实际只是相邻元素间的某种二元关系，即a->a->Bool。所以第一步可以把二元组列表找出来；第二步是把这个函数作用于每个元组，然后用and操作。老师给出的实现代码如下：

pairlst=ziplst(taillst)
sortedlstpredict=and[predictxy|(x,y)<-pairlst]

Haskell中，等号前面是函数的名称和参数，后面是函数的定义体。pair函数将列表lst错位一下(tail除去列表的第一个元素)后，和原列表在zip的作用下形成前后相邻元素二元组列表。predict函数接受两个数字，根据大小返回True或False。and对类型为[Bool]的列表中所有元素求与，其语义类似Python的all()函数。

随后，老师请大家思考性能问题。作者提出，若准确性要求不高，可生成三组随机数排序后作为下标，提取原列表相应的三组元素组成三个新的子列表("采样")。若判断三个子列表遵循同样的排序规则时，则认为原列表已排序。当列表很大且前段已排序时，选取适当数目的随机数，可在保障一定准确率的同时显著地降低运算规模。

此外，实际应用中还应考虑数据来源。例如，Python语言的os.listdir()方法在Windows系统中返回的列表条目满足字母序，在Linux系统中则返回乱序条目。因此，若判断系统平台(os.platform)为win32，则条目必然已经排序。

为对比验证随机采样方式的可行性，作者先在网上搜集判断列表排序的现有方法，主要参考StackOverflow网站上"Pythonicwaytocheckifalistissortedornot"问题的答案，并在本文第二节给出相关的代码示例。注意，本文所述的"排序"不要求严格排序，即相邻元素允许相等。例如，[1,2,2,3]视为升序，[3,3,2,2]视为降序。

二.代码实现

本节判断列表排序的函数名格式为IsListSorted_XXX()。为简洁起见，除代码片段及其输出外，一律以_XXX()指代。

2.1guess

defIsListSorted_guess(lst):
listLen=len(lst)
iflistLen<=1:
returnTrue
#由首个元素和末尾元素猜测可能的排序规则
iflst[0]==lst[-1]:#列表元素相同
foreleminlst:
ifelem!=lst[0]:returnFalse
eliflst[0]<lst[-1]:#列表元素升序
fori,eleminenumerate(lst[1:]):
ifelem<lst[i]:returnFalse
else:#列表元素降序
fori,eleminenumerate(lst[1:]):
ifelem>lst[i]:returnFalse
returnTrue

_guess()是最通用的实现，几乎与语言无关。值得注意的是，该函数内会猜测给定列表可能的排序规则，因此无需外部调用者指明排序规则。

2.2sorted

defIsListSorted_sorted(lst):
returnsorted(lst)==lstorsorted(lst,reverse=True)==lst

_sorted()使用Python内置函数sorted()。由于sorted()会对未排序的列表排序，_sorted()函数主要适用于已排序列表。
若想判断列表未排序后再对其排序，不如直接调用列表的sort()方法，因为该方法内部会判断列表是否排序。对于已排序列表，该方法的时间复杂度为线性阶O(n)——判断为O(n)而排序为O(nlgn)。

2.3for-loop

defIsListSorted_forloop(lst,key=lambdax,y:x<=y):
fori,eleminenumerate(lst[1:]):#注意，enumerate默认迭代下标从0开始
ifnotkey(lst[i],elem):#ifelem>lst[i]更快，但通用性差
returnFalse
returnTrue

无论列表是否已排序，本函数的时间复杂度均为线性阶O(n)。注意，参数key表明缺省的排序规则为升序。

2.4all

defIsListSorted_allenumk(lst,key=lambdax,y:x<=y):
returnall(key(lst[i],elem)fori,eleminenumerate(lst[1:]))
importoperator
defIsListSorted_allenumo(lst,oCmp=operator.le):
returnall(oCmp(lst[i],elem)fori,eleminenumerate(lst[1:]))
defIsListSorted_allenumd(lst):
returnall((lst[i]<=elem)fori,eleminenumerate(lst[1:]))
defIsListSorted_allxran(lst,key=lambdax,y:x<=y):
returnall(key(lst[i],lst[i+1])foriinxrange(len(lst)-1))
defIsListSorted_allzip(lst,key=lambdax,y:x<=y):
fromitertoolsimportizip#Python3中zip返回生成器(generator)，而izip被废弃
returnall(key(a,b)for(a,b)inizip(lst[:-1],lst[1:]))

lambda表达式与operator运算符速度相当，前者简单灵活，后者略为高效(实测并不一定)。但两者速度均不如列表元素直接比较(可能存在调用开销)。亦即，_allenumd()快于_allenumo()快于_allenumk()。

若使用lambda表达式指示排序规则，更改规则时只需要改变x和y之间的比较运算符；若使用operator模块指示排序规则，更改规则时需要改变对象比较方法。具体地，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()函数若要严格升序可设置oCmp=operator.lt。

此外，由all()函数的帮助信息可知，_allenumk()其实是_forloop()的等效形式。

2.5numpy

defIsListSorted_numpy(arr,key=lambdadif:dif>=0):
importnumpy
try:
ifarr.dtype.kind=='u':#无符号整数数组执行np.diff时存在underflow风险
arr=numpy.int64(lst)
exceptAttributeError:
pass#无dtype属性，非数组
return(key(numpy.diff(arr))).all()#numpy.diff(x)返回相邻数组元素的差值构成的数组

NumPy是用于科学计算的Python基础包，可存储和处理大型矩阵。它包含一个强大的N维数组对象，比Python自身的嵌套列表结构(nestedliststructure)高效得多。第三节的实测数据表明，_numpy()处理大型列表时性能非常出色。

在Windows系统中可通过pipinstallnumpy命令安装NumPy包，不建议登录官网下载文件自行安装。

2.6reduce

defIsListSorted_reduce(iterable,key=lambdax,y:x<=y):
cmpFunc=lambdax,y:yifkey(x,y)elsefloat('inf')
returnreduce(cmpFunc,iterable,.0)<float('inf')

reduce实现是all实现的变体。累加器(accumulator)中仅存储最后一个检查的列表元素，或者Infinity(若任一元素小于前个元素值)。

前面2.1~2.5小节涉及下标操作的函数适用于列表等可迭代对象(Iterable)。对于通用迭代器(Iterator)对象，即可以作用于next()函数或方法的对象，可使用_reduce()及后面除_rand()外各小节的函数。迭代器的计算是惰性的，只有在需要返回下一个数据时才会计算，以避免不必要的计算。而且，迭代器方式无需像列表那样切片为两个迭代对象。

2.7imap

defIsListSorted_itermap(iterable,key=lambdax,y:x<=y):
fromitertoolsimportimap,tee
a,b=tee(iterable)#为单个iterable创建两个独立的iterator
next(b,None)
returnall(imap(key,a,b))

2.8izip

defIsListSorted_iterzip(iterable,key=lambdax,y:x<=y):
fromitertoolsimporttee,izip
a,b=tee(iterable)
next(b,None)
returnall(key(x,y)forx,yinizip(a,b))
defpairwise(iterable):
fromitertoolsimporttee,izip
a,b=tee(iterable)
next(b,None)
returnizip(a,b)#"s->(s0,s1),(s1,s2),(s2,s3),..."
defIsListSorted_iterzipf(iterable,key=lambdax,y:x<=y):
returnall(key(a,b)fora,binpairwise(iterable))

第三节的实测数据表明，虽然存在外部函数调用，_iterzipf()却比_iterzip()略为高效。

2.9fast

defIsListSorted_fastd(lst):
it=iter(lst)
try:
prev=it.next()
exceptStopIteration:
returnTrue
forcurinit:
ifprev>cur:
returnFalse
prev=cur
returnTrue
defIsListSorted_fastk(lst,key=lambdax,y:x<=y):
it=iter(lst)
try:
prev=it.next()
exceptStopIteration:
returnTrue
forcurinit:
ifnotkey(prev,cur):
returnFalse
prev=cur
returnTrue

_fastd()和_fastk()是StackOverflow网站回答里据称执行最快的。实测数据表明，在列表未排序时，它们的性能表现确实优异。

2.10random

importrandom
defIsListSorted_rand(lst,randNum=3,randLen=100):
listLen=len(lst)
iflistLen<=1:
returnTrue

#由首个元素和末尾元素猜测可能的排序规则
iflst[0]<lst[-1]:#列表元素升序
key=lambdadif:dif>=0
else:#列表元素降序或相等
key=lambdadif:dif<=0

threshold,sortedFlag=10000,True
importnumpy
iflistLen<=thresholdorlistLen<=randLen*2ornotrandNum:
return(key(numpy.diff(numpy.array(lst)))).all()
fromrandomimportsample
foriinrange(randNum):
sortedRandList=sorted(sample(xrange(listLen),randLen))
flag=(key(numpy.diff(numpy.array([lst[x]forxinsortedRandList])))).all()
sortedFlag=sortedFlagandflag
returnsortedFlag

_rand()借助随机采样降低运算规模，并融入其他判断函数的优点。例如，猜测列表可能的排序规则，并在随机采样不适合时使用相对快速的判断方式，如NumPy。

通过line_profiler分析可知，第20行和第21行与randLen有关，但两者耗时接近。因此randLen应小于listLen的一半，以抵消sorted开销。除内部限制外，用户可以调节随机序列个数和长度，如定制单个但较长的序列。

注意，_rand()不适用于存在微量异常数据的长列表。因为这些数据很可能被随机采样遗漏，从而影响判断结果的准确性。

三.性能分析

本节借助Python标准库random模块，生成各种随机列表，以对比和分析上节列表排序判断函数的性能。

可通过sample()、randint()等方法生成随机列表。例如：

>>>importrandom
>>>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)foriinrange(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)foriinrange(10));randGen
<generatorobject<genexpr>at0x0192C878>

sample()方法从列表中随机选择数字，结合range()函数可生产不含重复元素的随机列表；而randint()方法结合列表解析生成的随机列表可能包含重复元素。Python文档规定，首次导入random模块时使用当前系统时间作为种子初始化随机数生成器。因此，本文并未显式地调用seed()方法设置种子。

为度量性能表现，定义如下计时装饰器：

fromtimeimportclock
TimeList=[]
defFuncTimer(repeats=1000):
defdecorator(func):
defwrapper(*args,**kwargs):
try:
startTime=clock()
foriinxrange(repeats):
ret=func(*args,**kwargs)
exceptException,e:
print'%s()Error:%s!'%(func.__name__,e)
ret=None
finally:#当目标函数发生异常时，仍旧输出计时信息
endTime=clock()
timeElasped=(endTime-startTime)*1000.0
msg='%21s():%s=>TimeElasped:%.3fmsec,repeated%dtime(s).'\
%(func.__name__,ret,timeElasped,repeats)
globalTimeList;TimeList.append([timeElasped,msg])
returnret
returnwrapper
returndecorator
defReportTimer():
globalTimeList;TimeList.sort(key=lambdax:x[0])
forentryinTimeList:
printentry[1]
TimeList=[]#Flush

该装饰器允许对输出进行排序，以便更直观地观察性能。基于该装饰器，下文将分别测试不同的排序场景。注意，第二节各函数头部需添加FuncTimer()装饰。

3.1列表前段乱序

测试代码如下：

defTestHeadUnorderedList():
TEST_NAME='HeadUnorderedList';scale=int(1e5)
List=random.sample(xrange(scale),scale)+range(scale)
print'Test1:%s,listlen:%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))#若不先转换为数组，则耗时骤增
IsListSorted_fastd(List)
IsListSorted_fastk(List)
ReportTimer()

运行输出如下：

Test1:HeadUnorderedList,listlen:200
IsListSorted_fastd():False=>TimeElasped:0.757msec,repeated1000time(s).
IsListSorted_fastk():False=>TimeElasped:1.091msec,repeated1000time(s).
IsListSorted_forloop():False=>TimeElasped:2.080msec,repeated1000time(s).
IsListSorted_guess():False=>TimeElasped:2.123msec,repeated1000time(s).
IsListSorted_allxran():False=>TimeElasped:2.255msec,repeated1000time(s).
IsListSorted_allenumd():False=>TimeElasped:2.672msec,repeated1000time(s).
IsListSorted_allenumo():False=>TimeElasped:3.021msec,repeated1000time(s).
IsListSorted_allenumk():False=>TimeElasped:3.207msec,repeated1000time(s).
IsListSorted_itermap():False=>TimeElasped:5.845msec,repeated1000time(s).
IsListSorted_allzip():False=>TimeElasped:7.793msec,repeated1000time(s).
IsListSorted_iterzip():False=>TimeElasped:9.667msec,repeated1000time(s).
IsListSorted_iterzipf():False=>TimeElasped:9.969msec,repeated1000time(s).
IsListSorted_numpy():False=>TimeElasped:16.203msec,repeated1000time(s).
IsListSorted_sorted():False=>TimeElasped:45.742msec,repeated1000time(s).
IsListSorted_reduce():False=>TimeElasped:145.447msec,repeated1000time(s).
Test1:HeadUnorderedList,listlen:200000
IsListSorted_fastd():False=>TimeElasped:0.717msec,repeated1000time(s).
IsListSorted_fastk():False=>TimeElasped:0.876msec,repeated1000time(s).
IsListSorted_allxran():False=>TimeElasped:2.104msec,repeated1000time(s).
IsListSorted_itermap():False=>TimeElasped:6.062msec,repeated1000time(s).
IsListSorted_iterzip():False=>TimeElasped:7.244msec,repeated1000time(s).
IsListSorted_iterzipf():False=>TimeElasped:8.491msec,repeated1000time(s).
IsListSorted_numpy():False=>TimeElasped:801.916msec,repeated1000time(s).
IsListSorted_forloop():False=>TimeElasped:2924.755msec,repeated1000time(s).
IsListSorted_guess():False=>TimeElasped:2991.756msec,repeated1000time(s).
IsListSorted_allenumo():False=>TimeElasped:3025.864msec,repeated1000time(s).
IsListSorted_allenumk():False=>TimeElasped:3062.792msec,repeated1000time(s).
IsListSorted_allenumd():False=>TimeElasped:3190.896msec,repeated1000time(s).
IsListSorted_allzip():False=>TimeElasped:6586.183msec,repeated1000time(s).
IsListSorted_sorted():False=>TimeElasped:119974.955msec,repeated1000time(s).
IsListSorted_reduce():False=>TimeElasped:154747.659msec,repeated1000time(s).

可见，对于前段乱序的列表，无论其长短_fastd()和_fastk()的表现均为最佳。对于未排序列表，_sorted()需要进行排序，故性能非常差。然而，_reduce()性能最差。

实际上除_guess()和_sorted()外，其他函数都按升序检查列表。为安全起见，可仿照_guess()实现，先猜测排序方式，再进一步检查。

因为短列表耗时差异大多可以忽略，后续测试将不再包含短列表(但作者确实测试过)，仅关注长列表。除非特别说明，列表长度为10万级，重复计时1000次。

3.2列表中段乱序

测试代码及结果如下：

defTestMiddUnorderedList():
TEST_NAME='MiddUnorderedList';scale=int(1e5)
List=range(scale)+random.sample(xrange(scale),scale)+range(scale)
print'Test2:%s,listlen:%d'%(TEST_NAME,len(List))
IsListSorted_numpy(numpy.array(List))#1572.295msec
IsListSorted_guess(List)#14540.637msec
IsListSorted_itermap(List)#21013.096msec
IsListSorted_fastk(List)#23840.582msec
IsListSorted_allxran(List)#31014.215msec
IsListSorted_iterzip(List)#33386.059msec
IsListSorted_forloop(List)#34228.006msec
IsListSorted_allenumk(List)#34416.802msec
IsListSorted_allzip(List)#42370.528msec
IsListSorted_sorted(List)#142592.756msec
IsListSorted_reduce(List)#187514.967msec
ReportTimer()

为节省篇幅，已根据运行输出调整函数的调用顺序。下文也作如此处理。

3.3列表后段乱序

测试代码及结果如下：

defTestTailUnorderedList():
TEST_NAME='TailUnorderedList';scale=int(1e5)
List=range(scale,0,-1)+random.sample(xrange(scale),scale)
print'Test3:%s,listlen:%d'%(TEST_NAME,len(List))
IsListSorted_numpy(numpy.array(List),key=lambdadif:dif<=0)#980.789msec
IsListSorted_guess(List)#13273.862msec
IsListSorted_itermap(List,key=lambdax,y:x>=y)#21603.315msec
IsListSorted_fastk(List,key=lambdax,y:x>=y)#24183.548msec
IsListSorted_allxran(List,key=lambdax,y:x>=y)#32850.254msec
IsListSorted_forloop(List,key=lambdax,y:x>=y)#33918.848msec
IsListSorted_iterzip(List,key=lambdax,y:x>=y)#34505.809msec
IsListSorted_allenumk(List,key=lambdax,y:x>=y)#35631.625msec
IsListSorted_allzip(List,key=lambdax,y:x>=y)#40076.330msec
ReportTimer()

3.4列表完全乱序

测试代码及结果如下：

defTestUnorderedList():
TEST_NAME='UnorderedList';scale=int(1e5)
List=random.sample(xrange(scale),scale)
print'Test4:%s,listlen:%d'%(TEST_NAME,len(List))
IsListSorted_fastk(List)#0.856msec
IsListSorted_allxran(List)#3.438msec
IsListSorted_iterzip(List)#7.233msec
IsListSorted_itermap(List)#7.595msec
IsListSorted_numpy(numpy.array(List))#207.222msec
IsListSorted_allenumk(List)#953.423msec
IsListSorted_guess(List)#1023.575msec
IsListSorted_forloop(List)#1076.986msec
IsListSorted_allzip(List)#2062.821msec
ReportTimer()

3.5列表元素相同

测试代码及结果如下：

```pythondefTestSameElemList():TEST_NAME='SameElemList';scale=int(1e5)List=[5]*scaleprint'Test5:%s,listlen:%d'%(TEST_NAME,len(List))IsListSorted_numpy(numpy.array(List))#209.324msecIsListSorted_sorted(List)#2760.139msecIsListSorted_guess(List)#5843.942msecIsListSorted_itermap(List)#20609.704msecIsListSorted_fastk(List)#23035.760msecIsListSorted_forloop(List)#29043.206msecIsListSorted_allenumk(List)#29553.716msecIsListSorted_allxran(List)#30348.549msecIsListSorted_iterzip(List)#32806.217msecReportTimer()

3.6列表升序

测试代码及结果如下：

defTestAscendingList():
TEST_NAME='AscendingList';scale=int(1e5)
List=range(scale)
print'Test6:%s,listlen:%d'%(TEST_NAME,len(List))
IsListSorted_numpy(numpy.array(List))#209.217msec
IsListSorted_sorted(List)#2845.166msec
IsListSorted_fastd(List)#5977.520msec
IsListSorted_guess(List)#10408.204msec
IsListSorted_allenumd(List)#15812.754msec
IsListSorted_itermap(List)#21244.476msec
IsListSorted_fastk(List)#23900.196msec
IsListSorted_allenumo(List)#28607.724msec
IsListSorted_forloop(List)#30075.538msec
IsListSorted_allenumk(List)#30274.017msec
IsListSorted_allxran(List)#31126.404msec
IsListSorted_reduce(List)#32940.108msec
IsListSorted_iterzip(List)#34188.312msec
IsListSorted_iterzipf(List)#34425.097msec
IsListSorted_allzip(List)#37967.447msec
ReportTimer()

可见，列表已排序时，_sorted()的性能较占优势。

3.7列表降序

剔除不支持降序的函数，测试代码及结果如下：

defTestDescendingList():
TEST_NAME='DescendingList';scale=int(1e2)
List=range(scale,0,-1)
print'Test7:%s,listlen:%d'%(TEST_NAME,len(List))
IsListSorted_numpy(numpy.array(List),key=lambdadif:dif<=0)#209.318msec
IsListSorted_sorted(List)#5707.067msec
IsListSorted_guess(List)#10549.928msec
IsListSorted_itermap(List,key=lambdax,y:x>=y)#21529.547msec
IsListSorted_fastk(List,key=lambdax,y:x>=y)#24264.465msec
importoperator;IsListSorted_allenumo(List,oCmp=operator.ge)#28093.035msec
IsListSorted_forloop(List,key=lambdax,y:x>=y)#30745.943msec
IsListSorted_allenumk(List,key=lambdax,y:x>=y)#32696.205msec
IsListSorted_allxran(List,key=lambdax,y:x>=y)#33431.473msec
IsListSorted_allzip(List,key=lambdax,y:x>=y)#34837.019msec
IsListSorted_iterzip(List,key=lambdax,y:x>=y)#35237.475msec
IsListSorted_reduce(List,key=lambdax,y:x>=y)#37035.270msec
ReportTimer()

3.8迭代器测试

参数为列表的函数，需要先将列表��过iter()函数转换为迭代器。注意，当iterable参数为iterator时，只能计时一次，因为该次执行将用尽迭代器。

测试代码如下：

defTestIter():
TEST_NAME='Iter';scale=int(1e7)
List=range(scale)#升序
#List=random.sample(xrange(scale),scale)#乱序
print'Test8:%s,listlen:%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=lambdax,y:x>=y)
ReportTimer()

运行结果如下：

Test8:Iter,listlen:10000000---升序
IsListSorted_fastd():True=>TimeElasped:611.028msec,repeated1time(s).
IsListSorted_sorted():False=>TimeElasped:721.751msec,repeated1time(s).
IsListSorted_guess():True=>TimeElasped:1142.065msec,repeated1time(s).
IsListSorted_itermap():True=>TimeElasped:2097.696msec,repeated1time(s).
IsListSorted_fastk():True=>TimeElasped:2337.233msec,repeated1time(s).
IsListSorted_reduce():True=>TimeElasped:3307.361msec,repeated1time(s).
IsListSorted_iterzipf():True=>TimeElasped:3354.034msec,repeated1time(s).
IsListSorted_iterzip():True=>TimeElasped:3442.520msec,repeated1time(s).
Test8:Iter,listlen:10000000---乱序
IsListSorted_fastk():False=>TimeElasped:0.004msec,repeated1time(s).
IsListSorted_fastd():False=>TimeElasped:0.010msec,repeated1time(s).
IsListSorted_iterzip():False=>TimeElasped:0.015msec,repeated1time(s).
IsListSorted_itermap():False=>TimeElasped:0.055msec,repeated1time(s).
IsListSorted_iterzipf():False=>TimeElasped:0.062msec,repeated1time(s).
IsListSorted_guess():False=>TimeElasped:736.810msec,repeated1time(s).
IsListSorted_reduce():False=>TimeElasped:8919.611msec,repeated1time(s).
IsListSorted_sorted():False=>TimeElasped:12273.018msec,repeated1time(s).

其中，_itermap()、_iterzip()、_iterzipf()、_reduce()、_fastd()、_fastk()可直接判断迭代器是否已排序。其他函数需将迭代器转换为列表后才能处理。_sorted()虽然接受迭代器参数，但sorted()返回列表，故无法正确判断迭代器顺序。

3.9随机采样测试

综合以上测试，可知_fastk()和_numpy()性能较为突出，而且_rand()内置numpy方式。因此，以_fastk()和_numpy()为参照对象，测试代码如下(计时1次)：

defTestRandList():
scale=int(1e6)
List=random.sample(xrange(scale),scale)+range(scale)
print'Test1:%s,listlen:%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'Test2:%s,listlen:%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'Test3:%s,listlen:%d'%('TailUnorderedList',len(List))
IsListSorted_fastk(List,key=lambdax,y:x>=y)
IsListSorted_numpy(numpy.array(List),key=lambdadif:dif<=0)
IsListSorted_rand(List,randNum=1)
ReportTimer()
List=[random.randint(1,scale)foriinxrange(scale)]#random.sample(xrange(scale),scale)
print'Test4:%s,listlen:%d'%('UnorderedList',len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List,randNum=1)
ReportTimer()
List=[5]*scale
print'Test5:%s,listlen:%d'%('SameElemList',len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List,randNum=1)
ReportTimer()
List=range(scale)
print'Test6:%s,listlen:%d'%('AscendingList',len(List))
IsListSorted_fastk(List)
IsListSorted_numpy(numpy.array(List))
IsListSorted_rand(List,randNum=1)
ReportTimer()
List=range(scale,0,-1)
print'Test7:%s,listlen:%d'%('DescendingList',len(List))
IsListSorted_fastk(List,key=lambdax,y:x>=y)
IsListSorted_numpy(numpy.array(List),key=lambdadif:dif<=0)
IsListSorted_rand(List,randNum=1)
ReportTimer()
List=range(scale,0,-1);List[scale/2]=0
print'Test8:%s,listlen:%d'%('MiddleNotchList',len(List))
IsListSorted_fastk(List,key=lambdax,y:x>=y)
IsListSorted_numpy(numpy.array(List),key=lambdadif:dif<=0)
IsListSorted_rand(List,randNum=1)
IsListSorted_rand(List,randNum=1,randLen=scale/2)
ReportTimer()

运行输出如下：

Test1:HeadUnorderedList,listlen:2000000
IsListSorted_fastk():False=>TimeElasped:0.095msec,repeated1time(s).
IsListSorted_rand():False=>TimeElasped:0.347msec,repeated1time(s).
IsListSorted_numpy():False=>TimeElasped:7.893msec,repeated1time(s).
Test2:MiddUnorderedList,listlen:3000000
IsListSorted_rand():False=>TimeElasped:0.427msec,repeated1time(s).
IsListSorted_numpy():False=>TimeElasped:11.868msec,repeated1time(s).
IsListSorted_fastk():False=>TimeElasped:210.842msec,repeated1time(s).
Test3:TailUnorderedList,listlen:2000000
IsListSorted_rand():False=>TimeElasped:0.355msec,repeated1time(s).
IsListSorted_numpy():False=>TimeElasped:7.548msec,repeated1time(s).
IsListSorted_fastk():False=>TimeElasped:280.416msec,repeated1time(s).
Test4:UnorderedList,listlen:1000000
IsListSorted_fastk():False=>TimeElasped:0.074msec,repeated1time(s).
IsListSorted_rand():False=>TimeElasped:0.388msec,repeated1time(s).
IsListSorted_numpy():False=>TimeElasped:3.757msec,repeated1time(s).
Test5:SameElemList,listlen:1000000
IsListSorted_rand():True=>TimeElasped:0.304msec,repeated1time(s).
IsListSorted_numpy():True=>TimeElasped:3.955msec,repeated1time(s).
IsListSorted_fastk():True=>TimeElasped:210.977msec,repeated1time(s).
Test6:AscendingList,listlen:1000000
IsListSorted_rand():True=>TimeElasped:0.299msec,repeated1time(s).
IsListSorted_numpy():True=>TimeElasped:4.822msec,repeated1time(s).
IsListSorted_fastk():True=>TimeElasped:214.171msec,repeated1time(s).
Test7:DescendingList,listlen:1000000
IsListSorted_rand():True=>TimeElasped:0.336msec,repeated1time(s).
IsListSorted_numpy():True=>TimeElasped:3.867msec,repeated1time(s).
IsListSorted_fastk():True=>TimeElasped:279.322msec,repeated1time(s).
Test8:MiddleNotchList,listlen:1000000
IsListSorted_rand():True=>TimeElasped:0.387msec,repeated1time(s).
IsListSorted_numpy():False=>TimeElasped:4.792msec,repeated1time(s).
IsListSorted_rand():False=>TimeElasped:78.903msec,repeated1time(s).
IsListSorted_fastk():False=>TimeElasped:110.444msec,repeated1time(s).

可见，在绝大部分测试场景中，_rand()性能均为最佳，且不失正确率。注意测试8，当降序列表中间某个元素被置0(开槽)时，随机采样很容易遗漏该元素，导致误判。然而，这种场景在实际使用中非常罕见。

Python判断列表是否已排序的各种方法及其性能分析

热门推荐

随机推荐