寻找Matlab 2015中“intersect”函数的高效替代方案

Question

我有一个在MATLAB 2015中运行的程序，调用intersect函数超过500万次。例如：

x=[2,4,6,3]
y=[3,5,7,9,1,6,4]
tic;for i=1:5*1e6;t=intersect(x,y);end;toc;
*Elapsed time is 365.038992 seconds in my computer

由于intersect函数，我的程序速度太慢了，有没有一种更有效的替代方法？是否有内置函数或Mex或类似的东西。我也尝试过unique(x(ismember(x,y)))：

tic;for i=1:5*1e6;t=unique(x(ismember(x,y)));end;toc;
*Elapsed time is 227.7381 seconds in my computer

虽然这些改进有一定的作用，但这还不够！我在使用 unique() 和 ismember() 函数时也遇到了同样的问题。

- Reza Sh

---

如果 x 和 y 是静态的，那么你可以安全地将 intersect 从循环中提取出来。 - Yvon

你应该发布一个更好的例子，因为现在你正在重复相交同一个向量一百万次。我们需要一个更合适的数据集。最重要的问题是：由于相交的结果向量长度不同，应该如何存储它们？我猜你正在循环中直接使用相交的结果，所以我们还需要知道随后的函数。 - Robert Seifert

这还不够。根据您提供的信息，我们可能无法替换intersect，因为intersect是专门执行您想要的操作的函数。但也许我们可以加快整个上下文的速度。 - Robert Seifert

如果这个例子恰好符合您的实际用例，您可以尝试使用 sort(y(any(bsxfun(@eq,x(:),y(:).')))). - TroyHaskin

请定义您用于评估为什么Troy的代码与您所期望的代码相比“效率低下”的标准。 - rayryeng

Answer 1

这里有一个快速的解决方案，适用于所有情况（元素可以是非唯一的和/或非正的）。

tmp = sort(x(ismembc(x,sort(y))));
t = tmp([~~diff(tmp),true]);

基本思想与您的建议中的unique(x(ismember(x,y)))相同，但是ismember和unique都很慢，可以改进。我们可以使用内置的ismembc代替ismember，但需要确保第二个参数已排序。而且，我们使用sort、diff和逻辑索引的组合来代替unique。

这在Matlab 2013b上比intersect提高了约15.5倍：

>> tic; for i=1:1e5, tmp=sort(x(ismembc(x,sort(y)))); t = tmp([~~diff(tmp),true]); end; toc;
Elapsed time is 0.998081 seconds.

>> tic; for i=1:1e5, t = intersect(x,y); end; toc;
Elapsed time is 15.538410 seconds.

如果您知道x的元素是唯一的，那么您可以直接使用ismembc的结果，这将导致速度提高 ~33x ：

>> tic; for i=1:1e5, t = x(ismembc(x,sort(y))); end; toc;
Elapsed time is 0.465070 seconds.

基准测试结果在不同的Matlab版本和/或PC上可能会有所不同，但我相信结果无论如何都是一样的。

- nirvana-msu