两个排序整型数组的快速交集 [英] Fast intersection of two sorted integer arrays
问题描述
我需要找到两个排序整数数组的交集并做到这一点非常快。
现在，我使用下面的code：
INT I = 0，J = 0;
而（I＆LT; arr1.Count和放大器;＆放大器; J＆LT; arr2.Count）
{
如果（ARR1 [1] - ; ARR2 [J]。）
{
我++;
}
其他
{
如果（ARR2 [J] LT; ARR1 [I]）
{
J ++;
}
其他
{
intersect.Add（ARR2 [J]）;
J ++;
我++;
}
}
}
不幸的是它可能需要几个小时来完成所有的工作。
如何更快地做到这一点？我发现这篇文章，其中SIMD指令的使用。是否有可能在.NET中使用SIMD？
你怎么思考：
<一个href="http://docs.go-mono.com/index.aspx?link=N:Mono.Simd">http://docs.go-mono.com/index.aspx?link=N:Mono.Simd Mono.SIMD
HTTP：//netasm.$c$cplex.com/ NetASM（注ASM code到管理）
和像<一个href="http://www.atrevido.net/blog/PermaLink.aspx?guid=ac03f447-d487-45a6-8119-dc4fa1e932e1">http://www.atrevido.net/blog/PermaLink.aspx?guid=ac03f447-d487-45a6-8119-dc4fa1e932e1
＆NBSP;
编辑：
当我说十万我的意思如下（code）
的（VAR I = 0; I＆LT; arrCollection1.Count-1;我++）
{
对于（VAR J = I + 1; J＆LT; arrCollection2.Count; J ++）
{
相交（arrCollection1 [我]，arrCollection2 [J]。）
}
}
更新
我得到的最快的是200ms的数组大小10MIL，与不安全的版本（最后一张code）。
测试我所做的：
VAR ARR1 =新INT [千万]
VAR ARR2 =新INT [千万]
对于（VAR I = 0; I＆LT;千万;我++）
{
ARR1 [我] =我;
ARR2 [我] = I * 2;
}
变种SW = Stopwatch.StartNew（）;
VAR的结果= arr1.IntersectSorted（ARR2）;
sw.Stop（）;
Console.WriteLine（sw.Elapsed）; // 00：00：00.1926156
全文后：
我已经尝试了各种方法来做到这一点，并发现这是非常好的：
公共静态列表＆LT; INT＆GT; IntersectSorted（这INT []来源，INT []目标）
{
//设置初始容量，以全交集大小
//这个prevents多次重新分配
VAR整数=新的名单，其中，INT＆GT;（Math.Min（source.Length，target.Length））;
变种I = 0;
变种J = 0;
而（I＆LT; source.Length和放大器;＆放大器; J＆LT; target.Length）
{
//比较只有一次，让编译器优化的switch-case
开关（来源[I] .CompareTo（目标[J]））
{
情况1：
我++;
//为我们节省了JMP指令
继续;
情况1：
J ++;
//为我们节省了JMP指令
继续;
默认：
ints.Add（来源[I ++]）;
J ++;
//为我们节省了JMP指令
继续;
}
}
//释放未使用的内存（套容量为实际计数）
ints.TrimExcess（）;
返回整数;
}
有关进一步的改进，你可以删除 ints.TrimExcess（）; ，这也将是一个不错的差异，但你应该想想，如果你要需要的内存。
另外，如果你知道你可能会破坏使用的交叉循环，你不必有结果作为一个数组/列表，你应该改变的实施，一个迭代器：
公共静态的IEnumerable＆LT; INT＆GT; IntersectSorted（这INT []来源，INT []目标）
{
变种I = 0;
变种J = 0;
而（I＆LT; source.Length和放大器;＆放大器; J＆LT; target.Length）
{
//比较只有一次，让编译器优化的switch-case
开关（来源[I] .CompareTo（目标[J]））
{
情况1：
我++;
//为我们节省了JMP指令
继续;
情况1：
J ++;
//为我们节省了JMP指令
继续;
默认：
收益回报源[我++];
J ++;
//为我们节省了JMP指令
继续;
}
}
}
另一个改进是使用不安全的code：
公共静态不安全的名单，其中，INT＆GT; IntersectSorted（这INT []来源，INT []目标）
{
VAR整数=新的名单，其中，INT＆GT;（Math.Min（source.Length，target.Length））;
固定（INT *的ptSrc =源）
{
VAR maxSrcAdr =的ptSrc + source.Length;
固定（INT * PTTAR =目标）
{
VAR maxTarAdr = PTTAR + source.Length;
VAR currSrc =的ptSrc;
VAR currTar = PTTAR;
而（currSrc＆LT; maxSrcAdr和放大器;＆安培; currTar＆LT; maxTarAdr）
{
开关（（* currSrc）.CompareTo（* currTar））
{
情况1：
currSrc ++;
继续;
情况1：
currTar ++;
继续;
默认：
ints.Add（* currSrc）;
currSrc ++;
currTar ++;
继续;
}
}
}
}
ints.TrimExcess（）;
返回整数;
}
总结下，最为主要的性能损失是在如果其他的。 把它变成一个开关的情况下作出了巨大的差异（快约2倍）。
I need to find the intersection of two sorted integer arrays and do it very fast.
Right now, I am using the following code:
int i = 0, j = 0;
while (i < arr1.Count && j < arr2.Count)
{
if (arr1[i] < arr2[j])
{
i++;
}
else
{
if (arr2[j] < arr1[i])
{
j++;
}
else
{
intersect.Add(arr2[j]);
j++;
i++;
}
}
}
Unfortunately it might to take hours to do all work.
How to do it faster? I found this article where SIMD instructions are used. Is it possible to use SIMD in .NET?
What do you think about:
http://docs.go-mono.com/index.aspx?link=N:Mono.Simd Mono.SIMD
http://netasm.codeplex.com/ NetASM(inject asm code to managed)
and something like http://www.atrevido.net/blog/PermaLink.aspx?guid=ac03f447-d487-45a6-8119-dc4fa1e932e1
EDIT:
When i say thousands i mean following (in code)
for(var i=0;i<arrCollection1.Count-1;i++)
{
for(var j=i+1;j<arrCollection2.Count;j++)
{
Intersect(arrCollection1[i],arrCollection2[j])
}
}
UPDATE
The fastest I got was 200ms with arrays size 10mil, with the unsafe version (Last piece of code).
The test I've did:
var arr1 = new int[10000000];
var arr2 = new int[10000000];
for (var i = 0; i < 10000000; i++)
{
arr1[i] = i;
arr2[i] = i * 2;
}
var sw = Stopwatch.StartNew();
var result = arr1.IntersectSorted(arr2);
sw.Stop();
Console.WriteLine(sw.Elapsed); // 00:00:00.1926156
Full Post:
I've tested various ways to do it and found this to be very good:
public static List<int> IntersectSorted(this int[] source, int[] target)
{
// Set initial capacity to a "full-intersection" size
// This prevents multiple re-allocations
var ints = new List<int>(Math.Min(source.Length, target.Length));
var i = 0;
var j = 0;
while (i < source.Length && j < target.Length)
{
// Compare only once and let compiler optimize the switch-case
switch (source[i].CompareTo(target[j]))
{
case -1:
i++;
// Saves us a JMP instruction
continue;
case 1:
j++;
// Saves us a JMP instruction
continue;
default:
ints.Add(source[i++]);
j++;
// Saves us a JMP instruction
continue;
}
}
// Free unused memory (sets capacity to actual count)
ints.TrimExcess();
return ints;
}
For further improvement you can remove the ints.TrimExcess();, which will also make a nice difference, but you should think if you're going to need that memory.
Also, if you know that you might break loops that use the intersections, and you don't have to have the results as an array/list, you should change the implementation to an iterator:
public static IEnumerable<int> IntersectSorted(this int[] source, int[] target)
{
var i = 0;
var j = 0;
while (i < source.Length && j < target.Length)
{
// Compare only once and let compiler optimize the switch-case
switch (source[i].CompareTo(target[j]))
{
case -1:
i++;
// Saves us a JMP instruction
continue;
case 1:
j++;
// Saves us a JMP instruction
continue;
default:
yield return source[i++];
j++;
// Saves us a JMP instruction
continue;
}
}
}
Another improvement is to use unsafe code:
public static unsafe List<int> IntersectSorted(this int[] source, int[] target)
{
var ints = new List<int>(Math.Min(source.Length, target.Length));
fixed (int* ptSrc = source)
{
var maxSrcAdr = ptSrc + source.Length;
fixed (int* ptTar = target)
{
var maxTarAdr = ptTar + source.Length;
var currSrc = ptSrc;
var currTar = ptTar;
while (currSrc < maxSrcAdr && currTar < maxTarAdr)
{
switch ((*currSrc).CompareTo(*currTar))
{
case -1:
currSrc++;
continue;
case 1:
currTar++;
continue;
default:
ints.Add(*currSrc);
currSrc++;
currTar++;
continue;
}
}
}
}
ints.TrimExcess();
return ints;
}
In summary, the most major performance hit was in the if-else's. Turning it into a switch-case made a huge difference (about 2 times faster).
这篇关于两个排序整型数组的快速交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
