从一个无序数组中查询最大值的最快算法是什么?

【伯乐在线导读】:2015 年 10 月,Reddit 有一个激烈的讨论帖,名为《这就是初级工程师与高级工程师之间的差距》,好奇打开一看。发现分享的童鞋是引用了 Thomas A. Limoncelli 在 Quora 上对《从一个无序数组中查询最大值的最快算法是什么?》的回复。一起来看看。


Ken Alverson 提到的并行计算的方法可能是最好的算法答案,而 Tim Farage 的回答可能是对这个这个问题最精确的解释…. 下面我将给出最实用的答案。

为什么注重实用?因为由我亲自操作,而我生活在一个真实的世界中。在现实生活中,我可以使这个搜索在 0 秒内完成,甚至不需要任何时间。 

在你的职业生涯中,可能从来不需要在完全独立的情况下进行这个查找。算法不是独立存在的,它们是用在真实世界。真实世界涉及流程,人员和团队。总有一些外部性的(看似无关的东西)条件可以利用,来获得比 Ken 和 Tim 的答案更好的结果。 

下面是我在职业生涯中作为一个系统管理员的一些案例:

1、对于一个小的数字列表来讲,任何算法都是没问题的。“小”对于当今世界来讲可能就是一千万个整数。你将会对现代 Intel 处理器遍历一千万个数字的速度感到惊讶。如果你只需要一天做一次这样的查询操作,搜索花费的这点时间是微不足道的。不要担心速度了,等到你觉得它是个问题时再担心也不迟!时间复杂度为O(N)可能刚刚好。已经记不清有多少次了,总有人跑来对我说“我们需要一个大数据专家”,结果在讨论之后,我发现他们所说的“大”只不过是10G的数据。我可以用一张信用卡额度买一台 Dell 服务器,然后把这 10G 的数据完全装载进 RAM 中。

2、可以将查询操作隐藏在后台执行。如果搜索耗费时间太长,看下是否可以在处理程序中尽早获取数组,这样就可以在后台进行搜索了。可能是要展示一个标题屏幕,也可能是要渲染一个用户界面。可以在渲染之前得到数组吗?可以的话就可以在后台进行排序了。纵观全局,并查询所有相关进程最早可以什么时候得到数据列表。我曾经遇到过这样一个场景,我们在T+4时得到了一个数组并在T+6时完成了排序。一个开发者对算法进行了改进,使得我们在T+5时就可以得到了排好序的数据。我在T+0时就获得了数组的访问权,T+1时刻就把数据准备好了。和v1.0版本的软件比起来就像是有一台时间机器!

3、干脆就不要搜索了!当你在构建一个list时,总是记录你遇到的最大值,这样就可以 O(0)时间内找到最大值了。去告诉负责人然后要求他们这样做。如果他们不让步,告诉他们的老板。是哪个混蛋非要让你在他们的数据中找到最大值?Oh,他们不能维护一个保存“最大值”的变量的原因竟是要对这个列表进行删除和更新操作?如果确实是这样,他们根本就不应该将数据放到一个无序的数组中,因为任何其它数据结构对于这些更新操作来说都会是更好的选择;并且任何其他数据结构都会有一个比 O(N) 更高效的查询最大值的方法。 

4、利用重复的优势。当你第一次看到这个 list 时,可能确实需要一个线性的时间 O(N) 进行搜索。然而数据在那之后并不会消失。可能被用来做一些其它的事情,更新,或者修正,这些改变之后需要再次找到最大的值。机会就在这里,更新操作可以用来跟踪“最大值”么?数据稍后会被放到树或者被排序么?是否需要精确的答案,或者是否可以根据之前的数据进行估计,然后通过每次重复来改进猜测结果?

我曾经看到有5个执行步骤的程序。每一步由不同的团队完成。每个团队都是通过对数据进行排序开始。如果第一个团队对数据进行了排序,然后为接下来的团队保存好排序后的数据,花在排序上的时间将会提高5倍!OMG ,那要求一个团队的成员来告诉另一个团队的成员!oh!太恐怖了!拜托拜托!不要让我做人类了!我只想做一个与世隔绝的码农!事实上不是这样的。你想成为一个很棒的程序开发团队的一员,开发那些由软件驱动的优秀程序。 

因此如果这是一个对功课进行分配的问题…答案是O(N):对 list 做一个线性搜索,检查每一个单独的项目。 

如果这个问题是一个诚恳的请求….放下键盘。站起来走到大厅中,与所有相关人员交流,挖掘出真正需要的东西,然后重新确定是否确实需要“最大值”,需要它做什么,以及通过一直追踪它,整个处理程序是否可以得到改进。

走出你的小黑屋,与人们交流,你将会得到更好的结果。

后续更新:

5、我曾经遇到过这样的一个场景,发现原来分配内存时需要调用max()函数。为什么不基于最后一次得到的相似的dataset进行内存大小的增长与收缩?这样一来,最大值就是一个常量,因此通过提出类似的问题,程序员可以以一种完全不同的方式来完成任务。 

6、确定后续步骤是否需要一个有序的数据。主动在你这一步将它排好序,这样就可以通过简单地获取最后一个元素来得到最大值。现在这个算法的复杂度是O(n log2 n)[或者其他排序算法的复杂度],比 O(n) 更大,但是整个系统却因此变得更快。

打赏支持我翻译更多好文章,谢谢!

打赏译者

打赏支持我翻译更多好文章,谢谢!

任选一种支付方式

2 5 收藏 评论

关于作者:飘扬叶

一个空闲时写写代码、做做翻译、看看世界的成长中小码农,辛勤耕耘只为美好的生活! 个人主页 · 我的文章 · 13 ·  

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部