缓存优化-哈希映射与QuickSort？

Question

假设我有N个未排序的整数数组。我想找到这些数组的交集。

有两种处理这个问题的好方法。

首先，我可以使用nlogn排序(如QuickSort或MergeSort )对数组进行排序。然后，我可以在每个数组的开头放置一个指针。将每个数组与其下面的数组进行比较，迭代数组指针较小的数组，或者如果它们都相等，就会找到一个交集。

这是一个具有固定内存的O(nlogn)解决方案(因为一切都是就地完成的)。

第二种解决方案是使用哈希映射，将第一个数组中出现的值作为键放入，然后在遍历其余数组时递增这些值(然后获取所有值为N的值)。这是一个O(n)解决方案，具有O(n)内存，其中n是所有数组的总大小。

理论上，前者是o(nlogn)，后者是O(n)。但是，哈希映射没有很大的局部性，因为由于冲突，项可以随机分散在映射中。另一种解决方案，尽管是o(nlogn)，一次遍历一个数组，显示出良好的局部性。由于CPU将倾向于将当前索引旁边的数组值从内存中提取到缓存中，所以O(nlogn)解决方案将比散列映射解决方案更频繁地访问缓存。

因此，如果数组的大小非常大(当元素数达到无穷大时)，o(nlogn)解实际上比O(n)解更快是否可行？

Answer 1

对于整数，可以使用非比较排序(请参见计数，基数排序)。可能会对一个大集合进行编码，例如顺序运行到范围。这将压缩数据集并允许跳过大块(请参阅RoaringBitmaps)。有可能是硬件友好和具有O(n)复杂性。

复杂性理论不考虑常数。正如您所怀疑的，由于隐藏常量，具有更高复杂度的算法总是比替代算法更快。通过利用问题的性质，例如将解决方案限制在整数上，就有可能进行优化，而这种优化并不适用于一般的方法。好的算法设计通常需要理解和利用这些约束。