位置: 编程技术 - 正文

Python判断列表是否已排序的各种方法及其性能分析(如何判断python列表长度)

编辑:rootadmin

推荐整理分享Python判断列表是否已排序的各种方法及其性能分析(如何判断python列表长度),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:python怎么判断列表为空,python判断列表中的数字,python怎么判断列表为空,python判断列表包含,python判断列表中,python判断属于列表,python判断属于列表,python判断属于列表,内容如对您有帮助,希望把文章链接给更多的朋友!

声明

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

一. 问题提出

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

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

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

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

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

为对比验证随机采样方式的可行性,作者先在网上搜集判断列表排序的现有方法,主要参考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

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

2.2 sorted

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

2.3 for-loop

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

2.4 all

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

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

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

2.6 reduce

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

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

2.7 imap

2.8 izip

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

2.9 fast

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

2. random

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

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

Python判断列表是否已排序的各种方法及其性能分析(如何判断python列表长度)

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

三. 性能分析

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

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

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

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

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

3.1 列表前段乱序

测试代码如下:

运行输出如下:

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

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

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

3.2 列表中段乱序

测试代码及结果如下:

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

3.3 列表后段乱序

测试代码及结果如下:

3.4 列表完全乱序

测试代码及结果如下:

3.5 列表元素相同

测试代码及结果如下:

3.6 列表升序

测试代码及结果如下:

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

3.7 列表降序

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

3.8 迭代器测试

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

测试代码如下:

运行结果如下:

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

3.9 随机采样测试

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

运行输出如下:

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

解析Python中的生成器及其与迭代器的差异 生成器生成器是一种迭代器,是一种特殊的函数,使用yield操作将函数构造成迭代器。普通的函数有一个入口,有一个返回值;当函数被调用时,从入口

Python中在for循环中嵌套使用if和else语句的技巧 for...[if]...构建List(Listcomprehension)1.简单的for...[if]...语句Python中,for...[if]...语句一种简洁的构建List的方法,从for给定的List中选择出满足if条件的元素

Python中的数学运算操作符使用进阶 Python中对象的行为是由它的类型(Type)决定的。所谓类型就是支持某些特定的操作。数字对象在任何编程语言中都是基础元素,支持加、减、乘、除等数

标签: 如何判断python列表长度

本文链接地址:https://www.jiuchutong.com/biancheng/387697.html 转载请保留说明!

上一篇:Python编程中装饰器的使用示例解析

下一篇:解析Python中的生成器及其与迭代器的差异(python程序解析)

  • 小微企业要做企业年金吗
  • 非上市公司股权转让涉及哪些税
  • 机票和发票是一样的吗
  • 为什么盈利要利润亏损要扣除所得税
  • 公司之间往来款需要开收据吗
  • 承兑贴现几个点是月息还是年息
  • 金蝶美金账户怎么开
  • 个体工商户是否家庭经营的区别
  • 出口未开票怎么会计处理
  • 专用发票网上勾选不了
  • 充电桩收入属于什么类别
  • 税费误差财务怎么调整
  • 增值税专用发票电子版
  • 辅助材料属于成本吗
  • 记账凭证填制流程是什么
  • 房租怎么抵扣个税计算方法
  • 海关进口增值税如何入账
  • 部分预收账款会计科目
  • 增值税普通发票税率
  • 分公司税务是独立核算还是非独立
  • 装修公司一般纳税人纳税标准
  • 个税起征点是多少啊
  • 文化事业建设费的征收范围
  • 保险公司代收车船税完税证明在哪里打印
  • 客户购买产品的好处
  • 建筑业预估成本怎么算
  • 6月 全新windows
  • mac安装软件不用密码
  • 华为手机hms提醒
  • erl.exe是什么进程
  • 系统更新到win11后还可以调回win10吗
  • 支付货款的流程
  • 物业管理费发票图片
  • ksysslim.exe是什么
  • 员工冲借款应该怎么做账
  • PHP:move_uploaded_file()的用法_Filesystem函数
  • 逾期未收回包装物押金增值税
  • 预付办公用品费用,未收到发票
  • 逆回购利息计算公式
  • php 读取大excel
  • 单位管理费用核算范围包括
  • vscode调试在哪
  • uniapp示例
  • 网络安全工具大全图片
  • windowsserver2012r2远程协助灰色
  • 2023年中国会有什么重大事件
  • 现金和现金等价物包括哪些
  • 建账在1月份如何录入期初
  • 程序员35岁 知乎
  • 织梦怎么建站
  • 差旅费报销范文
  • 材料成本差异的借方表示什么
  • 民间非营利组织财务管理制度
  • 应收票据备查簿的作用
  • 应收账款坏账计提比例新标准
  • 购买不动产增值税率
  • 费用报销的凭证是什么
  • 现金支票存根联丢失怎么办
  • 省外出差
  • 销售费用可以提现吗
  • 无形资产摊销费怎么算
  • mysql无法配置
  • mysql数据库主机一般填什么
  • windows开始菜单在哪里
  • 迁移windows
  • VMware虚拟机中卸载java命令
  • 如果不用2b橡皮擦2b铅笔 能扫的出来吗
  • win7笔记本电脑怎么重装系统教程
  • win1021年更新
  • unity2019新功能
  • android实战项目
  • shell脚本ping
  • 变量代码是什么
  • python语言的特殊符号
  • python3.5怎么保存
  • dom事件模型由什么组成
  • javascript中array的正确写法
  • js写日期
  • 我的宁夏灵活就业缴费失败
  • 先征后返的增值税计入哪个科目
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设