交集算法有两个未排序，小阵 [英] Intersection algorithm for two unsorted, small array

问题描述

我在寻找一种算法为两头小，无序排列的交点在非常特殊的情况。

I'm looking for an algorithm for intersection of two small, unsorted array in very specific condition.

• 阵列产品类型仅仅是整数或整数样型。
• 显着量的时间（约30〜40％），一个或两个阵列可能是空的。
• 在阵列通常都非常小 - 通常是1〜3项，我不希望超过10
。
• 的交集功能会很频繁地调用。
• 我不关心依赖于平台的解决方案 - 我的工作在x86 /窗/ C ++

这两个蛮力/排序和相交的解决方案也不差，但我不认为他们是速度不够快。是否有更优化的解决方案？

Both brute-force/sort-and-intersect solutions are not that bad, but I don't think that they're fast enough. Is there more optimal solution?

推荐答案

由于数组是原始类型，和短到足以在高速缓存行，快速的实现将侧重于比较的战术机制，而不是大O复杂如避免哈希表，因为它们一般会涉及散列和间接和总是涉及很多管理开销。

As the arrays are of primitive types, and short enough to be in cache lines, a fast implementation would focus on the tactical mechanics of comparisons rather than the big O complexity e.g. avoid hash-tables as these would generally involve hashing and indirection and would always involve a lot of management overhead.

如果您有两个有序数组，然后交集是O（N + M）。你说的那种，然后相交是蛮力，但你不能更快地做到这一点。

If you have two sorted arrays, then intersection is O(n+m). You say that sort-then-intersect is 'brute-force' but you can't do it quicker.

如果该阵列的保存的排序，当然，你还可以获得像你说的，你所呼叫的交汇频繁。

If the arrays are stored sorted, of course, you gain further as you say you are calling the intersection often.

的交点本身可以​​是与上证所完成。

The intersection itself can be done with SSE.

这篇关于交集算法有两个未排序，小阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！