merge sorted array follow up的思路讨论

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)

还是我哪里理解错了？ 谢谢！

说一点点我的理解.. 虽然不知道这个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)大小的数据拷贝。

magicsets 发表于 2017-8-1 13:59
说一点点我的理解.. 虽然不知道这个follow up所期望的答案是什么。

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

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

感觉是为了减少比较的次数，如果一个array很小的话，应该用二分容易找到它在新array里的位置，然后再统一把两个array合并到一个新的里面