Speed performance: Find all y-vector entries that have the same value in an x-vector of equal length.

Hi Guys,

imagine you have an x-vector

   x = [1 1 2 2 1 1];

as well as an y-vector of equal length.

    y = [1 2 3 4 5 6]

And you want to find out, which values the y-vector has at those indices where the x-vector has the value 1, as well as the y-vector values at those indices where the x-vector has the value 2. So that the solution for this example would be

solution = {[1 2 5 6], [3 4]} 

That is the first cell of 'solution' contains all y-values, that belong to the first unique x-value (1) & the second cell of it contains all y-values, that belong to the second unique x-value (2).

My ideas on how to implement this for vectors of any length are given below.

Does anybody has an idea, how to avoid the for-loop in approach A???

x = randi(10, 1, 100000);
y = randi(5, 1, 100000);

% Approach A:
tic 
xVals = unique(x); % get unique x values
tf = x == xVals';  % get true-or-false logical array (each row specifies where the n-th value of xVals occurs in x).
yVals = cell(1, size(tf,1)); % preallocate yVals
for i = 1:size(tf,1)
    yVals(i) = {y(tf(i,:))}; % Assign all y-values that belong to one xVal-entry to one cell.
end
toc

% Approach B: 
tic
[xs, id] = sort(x); % xsorted
ys = y(id); % sort y the same way x was sorted
[xVals, ia] = unique(xs);
% Divide the ys-vector into sections whose corresponding xs-indices have the same value in the xs vector.
yVals = mat2cell(ys, [1], [diff(ia)', length(ys)-sum(diff(ia))]); 
toc

% Runtimes:
%  x = randi(10, 1, 1000000);
%  y = randi(5, 1, 1000000);
%  A: Elapsed time is 0.100635 seconds.
%  B: Elapsed time is 0.149284 seconds. 

%  x = randi(100, 1, 1000000);
%  y = randi(5, 1, 1000000);
%  A: Elapsed time is 0.886396 seconds.
%  B: Elapsed time is 0.139918 seconds.

% Comparison
% A is faster than B if there are few different x-values (about 10-20). 
% The number of different x-values has high impact on speed of A.
% A is faster than B if x & y-vector are extremely long (> 100000).
% The vector length has low impact on speed of B.

[KSSV]

Read about unique

[Star Strider]

I was going to suggest a solution using accumarray, however when I tested it with your ‘Approach A’, my accumarray code was about 0.03 seconds slower than ‘Approach A’ on my laptop, so I did not post it. You may have the optimal solution.

[Zwithouta]

@Star Strider

Could you please share your code?

Using accumarry for the above example works perfectly and is by far the fastest solution (see code below). The problem with using accumarray is that this code only works if the x-vector contains only positive integers. Do you have any idea how accumaray could be used with all kind of real numbers in the x-vector?

x = randi(10, 1, 1000000);
y = randi(5, 1, 1000000);

tic
yVals = accumarray(x', y, [], @(x) {x});
toc
Elapsed time is 0.081769 seconds.

@KSSV

I've read the documentation, but unfortunately I don't understand what you're getting at.

[Star Strider]

@Zwithouta — Yours is essentially the same as mine, except that I included a unique call:

tic
[Ux,~,ix] = unique(x);
solution = accumarray(ix, y, [], @(x){x});
toc

The timings for accumarray and ‘Approach A’ on my laptop are typically:

Elapsed time is 0.432192 seconds.
Elapsed time is 0.185815 seconds.

respectively. (The timings earlier today were different for some reason, although the approximate 2/1 ratio held for both runs.)

[Zwithouta]

@Star Strider

Thanks for sharing!

I think the combination of unique & accumarray is the most elegant approach I will use from now on. For extremely long vectors with many unique-values I tend to use approach B.

x = randi(100000, 1, 1000000);
y = randi(100000, 1, 1000000);

Elapsed time is 0.295816 seconds. % Approach B
Elapsed time is 0.757274 seconds. % accumarray + unique

[Star Strider]

My pleasure!

I was surprised that accumarray was slower than the loop, even though it makes for neater code.

I didn’t test ‘Approach B’, since ‘Approach A’ (chosen randomly) was significantly faster than my accumarray call.

[Zwithouta]

Enjoy it with caution! Approach A really suffers terribly from increasing the number of unique-values in the x-vector, since it increases the number of needed for-loop iterations. Approach B in contrast shows a really stable performance.

y = randi(5, 1, 1000000);

x = randi(10, 1, 1000000);
Elapsed time is 0.108344 seconds. % A
Elapsed time is 0.195844 seconds. % B

x = randi(100, 1, 1000000);
Elapsed time is 0.877760 seconds. % A
Elapsed time is 0.182726 seconds. % B

x = randi(1000, 1, 1000000);
Elapsed time is 11.379839 seconds.% A
Elapsed time is 0.196772 seconds. % B

Answer 1

[Paul Shoemaker]

If you're trying to avoid a FOR loop you can use arrayfun, although I'm not sure it improves speed.

It would look something like this:

x = [1 1 2 2 1 1];
y = [1 2 3 4 5 6];
solution = arrayfun(@(z) y(z==x),unique(x),'uniformoutput',false);

Paul Shoemaker

http://www.matlabinvesting.com

[Zwithouta]

Thanks for sharing your thoughts on that topic!

Your approach is the fastest for long x-vectors so far, but suffers similar to approach A from high numbers of unique x-values.