登录 立即注册
安币:

安卓巴士 - 安卓开发 - Android开发 - 安卓 - 移动互联网门户

查看: 148|回复: 6

增量地改进python脚本的性能,直到没有任何意义为止

[复制链接]

551

主题

554

帖子

1万

安币

手工艺人

发表于 2019-1-11 12:01:04 | 显示全部楼层 |阅读模式
我最近在Kattis上研究了很多非常棘手的编程问题。Kattis是我最喜欢的在线编程裁判系统,并且我一直非常享受在爱尔兰记分牌上排名攀升的感觉,现在是时候去重新赢回第一名的荣耀了。
今天我特别要讲的是Pivot问题。这是一个相当小的、简单的、独立的问题,但是在尝试优化我的答案的过程中,我学到了一些有趣的东西。
以下是这个问题陈述的要点:
一个复杂度为O(n)的分区算法计划把一个数组A围绕一个基准元素(基准也是A的一个成员)分成三个部分:一个左子列,其中包含所有小于等于基准的元素,基准本身,和一个右子列,包含所有大于基准的元素。
现在这个问题的实际工作是这样的:从一个有n个不同整数的数组A开始,我们用A中的一个元素作为基准对A进行分区,从而生成一个变换后的数组A "。给定这个变换后的数组A ",你的工作是计算有多少个整数可以是被选中的基准。
简单地说,我们得到一个分区的输出,并且必须计算列表中可能用作基准的值的数量。
我们被告知,元素的数量n的范围是3≤n≤100000。我们还知道所有输入的数字都是32位有符号整数(但是在Python中,这并没有太大的区别)。
现在,让我们进入解决这个问题的无底洞,然后尝试着再进一步。
朴素的解决方案
我不是说这是你的错/尽管你本可以做得更多
在分解问题的时候,我们可以看到我们是在试图找到输入列表中的每一个数字 (我将称之为D),条件是当j<i时,D大于或等于所有D[j],当k>i时,小于所有D[k]。这个想法的实现如下。
这个解决方案的时间复杂度O (n ^ 2),而且超过了Kattis第四个测试用例的1秒时间限制。简单地说就是还不够快。
这是因为,对于(多达)100万个输入数字中的每一个,我们要迭代(在最坏的情况下)每一个数字。这是需要很长时间的。
你可以做一些小的优化,比如跳过循环k(如果ok已经为假),但是我怀疑这些优化能否在限制时间内完成。然而如果实在没有其他的想法的话,这些优化还是值得的,毕竟你还在编程比赛中,并且极度渴望得到一些额外的分数。
完美的 O (n)
当我明白- 10 ^ 12的比较问题是不可能在一秒内完成,我就知道O (n ^ 2)是不够的。我立刻意识到这个问题可以在O(n)时间内解决。
你不需要把每个数和它之前的每个数进行比较,看它是否大于或等于每一个数。你只需要将该数字与它之前的最大数字进行比较。同样地,你也只需要将数字与它之后的最小数字进行比较。
你可以在O(n)时间内构建一个列表,我在下文将其称为左列,含义是“元素左边的最大数字”。
你可以类似的方式构建“该元素右边的最小数字”的等效列表右列。
阅读代码可能比我在这里东拉西扯更容易理解。这是我提交的首个解决方案。
Kattis告诉我这个运行了0.16秒,远远低于时间限制,可以得到这个问题的满分。工作完成!
Kattis有一个很好的特性,它可以按语言分类地显示每个问题的前10个最快解决方案的计分板。我经常在解决一个问题后去看看这个表格,看看我的解决方案排名如何。
当我扫了一眼这个问题的记分牌时,我的心被射伤了。Python 3提交的最快时间仅仅是0.06秒,并且它是由我的同学/劲敌/竞争对手Cian Ruane提交的。这太可怕了!我无法忍受他比我快十分之一秒;想象一下如果他看到这些,他会有多么得意!我必须要做得更好。
加速# 1
嫉妒也是促人进步的动力。
很快(实际上,我在1分18秒之后提交了新的解决方案),我意识到我做了两倍于我需要做的工作。我不需要构建左边的列表,只需要在最后迭代列表以计算结果时,对目前为止看到的最大数字保持一个运行计数即可。这将使解决方案节约大约一半的空间,节省整个数组的迭代,并肯定会提高我的速度。
也许这就是Cian成绩更好的原因?以下是我提交的新方案。
它跑了0.14秒。甚至还没有快到能在积分榜上排到第10名,更别提第一名了。
从以往的经验来看,我发现最简单的Python问题只需要0.02秒。我假设这是启动Python解释器、解析程序等的时间成本。一旦问题想要在小于0.05秒左右的时间内运行,可能就没有多少空间可以提高速度了。然而,我们还远没有达到这个极限。此外,我可以看到其他人在0.06秒内完成了它,而计分板的其余排名都在0.07秒- 0.09秒,所以它一定是可行的!
过了4分钟,快了0.04秒
2分45秒后,我提交了以下文件:
我在很多地方看到人们避免使用Python内置的max和min,而在研究这个问题时,我没有看到任何其他明显的潜在加速的可行性。对我来说,这些可能比简单的if语句还要慢;不仅每次调用函数都有开销,而且这些函数还支持从迭代器中获取最大值或最小值,因此必须有一些逻辑来确定这些函数是否有需要避免被使用。
这个解决方案花费了0.12秒。
Cian的解决方案只花了一半的时间。我的好奇心被激起来了;他是怎么做到的?我试图通过阅读他的解决方案来找出答案——这可以教会我很多东西。
偷窥
我到github上看了看他的Kattis解决方案:
他的解决办法是……和我的差不多一样。他列出的清单和我的顺序正好相反,但这应该没什么区别吧?
在他所写的最后的循环中,少了一步比较——也许就是因为这样? 他在一个列表而不是一个映射中构建他的输入值列表——这可能会更理想一些? 也许我在他的迭代命令中遗漏了一些东西,而正是这些东西秘密的进行了智能加速?
我窃取了他的一些想法,并提交了以下内容。
这次花费了 0.09s.
WTF
承认失败后,我给Cian发了个短信。
Noah: @Cian Ruane,关于Pivot问题,我的解决方案和你的差不多,但是你的快了0.03秒
Cian:真是难以置信
Noah: if __name__ == "__main__"这行代码是不是有神奇的加速效果
Noah:是不是碰巧服务器加载的很快
Cian:试着把它变成一个函数
Noan:那肯定会更慢
Cian:也许它会产生意想不到的效果呢
好吧,为什么不试试呢?我提交了以下内容。
这次解决方案运行花费了0.06秒。
WTF 2:机械舞
为什么将代码放入函数中会加快速度?跳转到函数的开销肯定会使代码变慢,而不是变快吗?Cian说的对吗,还是说JIT里有一些其他东西?
并不是-但Stack Overflow有答案:
Scharron:只是一种直觉,不确定是否正确:我猜是因为作用域。在这种情况下,函数将创建一个新的作用域(即一种将变量名绑定到其值的散列)。如果没有函数,变量是在全局范围内的,当你需要寻找很多东西时,因此会减慢循环
katrielalex:@Scharron,你说对了一半。它是关于作用域的,在局部变量中更快的原因是,局部范围实际上是作为数组而不是字典实现的(因为在编译时知道它们的大小)。
然后,katriealex详细介绍了关于变量作用域的更有趣的细节。
ecatmur还查看了字节码,并展示它如何在解释器中显示出来。
超级有趣。
事后剖析
在说了这么多以后,我从中学到了什么?
1.将我的脚本放在函数中而不是全局范围中,没有什么大的缺点,但是有一个潜在的优点。
  • 就像我在这里看到的,它更快。我想,当脚本中的变量访问更少时,这种加速就不那么明显了。
  • 这里的一些答案提到了代码不运行在模块导入上的好处。
  • (在我看来)它创造了更干净的代码。我只是太懒了,不愿意放弃之前的有竞争力的编程解决方案。

