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

 欣欣然人人宇 发布于 2023-02-09 13:09

我正在尝试找到一种最快的方法来查找数组中的唯一值,并删除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.

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
    

    女士们,先生们,我们有一个胜利者.

    AFTERWORD基于索引的方法(sparseaccumarray)仅适用于整数值输入(尽管它们可以是double类型).根据问题中给出的输入数组,这似乎没问题,但不适用于非整数值输入.当然,unique当你有双打时,这是一个棘手的概念 - "看起来"相同的数字可能用不同的方式表示.您可以考虑截断输入数组(清理数据)以确保这不是问题.例如,如果你这样做了

    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,实际上必须对数据进行排序.)

    2023-02-09 13:11 回答
  • 这是一个古怪的建议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非常短).

    2023-02-09 13:12 回答
撰写答案
今天,你开发时遇到什么问题呢?
立即提问
热门标签
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有