美国买被子or国内带被子?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 789|回复: 3
收起左侧

[算法题] merge sorted array follow up的思路讨论

[复制链接] |试试Instant~ |关注本帖
我的人缘0
2011051305 发表于 2017-8-1 09:47:06 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (122)
 
 
22% (35)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x


Merge Two Sorted Array里有个follow up是说:  如果一个Array比另一个大很多, 另外一个非常小: How can you optimize your algorithm if one array is very large and the other is very small?
我不太理解这还能怎么优化,毕竟无论如何都要return一个新的array,memory complexity就是O(m+n)。一个可能的想法是针对那个very small的array 每一个元素在very big array用二分的方法迅速定位再插入,但是vector新插一个元素,不得把插入位置先空出来插入,然后后面依次copy下去么? 时间复杂度仍然是O(m+n)
还是我哪里理解错了? 谢谢!


上一篇:【Google】 面经, 这题怎么搞?
下一篇:求大神指点,用栈stack解决问题的思路
我的人缘0
magicsets 发表于 2017-8-1 13:59:46 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (214)
 
 
2% (6)  踩
本帖最后由 magicsets 于 2017-8-1 14:03 编辑

说一点点我的理解.. 虽然不知道这个follow up所期望的答案是什么。

首先时间复杂度只能固定在O(m+n)了,所以需要优化的只是常数因子——虽然算法题中不讲究常数因子,但现实中系统性能的差距很大程度上决定于在对底层执行的理解的基础上、受限于系统架构和所使用的抽象所决定的对“常数因子”的优化能力。

现在考虑m非常大(例如10^9)、n非常小(例如10)的情况,这里列举两种情况可能导致不同的实现会有2倍以上(甚至可能5倍以上)的性能差距。

(1) 使用C++编写代码,追求最大化性能
-- 标准的写法:while里面套个if,最后再while收尾,例如Leetcode上的解答:https://leetcode.com/problems/merge-sorted-array/discuss/
-- 高性能写法:对于第二个array的每个元素,用二分查找其在第一个array中对应的边界,然后使用std::memcpy拷贝整个区间

性能的差距在于
(a) 后者使用std::memcpy,在现有的大部分机器上,编译器会进一步优化为SSE/AVX指令以达到最大传输带宽;而简单写法中的if使得编译器无法做此优化。
(b) 前者while中的if在m很大、n很小的情况下显得非常低效——因为绝大多数情况下必然是进入m对应的那个分支,虽然CPU的branch prediction可以缓和这一影响,但是其还是浪费两个CPU cycle并且使得编译器无法使用SSE/AVX指令。

(2) array中存储的对象不是简单数据类型并且“compare”代价昂贵
一般我们讨论这个问题时,会假设array中存储的是int类型——而比较两个int是非常容易的,就一个CPU cycle。

但如果里面存储不是int,而是实现了Comparator接口的某一抽象数据类型,其拷贝很快而"compare"操作非常慢,那么标准写法中O(m+n)的比较次数就会比二分方法中O(n * log(m))的比较次数慢非常多——虽然它们都要做O(m+n)大小的数据拷贝。
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
 楼主| 2011051305 发表于 2017-8-2 01:56:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  77% (122)
 
 
22% (35)  踩
magicsets 发表于 2017-8-1 13:59
说一点点我的理解.. 虽然不知道这个follow up所期望的答案是什么。

首先时间复杂度只能固定在O(m+n)了, ...

非常感谢大神的指点。 我只是能隐约猜测可能二分是个方向,但是不知道里面还有这么多优化细节! 感谢!!
回复

使用道具 举报

我的人缘0
mchzh 发表于 2017-8-2 02:08:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (66)
 
 
7% (5)  踩
感觉是为了减少比较的次数,如果一个array很小的话,应该用二分容易找到它在新array里的位置,然后再统一把两个array合并到一个新的里面
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html






手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-7-22 01:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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