Fast method count unique variables

2017 5 3
3 个回答
回答已采纳
更新时间：2017 5 8
5 次查看（30 天）

1 个投票

Ok so given an array of (n,m) dimensions populated with positive integers from 1:m and each row of the array will contain only one of each integer: so no repeats.
For example:
2,1,3,4
3,1,2,4
1,2,3,4
2,1,4,3
I'd like a fast method of creating arrays containing all the positions that the numbers fall into, for example:
One.positions = [1,2]
Two.positions = [1,2,3]
Three.postions = [1,3,4]
Four.positions = [3,4]
I'm doing this for arrays sometimes of sizes = [1e+6,30]; currently I'm using a loop moving column wise with accummarray and if the number exists in that Column it is iteratively added to an array.
Original Code:
% m = array containing sequences of integers
total = size(m,2)
A = (1:total);
intel_pos = cell(total,1);
for i = 1:total
for j = 1:total
if sum(A(accumarray(m(:,j),1) > 0) == i) == 1
intel_pos{i} = [intel_pos{i};j];
end
end
end
So obvious areas of improvement can be done.

请先登录，再回答此问题。

 采纳的回答

David Goodmanson
David Goodmanson 2017-5-3
编辑：David Goodmanson 2017-5-5

0 个投票

Revised answer. For a 7e6 x 30 matrix this takes about 2.7 sec on my PC.
m8 = uint8(m);
u1 = uint8(1);
ncol = size(m8,2);
nmax = ncol; % in your case. otherwise nmax = max(max(m))
A = zeros(nmax,ncol);
locations = cell(nmax,1);
% create matrix with j,k element = 1 if integer j is found in column k, 0 otherwise
for k = 1:ncol
A(m8(:,k),k) = u1;
end
for k = 1:nmax
locations{k} = find(A(k,:));
end
based on the principle that if you set an element to 1, it doesn't matter if you have set it to 1 a thousand times already.

2 个评论
显示 无 隐藏 无

Matthew Hickson
Matthew Hickson 2017-5-8
Yeah this is now the fastest answer, I improved it by about 5% by using logical indexing instead of find, and this speed is pretty darn fast so I'm going to leave this answer as accepted. It was twice as fast as my improved version of Sean's method so this is definitely acceptable, thank you
David Goodmanson
David Goodmanson 2017-5-8
You're welcome, it was a good problem. I realized that I forgot to set A equal to a uint8 matrix so it is inconsistent to use u1 instead of 1 in the for loop. Actually it does not seem to make much difference speedwise if A is double and its elements are set 1 or if A is uint8 and its elements are set to u1.

请先登录，再进行评论。

更多回答（2 个）

Guillaume
Guillaume 2017-5-3

1 个投票

No idea if it's faster than your method, this does not need a loop:
m = [2 1 3 4;1 2 3 4;1 2 4 3;2 1 4 3]; %demo data
colindices = repmat(1:size(m, 2), size(m, 1), 1);
out = accumarray(m(:), colindices(:), [], @(x) {unique(x)})

2 个评论
显示 无 隐藏 无

Sean de Wolski
Sean de Wolski 2017-5-3
Loops are not typically slower. This was true 15 years ago but with advances in the MATLAB execution engine and jit accelerator they are now at parity with vectorized operations much of the time.
Matthew Hickson
Matthew Hickson 2017-5-3
编辑：Matthew Hickson 2017-5-3
That may be true and don't get me wrong I use loops all the time but the real hindrance to this was unique(x) which is a slow function. This is the fastest suggestion made that actually completes the task though, but I feel like further improvements could be made and with less memory use.
Replacing {unique(x)} with {A(ismember(1:total,x))} where A = 1:m is faster

请先登录，再进行评论。

Sean de Wolski
Sean de Wolski 2017-5-3
编辑：Sean de Wolski 2017-5-4

1 个投票

I'd suspect a simple loop over columns with ismember would be very fast.
EDIT from Comment Clarification
tic
ncol = size(m,2);
nrow = size(m,1);
present = cell(ncol,1);
for ii = 1:ncol
present{ii} = unique(ceil(find(m==ii)./nrow));
end
toc
OLD
[~,m] = sort(rand(1e6,30),2);
tic
ncol = size(m,2)
present = cell(ncol,1);
for ii = 1:ncol
present{ii} = find(ismember(1:ncol,m(:,ii)));
end
toc
This is taking 0.9s on my laptop.

6 个评论
显示 4更早的评论 隐藏 4更早的评论

Matthew Hickson
Matthew Hickson 2017-5-3
Actually this doesn't satisfy the condition that I have, which is that an array of the allowable positions of each entity is known. My question example didn't portray that accurately so that's my mistake. However, your code would just generate a cell array containing each variable in a given position and not each position thats allowed for a given variable.
Sean de Wolski
Sean de Wolski 2017-5-3
Can you be more specific? I don't understand the difference between "allowed" and "at a given position". Maybe a counter example with the same original data set?
Matthew Hickson
Matthew Hickson 2017-5-3
编辑：Matthew Hickson 2017-5-3
So for example:
1,2,3,4
1,3,2,4
1,3,4,2
would produce:
1 - can be in position = [1]
2 - can be in position = [2,3,4]
3 - can be in position = [2,3]
4 - can be in position = [3,4]
Does that make sense? Sorry about the confusion, wording this is difficult since in my head it makes so much sense, but explaining it obviously can get misinterpreted.
Matthew Hickson
Matthew Hickson 2017-5-4
编辑：Matthew Hickson 2017-5-4
Examining your EDIT, your code successfully satisfies the problem, using both find and especially unique is slow, so I will remove them and see if its faster than the above mentioned answer using accumarray with no loop. At the present moment though it is slower by about 20% for arrays of size 20000 x 20:
I managed to improve the speed by about 2 times using:
A = (1:size(m,2));
for ii = 1:ncol
present{ii} = A(sum((m==ii),1) > 0);
end
For an array 6684672 x 30 in size;
-
The time of my improved version of your method is: 5.425416 seconds.
The time of my improved version of the repmat method in another answer is: 8.857116 seconds.
-
So now I assume sum is optimised so theres no faster way to do that.
Good news is this method is now the fastest suggested and uses considerably less memory than repmat. Any suggestions on further improvements?
David Goodmanson
David Goodmanson 2017-5-5
Hi Matthew, I have done a revised answer, which is about three times faster than the code listed above.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by