由网友(凉心暖男√)分享简介：我在寻找一种算法为两头小，无序排列的交点在非常特殊的情况。I'm looking for an algorithm for intersection of two small, unsorted array in very specific condition.阵列产品类型仅仅是整数或整数样型。显着量的时间（约30...

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

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.