Python判断列表是否已排序的各种方法及其性能分析
发布网友
发布时间：2022-04-22 04:23
共1个回答
热心网友
时间：2022-04-14 07:04
本文基于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，则条目必然已经排序。
为对比验证随机采样方式的可行性，作者先在网上搜集判断列表排序的现有方法，