2.如果我只比较两个值,并且担心性能,我应该考虑使用if而不是max和min。
  • 这段代码不是很好,但如果经常运行,可以节省宝贵的时间。

3.我应该从katriealex链接的页面了解python性能技巧。那里有一些关于Python内部的详细信息。
4.我应该站在Cian一边,这样他就能继续留在我的队伍里,而不是跑去跟我竞争的队伍里。也就是说,我在以前的一些比赛中做得比他好,而且我将永远让他牢记这一点。

2

主题

9409

帖子

2478

安币

Android大神

Rank: 6Rank: 6

发表于 2019-1-11 12:10:27 | 显示全部楼层
感谢分享,楼主V5~

434

主题

1067

帖子

474

安币

手工艺人

发表于 2019-1-11 12:36:52 | 显示全部楼层
楼主是好人,回个帖会有安币吗?

0

主题

9295

帖子

2405

安币

Android大神

Rank: 6Rank: 6

发表于 2019-1-11 12:57:48 | 显示全部楼层
楼主威武,以后多发干货,多办活动~!

329

主题

919

帖子

726

安币

手工艺人

发表于 2019-1-11 13:01:51 | 显示全部楼层
每次我都积极回帖的,想要安币~
发表于 2019-1-11 13:03:43 | 显示全部楼层
感谢分享,楼主V5~

3

主题

9425

帖子

1796

安币

Android大神

Rank: 6Rank: 6

QQ达人

发表于 2019-1-11 13:10:24 | 显示全部楼层
不错不错,楼主辛苦了。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

站长推荐

通过邮件订阅最新安卓weekly信息
上一条 /4 下一条

下载安卓巴士客户端

全国最大的安卓开发者社区
联系我们
关闭
合作电话:
15618560077
Email:
805941275@qq.com
商务市场合作/投稿
问题反馈及帮助
联系我们

广告投放| 广东互联网违法和不良信息举报中心|中国互联网举报中心|下载客户端|申请友链|手机版|站点统计|安卓巴士 ( 粤ICP备15117877号 )

快速回复 返回顶部 返回列表