在一个数组中查找唯一值的最快方法

Question

我正在尝试找到一种最快的方法来查找数组中的唯一值，并将 0 作为唯一值的可能性移除。

目前我有两个解决方案：

result1 = setxor(0, dataArray(1:end,1)); % This gives the correct solution
result2 = unique(dataArray(1:end,1)); % This solution is faster but doesn't give the same result as result1

dataArray 等同于：

dataArray = [0 0; 0 2; 0 4; 0 6; 1 0; 1 2; 1 4; 1 6; 2 0; 2 2; 2 4; 2 6]; % This is a small array, but in my case there are usually over 10 000 lines.

因此，在这种情况下，result1 等于 [1; 2]，而 result2 等于 [0; 1; 2]。 unique 函数更快，但我不希望将 0 视为唯一值。有没有办法使用 unique 并不考虑 0 作为唯一值？还有其他替代方法吗？ 编辑 我想计算各种解决方案的时间。

clc
dataArray = floor(10*rand(10e3,10));
dataArray(mod(dataArray(:,1),3)==0)=0;
% Initial
tic
for ii = 1:10000
   FCT1 = setxor(0, dataArray(:,1));
end
toc
% My solution
tic
for ii = 1:10000
   FCT2 = unique(dataArray(dataArray(:,1)>0,1));
end
toc
% Pursuit solution
tic
for ii = 1:10000
   FCT3 = unique(dataArray(:, 1));
   FCT3(FCT3==0) = [];
end
toc
% Pursuit solution with chappjc comment
tic
for ii = 1:10000
   FCT32 = unique(dataArray(:, 1));
   FCT32 = FCT32(FCT32~=0);
end
toc
% chappjc solution
tic
for ii = 1:10000
   FCT4 = setdiff(unique(dataArray(:,1)),0);
end
toc
% chappjc 2nd solution
tic
for ii = 1:10000
   FCT5 = find(accumarray(dataArray(:,1)+1,1))-1;
   FCT5 = FCT5(FCT5>0);
end
toc

结果如下：

Elapsed time is 5.153571 seconds. % FCT1 Initial
Elapsed time is 3.837637 seconds. % FCT2 My solution
Elapsed time is 3.464652 seconds. % FCT3 Pursuit solution
Elapsed time is 3.414338 seconds. % FCT32 Pursuit solution with chappjc comment
Elapsed time is 4.097164 seconds. % FCT4 chappjc solution
Elapsed time is 0.936623 seconds. % FCT5 chappjc 2nd solution

然而，使用 sparse 和 accumarray 的解决方案仅适用于 integer。这些解决方案对于 double 不起作用。

- m_power

---

你可能想尝试更长的dataArray时间而不是更多的迭代次数。但只是为了好玩，加入FCT3 = FCT3(FCT3~=0);，因为这通常比分配[]更快。 - chappjc

@chappjc 第二个解决方案目前似乎是最快的 :D。 - m_power

@m_power 请查看Floris的答案，以及他的测试数据命令，这些命令可以删除一些元素以进行更强大的测试。如果您愿意，您也可以使用rand(10e3,10)一次性处理所有10列。 - chappjc

@m_power 正如我在下面的评论中提到的，即使使用 unique 函数，浮点数也会带来一些挑战。请参见此处和此处。请考虑是否可以使用整数值索引而不是浮点数值进行操作。 - chappjc

受到@chappjc最后一条评论的启发，我又更新了一次我的答案... - Floris

Answer 1

以下是一个用accumarray实现的疯狂想法，使用了Floris的测试数据进行演示：

a = floor(10*rand(100000, 1)); a(mod(a,3)==0)=0;
result = find(accumarray(nonzeros(a(:,1))+1,1))-1;

感谢Luis Mendo指出使用nonzeros，不需要执行result = result(result>0)！

请注意，此解决方案需要整数型数据（不一定是整数数据类型，但不能带有小数部分）。与unique一样，比较浮点值是否相等是很危险的。请参见这里和这里。

---

原始建议：将unique与setdiff组合使用：

result = setdiff(unique(a(:,1)),0)

或者在使用unique之后使用逻辑索引进行删除：

result = unique(a(:,1));
result = result(result>0);

通常我不喜欢使用[]进行赋值（例如：result(result==0)=[];）。这样对于大型数据集来说效率很低。

在使用unique函数之后移除零应该会更快，因为它处理的数据量较小（除非每个元素都是唯一的，或者a/dataArray 非常短）。

- chappjc

---

@m_power 需要像其他解决方案一样只使用第一列 (a(:,1))。已更新。 - chappjc

