2

所以我有一组两个 x、y、z 点列表。

List1 and List2.

我想删除 List1 中存在的所有点，这些点也存在于 List2 中。在此示例中，List2 中的大多数点（可能 100%）将存在于 List1 中。例子：

清单 1

1, 2, 3
4, 5, 6
7, 8, 9

清单2

7, 8, 9

输出

1, 2, 3
4, 5, 6

这将发生在每个列表大小的数千个点上。显然，这可以通过遍历 List2 并搜索时间为 O(n*m) 的列表 1 来完成。有没有更快、更原生的 matlab 方法来做到这一点？

谢谢您的帮助。

4

3 回答 3

4

尝试： SETDIFF(List1, List2, 'rows')

（我不知道这有多有效，但由于它是一种本机方法，它可能已经过优化。）

于 2012-06-29T05:19:18.603 回答
2

@Turix 的setdiff选项应该有效。另一种选择（只是为了踢）是

List1(~ismember(List1,List2,'rows'), :);
于 2012-06-29T05:29:50.880 回答
2

我发现了一种稍微快一点（虽然不太通用）的方法来做到这一点。第一个答案，请耐心等待我学习格式化...

我没有发现值得注意的缩放效果，因此我将使用以下 Lists 对象作为示例：

example_step=3;
max_value_outer=example_step*333;
max_value_inner=example_step*33;
List1=[1:example_step:max_value_outer; 2:example_step:max_value_outer; 3:example_step:max_value_outer]';
List2=[1:example_step:max_value_inner; 2:example_step:max_value_inner; 3:example_step:max_value_inner]';

Turix 的内置 setdiff 调用提供了迄今为止最好的结果，在不到 3 秒的时间内运行以下代码块：

tic; 
  for i=1:10000 result=setdiff(list1,list2,'rows'); 
  end;
toc
>> Elapsed time is 2.821303 seconds.

但是，如果您的示例数据集代表您的数据是向量、整数并且在合理有限的范围内的事实，那么您可以通过使用 sub2ind 比较等价的线性索引而不是三元组来加快速度，如下所示：

range=max_value_outer*ones(1,3);
[c,ia] = setdiff(sub2ind(range,List1(:,1),List1(:,2),List1(:,3)), sub2ind(range,List2(:,1),List2(:,2),List2(:,3))); result=List1(ia,:);
  result=List1(ia,:);

如果您运行 10,000 次以按行与直接 setdiff 进行比较，您会得到这个

tic;
for i=1:10000 
  range=max_value_outer*ones(1,3); 
  [c,ia] = setdiff(sub2ind(range,List1(:,1),List1(:,2),List1(:,3)), sub2ind(range,List2(:,1),List2(:,2),List2(:,3))); 
  result=List1(ia,:); 
end; 
toc
>> Elapsed time is 2.285992 seconds.

因此 setdiff(,,'row) 的执行时间减少了 %20 左右，而 for 循环实现减少了大约 98%（未显示）。根据您的数据的具体情况，我可以想到一些可能会进一步加快速度的想法。例如，如果您正在考虑的 maximum_value 与内存相比相对较小，您可以通过将样本空间映射到内存来利用线性索引，然后使用 List1 中的线性索引设置高位，然后使用 List2 中的设置来设置他们低。任何保持高位的位都将在 List1 上，但不在 List2 上。这里有一个简化版本，尽管我不保证该实现。

希望有帮助！

于 2012-06-29T19:21:30.747 回答