python升序数判断_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)
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,2,3]视为升序，[3,3,2,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, 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表达式与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, 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实现是all实现的变体。累加器(accumulator)中仅存储最后⼀个检查的列表元素，或者Infinity(若任⼀元素⼩于前个元素值)。
前⾯2.1~2.5⼩节涉及下标操作的函数适⽤于列表等可迭代对象(Iterable)。对于通⽤迭代器(Iterator)对象，即可以作⽤于next()函数或⽅法的对象，可使⽤_reduce()及后⾯除_rand()外各⼩节的函数。迭代器的计算是惰性的，只有在需要返回下⼀个数据时才会计算，以避免不必要的计算。⽽且，迭代器⽅式⽆需像列表那样切⽚为两个迭代对象。
2.7 imap
def IsListSorted_itermap(iterable, key=lambda x, 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, 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))
第三节的实测数据表明，虽然存在外部函数调⽤，_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
random pythonprev = 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⽹站回答⾥据称执⾏最快的。实测数据表明，在列表未排序时，它们的性能表现确实优异。
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模块，⽣成各种随机列表，以对⽐和分析上节列表排序判断函数的性能。
可通过sample()、randint()等⽅法⽣成随机列表。例如：
>>>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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。