有点古怪，但是非常快！ - Floris

如果a数组中有double，我会收到错误消息First input SUBS must contain positive integer subscripts.。 - m_power

@m_power 我会根据所期望的值重新考虑这个问题。它们是连续的还是某些确定的值。在双精度上使用unique存在问题，尽管它会让你运行它。注意。 - chappjc

@chappjc +1，但为什么不在accumarray之前移除零元素呢？：result = find(accumarray(nonzeros(a(:,1))+1,1)-1);。在我的电脑上，这样做会稍微节省一些时间。 - Luis Mendo

Answer 2

为了增加普遍的喧哗声 - 这里有三种不同的方法。它们都给出相同的答案，但时间略有不同：

a = floor(10*rand(100000, 1));
a(mod(a,3)==0)=0;
tic
b1 = unique(a(:,1));
b1(b1==0) = [];
toc
tic
b2 = find(sparse(a(:,1)+1, 1, 1)) - 1;
b2(b2==0)=[];
toc
tic
b3 = setxor(0, a(:, 1), 'rows');
toc

display(b1)
display(b2)
display(b3)

在我的机器上，对于一个包含100000个元素的数组，时间如下所示：

0.0087 s  - for unique
0.0142 s  - for find(sparse)
0.0302 s  = for setxor

我觉得在这种情况下，sparse 是一个很好的选择 - 你可以同时获得元素数量和它们唯一的值。

编辑根据@chappj的建议，我添加了第四个选项。

b4 = find(accumarray(a(:,1)+1,1)-1);
b4(b4==0) = [];

时间:

0.0029 s , THREE TIMES FASTER THAN UNIQUE

女士们先生们，我们有一个获胜者。

后记：基于索引的方法（sparse和accumarray）仅适用于整数值输入（尽管它们可以是double类型）。这似乎对于问题中给出的输入数组来说没有问题，但对于非整数值输入则无法正常工作。当然，当你有双倍数时，“唯一”是一个棘手的概念 - 看起来相同的数字可能被表示为不同的数字。您可以考虑截断输入数组（清理数据），以确保这不是一个问题。例如，如果你这样做：

a = 0.001 * double(int(a * 1000));

您需要将所有的值四舍五入到不超过3个有效数字，并且因为您通过“int”进行了转换，所以您可以确信不会出现“非常微妙的差异”（例如在第8位或更远的小数位）。当然，在这种情况下，您也可以执行以下操作：

a = round(a * 1000);
mina = min(a(:));
b = find(accumarray(a - mina + 1, 1)) + mina - 1;
b = 0.001 * b(b ~= 0);

对于非整数值，这种方法相当稳健（在上述情况下，它可以处理具有最多三个有效数字的值；如果您需要更多，则空间要求最终会变得过大，这种方法会比unique慢，实际上必须对数据进行排序。）

- Floris

---

我更喜欢使用accumarray而不是sparse。想要添加时间记录。 ;) - chappjc

@chappjc 那是一个非常好的建议。在我的机器上，它快了3倍！ - Floris

<鞠躬>谢谢，谢谢。</鞠躬>但很可能只是时间问题，更快的会出现的。;) - chappjc

你的第三个解决方案是正确的，但是我不能用它来做我需要的事情。我需要具有完全相同的值，而不是舍入后的值。 - m_power

@m_power 能否在Dropbox或类似的地方发布一些实际数据。我对不使用公差（包括“unique”）的任何解决方案都持怀疑态度，因为测试浮点值的相等性很少能按预期工作。请提供更多信息。 - chappjc

@Floris 正如我刚刚在 chappjc 的回答中评论的那样：为什么不_最初_删除零元素呢？在 accumarray 版本中，这似乎可以节省一点时间（在我的计算机上）：b5 = find(accumarray(nonzeros(a(:,1))+1,1)-1)。 - Luis Mendo

Answer 3

为什么不在第二步中删除零：

result2 = unique(.....);
result2 = (result2~=0);

- Pursuit

---

result2 = result2(result2 ~= 0) 可能更快：https://dev59.com/xWjWa4cB1Zd3GeqPqnFx - Dan

Answer 4

我还发现了另一种方法：

result2 = unique(dataArray(dataArray(:,1)>0,1));

- m_power

---

只是一个小技巧：1:end与仅使用:是相同的。但是，是的，这是一个可行的解决方案。 - chappjc

严格来说，您应该使用 dataArray(:,1)~=0 来允许负数的可能性。但我怀疑，删除末尾多余的零（操作更小的数组）会更快。 - Floris