查找和乘以数组中重复值的最快方法

Question

在数组中查找和重复它们之间的重复值的最快方法是什么？

例:

a = [ 2 2 3 5 11 11 17 ]

结果:

a = [ 4 3 5 121 17 ]

我可以想到迭代的方法(通过查找hist,迭代bin,......),但是有没有矢量化/快速方法？

Answer 1

前瞻性方法和解决方案代码

似乎贴出来的问题非常适合accumarray-

%// Starting indices of each "group"
start_ind = find(diff([0 ; a(:)]))

%// Setup IDs for each group
id = zeros(1,numel(a)) %// Or id(numel(a))=0 for faster pre-allocation
id(start_ind) = 1

%// Use accumarray to get the products of elements within the same group
out = accumarray(cumsum(id(:)),a(:),[],@prod)

对于非单调增加的输入,您需要再添加两行代码 -

[~,sorted_idx] = ismember(sort(start_ind),start_ind)
out = out(sorted_idx)

样品运行 -

>> a
a =
     2     2     3     5    11    11    17     4     4     1     1     1     7     7
>> out.'
ans =
     4     3     5   121    17    16     1    49

Tweaky,吱吱

现在,人们可以利用logical indexing删除find并使用更快的预分配方案来为提议的方法提供超级提升并给我们一个调整代码 -

id(numel(a))=0;
id([true ; diff(a(:))~=0])=1;
out = accumarray(cumsum(id(:)),a(:),[],@prod);

标杆

这是基准测试代码,它比较了迄今为止针对运行时所述问题发布的所有建议方法 -

%// Setup huge random input array
maxn = 10000;
N = 100000000;
a = sort(randi(maxn,1,N));

%// Warm up tic/toc.
for k = 1:100000
    tic(); elapsed = toc();
end

disp('------------------------- With UNIQUE')
tic
ua = unique(a);
out = ua.^histc(a,ua);
toc, clear ua out

disp('------------------------- With ACCUMARRAY')
tic
id(numel(a))=0;
id([true ; diff(a(:))~=0])=1;
out = accumarray(cumsum(id(:)),a(:),[],@prod);
toc, clear out id

disp('------------------------- With FOR-LOOP')
tic
b = a(1);
for k = 2:numel(a)
    if a(k)==a(k-1)
        b(end) = b(end)*a(k);
    else
        b(end+1) = a(k);
    end
end
toc

运行时

------------------------- With UNIQUE
Elapsed time is 3.050523 seconds.
------------------------- With ACCUMARRAY
Elapsed time is 1.710499 seconds.
------------------------- With FOR-LOOP
Elapsed time is 1.811323 seconds.

结论:看起来运行时,支持accumarray其他两种方法的想法!

Answer 2

使用histc和unique:

ua = unique(a)
out = ua.^histc(a,ua)

out =

     4     3     5   121    17

考虑的情况下,该矢量a是不单调递增,它变得有点复杂:

%// non monotonically increasing vector
a = [ 2 2 3 5 11 11 17 4 4 1 1 1 7 7]

[ua, ia] = unique(a)             %// get unique values and sort as required for histc  
[~, idx] = ismember(sort(ia),ia) %// get original order
hc = histc(a,ua)                 %// count occurences
prods = ua.^hc                   %// calculate products
out = prods(idx)                 %// reorder to original order

要么:

ua = unique(a,'stable')          %// get unique values in original order
uas = unique(a)                  %// get unique values sorted as required for histc  
[~,idx] = ismember(ua,uas)       %// get indices of original order
hc = histc(a,uas)                %// count occurences
out = ua.^hc(idx)                %// calculate products and reorder 

out =

     4     3     5   121    17    16     1    49

似乎仍然是一个很好的解决方案accumarray也没有提供默认情况下一个稳定的版本.