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

声明

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

一. 问题提出

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

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

pair lst = zip lst ( tail lst )
sorted lst predict = and [ predict x y | (x,y) <- pair lst] 

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

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

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

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

二. 代码实现

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

2.1 guess

def IsListSorted_guess(lst):
listLen = len(lst)
if listLen <= 1:
return True
#由首个元素和末尾元素猜测可能的排序规则
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()是最通用的实现，几乎与语言无关。值得注意的是，该函数内会猜测给定列表可能的排序规则，因此无需外部调用者指明排序规则。

2.2 sorted

def IsListSorted_sorted(lst):
return sorted(lst) == lst or sorted(lst,reverse=True) == lst 

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

2.3 for-loop

def IsListSorted_forloop(lst,key=lambda x,y: x <= y):
for i,elem in enumerate(lst[1:]): #注意，enumerate默认迭代下标从0开始
if not key(lst[i],elem): #if elem > lst[i]更快，但通用性差
return False
return True 

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

2.4 all

def IsListSorted_allenumk(lst,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 in enumerate(lst[1:]))
def IsListSorted_allenumd(lst):
return all((lst[i] <= elem) for i,elem in enumerate(lst[1:]))
def IsListSorted_allxran(lst,lst[i+1]) for i in xrange(len(lst)-1))
def IsListSorted_allzip(lst,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表达式与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.5 numpy

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

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

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

2.6 reduce

def IsListSorted_reduce(iterable,y: x <= y):
cmpFunc = lambda x,y: y if key(x,y) else float('inf')
return reduce(cmpFunc,iterable,.0) < float('inf') 

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

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

2.7 imap

def IsListSorted_itermap(iterable,y: x <= y):
from itertools import imap,tee
a,b = tee(iterable) #为单个iterable创建两个独立的iterator
next(b,None)
return all(imap(key,a,b)) 

2.8 izip

def IsListSorted_iterzip(iterable,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,None)
return izip(a,b) #"s -> (s0,s1),(s1,s2),(s2,s3),..."
def IsListSorted_iterzipf(iterable,y: x <= y):
return all(key(a,b) for a,b in pairwise(iterable)) 

第三节的实测数据表明，虽然存在外部函数调用，_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,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网站回答里据称执行最快的。实测数据表明，在列表未排序时，它们的性能表现确实优异。

2.10 random

import random
def IsListSorted_rand(lst,randNum=3,randLen=100):
listLen = len(lst)
if listLen <= 1:
return True

#由首个元素和末尾元素猜测可能的排序规则
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()借助随机采样降低运算规模，并融入其他判断函数的优点。例如，猜测列表可能的排序规则，并在随机采样不适合时使用相对快速的判断方式，如NumPy。

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

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

三. 性能分析

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

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!