Efficient number occurence count

4 ビュー (過去 30 日間)
Jan Siegmund
Jan Siegmund 2020 年 10 月 17 日
編集済み: Jan Siegmund 2020 年 10 月 18 日
I want to efficiently count the number of occurences of numbers between 1-numel(num) in a Matrix. I came up with two options for that:
sz = [3000 2000];
mx = prod(sz);
num = randi([1 mx],sz);
tic;
% First option
counts = zeros(numel(num),1);
for i = 1:numel(num)
counts(num(i)) = counts(num(i)) + 1;
end
toc
tic;
% Second option
uni = unique(num);
uni = reshape(uni,[],1);
hc = histcounts(num,[uni;uni(end)]);
toc
Execution times are:
Elapsed time is 0.098540 seconds.
Elapsed time is 0.342214 seconds.
So option 1 is clearly faster. However the for loop bugs me. Is there any possibility to vectorize this?
  3 件のコメント
Adam Danz
Adam Danz 2020 年 10 月 18 日
"I want to efficiently count the number of occurences of numbers between 1-numel(num) in a Matrix"
I'm a bit lost. Your matrix contains integers between 1 and 1000 and has 6000000 values (3000x2000). So, why are you looking for 6000000 different values when you only have a max of 1000 values?
Jan Siegmund
Jan Siegmund 2020 年 10 月 18 日
Sorry, num was a stupid example. A more suitable would be
sz = [3000 2000];
mx = prod(sz);
num = randi([1 mx],sz);
%...

サインインしてコメントする。

採用された回答

Matt J
Matt J 2020 年 10 月 18 日
編集済み: Matt J 2020 年 10 月 18 日
In this situation, accumarray will be faster than histcounts, but still not as fast as the for-loop,
tic;
hc=accumarray(num(:),1,[mx,1]).';
toc
Elapsed time is 0.172890 seconds. %for-loop
Elapsed time is 0.236013 seconds. %accumarray
unless the values are pre-sorted,
num=sort(num(:));
tic;
hc=accumarray(num(:),1,[mx,1]).';
toc
Elapsed time is 0.168976 seconds. %for-loop
Elapsed time is 0.075965 seconds. %accumarray
I think this is simply one of those situations where Matlab's for-loop optimization has caught up to vectorized code.
  1 件のコメント
Jan Siegmund
Jan Siegmund 2020 年 10 月 18 日
Alright, accumarray is also a great choice. Thank you for your time and effort. This is the answer I am going to accept.

サインインしてコメントする。

その他の回答 (2 件)

Bruno Luong
Bruno Luong 2020 年 10 月 18 日
ac = accumarray(num(:),1);

Matt J
Matt J 2020 年 10 月 18 日
編集済み: Matt J 2020 年 10 月 18 日
I want to efficiently count the number of occurences of numbers between 1-numel(num) in a Matrix
If that's really what you want, then
hc = histcounts(num(:), 1:numel(num)+1 );
but as Adam points out, it would make more sense to have
hc = histcounts(num(:), 1:1001 );
  3 件のコメント
Jan Siegmund
Jan Siegmund 2020 年 10 月 18 日
Ok no, the branching is not the problem. Calling
matlab.internal.math.histcounts
directly only results in a minor improvement.
Matt J
Matt J 2020 年 10 月 18 日
編集済み: Matt J 2020 年 10 月 18 日
I think the for-loop is the fastest for integer data ranges that large. Unfortunately (and strangely), histcounts cannot innately recognize that the data consists only of integers and use a simpler binning method for that case. There is an input option 'BinMethod'='integers' that is offered, however, it will not permit more than 65536 bins.

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeLogical についてさらに検索

製品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by