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

Question

在数组中找到和增加重复值的最快方法是什么？

示例：

a = [ 2 2 3 5 11 11 17 ]

结果：

a = [ 4 3 5 121 17 ]

我可以想到迭代的方法(通过找到hist，遍历回收箱，.)，但是有矢量化/快速方法吗？

Answer 1

使用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和doesn't offer a stable version by default一样，似乎仍然是一个很好的解决方案。

Answer 2

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

似乎发布的问题很适合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

奇奇奇

现在，我们可以使用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.

Conclusions:运行时似乎支持accumarray的思想，而不是其他两种方法！

Answer 3

您可能会惊讶于简单的for-loop在速度方面的比较：

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

即使不进行任何预分配，这也与accumarray解决方案相同。