CODEWITHSUNDEEP
matlabmatrixincrement
user137927
user137927

Reputation: 367

Matlab: Increment of matrix values with indices

I have a vector of indices and want to increase values in matrix in every index. For example:

    ind = [1 2 2 5];
    m = zeros(3);
    m(ind) = m(ind) + 1;

The result is as follow:

    m = [1 0 0
         1 1 0
         0 0 0]

But I need the results to be

    m = [1 0 0
         2 1 0
         0 0 0]

The time complexity is very important to me, and I can't use for. Thanks.

Upvotes: 4

Views: 626

Answers (3)

Divakar
Divakar

Reputation: 221504

For a sorted array of indices, we can have a play of diff -

out = zeros(M,N);  % Output array of size(M,N)
df = diff([0,ind,ind(end)+1]);
put_idx = diff(find(df)); % gets count of dups
out(ind(df(1:end-1)~=0)) = put_idx;

The basic idea being we count the duplicates along the length with diff. Those counts are the values to be assigned into the zeros array. The indices at which those values are to be assigned are simply the unique indices, which could be found out by looking for the start of each group of duplicate indices.

Benchmarking

Script to create sorted indices array (create_data.m) -

function ind = create_data(M,N, num_unq_ind, max_repeats)

unq_ind = unique(randi([1,M*N],1,num_unq_ind));
num_repeats = randi(max_repeats, [1,numel(unq_ind)]);
ind = repelem(unq_ind, num_repeats);

Benchmarking script (bench1.m) to test out various scenarios -

clear all; close all;

M = 5000; % Array size
N = 5000;

% Input params and setup input indices array (edited for various runs)
num_unq_ind = 100000;
max_repeats = 100;
ind = create_data(M,N, num_unq_ind, max_repeats);

num_iter = 100; % No. of iterations to have reliable benchmarking 
disp('Input params :')
disp(['num_unq_ind = ' int2str(num_unq_ind)])
disp(['max_repeats = ' int2str(max_repeats)])

disp('------------------ Using diff ----------------')
tic
for i=1:num_iter
    out = zeros(M,N);
    df = diff([0,ind,ind(end)+1]);
    put_idx = diff(find(df));
    out(ind(df(1:end-1)~=0)) = put_idx;
end
toc

% Luis's soln
disp('------------------ Using accumaray ----------------')
tic
for i=1:num_iter
    m = reshape(accumarray(ind(:), 1, [N^2 1]), N, N);
end
toc

Various scenario runs -

>> bench1
Input params :
num_unq_ind = 10000
max_repeats = 10
------------------ Using diff ----------------
Elapsed time is 0.948544 seconds.
------------------ Using accumaray ----------------
Elapsed time is 1.502658 seconds.
>> bench1
Input params :
num_unq_ind = 100000
max_repeats = 10
------------------ Using diff ----------------
Elapsed time is 1.784576 seconds.
------------------ Using accumaray ----------------
Elapsed time is 1.533280 seconds.
>> bench1
Input params :
num_unq_ind = 10000
max_repeats = 100
------------------ Using diff ----------------
Elapsed time is 1.315998 seconds.
------------------ Using accumaray ----------------
Elapsed time is 1.391323 seconds.
>> bench1
Input params :
num_unq_ind = 100000
max_repeats = 100
------------------ Using diff ----------------
Elapsed time is 6.180565 seconds.
------------------ Using accumaray ----------------
Elapsed time is 3.576154 seconds.

With less sparsey and more repeats, accumarray seems to be doing better.

Upvotes: 4

rahnema1
rahnema1

Reputation: 15837

You can use histcounts

n = 3;
m = reshape(histcounts(ind, [1:n^2 n^2]), n, n);

Upvotes: 3

Luis Mendo
Luis Mendo

Reputation: 112659

Here's a way. I haven't timed it.

ind = [1 2 2 5];
N = 3;
m = full(reshape(sparse(ind, 1, 1, N^2, 1), N, N));

Equivalently, you can use

ind = [1 2 2 5];
N = 3;
m = reshape(accumarray(ind(:), 1, [N^2 1]), N, N);

or its variation (thanks to @beaker)

ind = [1 2 2 5];
N = 3;
m = zeros(N);
m(:) = accumarray(ind(:), 1, [N^2 1]);

This one is probably slower than the others:

ind = [1 2 2 5];
N = 3;
m = zeros(N);
[ii, ~, vv] = find(accumarray(ind(:), 1));
m(ii) = vv;

Upvotes: 6

Related Questions