Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
FAST algorithm to jenga matrix?

Subject: FAST algorithm to jenga matrix?

From: Hoi Wong

Date: 29 Mar, 2009 02:17:01

Message: 1 of 11

I have a GIANT sparse matrix with scattered non-trivial elements ranging from 1:N, then I need to remove a M non-trivial elements and maintain the cardinality from 1:N-M. Is there a fast way to do it? Here's an example to illustrate what I'm trying to do (N=8, M=2):

>> A=[ 0 0 8 0 0 ; 1 4 0 0 2; 0 5 3 0 0; 7 0 0 6 0]
A =
     0 0 8 0 0
     1 4 0 0 2
     0 5 3 0 0
     7 0 0 6 0

>> sort(nonzeros(A))
ans =
     1
     2
     3
     4
     5
     6
     7
     8

------------------------------
Numbers to delete: 2, 6


desiredMatrix =
     0 0 6(-2) 0 0
     1 3(-1) 0 0 X
     0 4(-1) 2(-1) 0 0
     5(-2) 0 0 X 0

desiredMatrix =
     0 0 6 0 0
     1 3 0 0 0
     0 4 2 0 0
     5 0 0 0 0

>> sort(nonzeros(desiredMatrix))
ans =
     1
     2
     3
     4
     5
     6

Because the matrix is huge (but sparse), I don't want to use for loops. I kind of have a feeling that there must be a slick way to do it with a different way of thinking, and there must be some MATLAB master-minds here who can come up with a slick one-or-two-liners. :)

Thanks in advance

Subject: FAST algorithm to jenga matrix?

From: Roger Stafford

Date: 29 Mar, 2009 07:11:03

Message: 2 of 11

"Hoi Wong" <wonghoi.ee@gmailNOSPAM.com> wrote in message <gqmlmt$6tp$1@fred.mathworks.com>...
> I have a GIANT sparse matrix with scattered non-trivial elements ranging from 1:N, then I need to remove a M non-trivial elements and maintain the cardinality from 1:N-M. Is there a fast way to do it? Here's an example to illustrate what I'm trying to do (N=8, M=2):
>
> >> A=[ 0 0 8 0 0 ; 1 4 0 0 2; 0 5 3 0 0; 7 0 0 6 0]
> A =
> 0 0 8 0 0
> 1 4 0 0 2
> 0 5 3 0 0
> 7 0 0 6 0
>
> >> sort(nonzeros(A))
> ans =
> 1
> 2
> 3
> 4
> 5
> 6
> 7
> 8
>
> ------------------------------
> Numbers to delete: 2, 6
>
>
> desiredMatrix =
> 0 0 6(-2) 0 0
> 1 3(-1) 0 0 X
> 0 4(-1) 2(-1) 0 0
> 5(-2) 0 0 X 0
>
> desiredMatrix =
> 0 0 6 0 0
> 1 3 0 0 0
> 0 4 2 0 0
> 5 0 0 0 0
>
> >> sort(nonzeros(desiredMatrix))
> ans =
> 1
> 2
> 3
> 4
> 5
> 6
>
> Because the matrix is huge (but sparse), I don't want to use for loops. I kind of have a feeling that there must be a slick way to do it with a different way of thinking, and there must be some MATLAB master-minds here who can come up with a slick one-or-two-liners. :)
>
> Thanks in advance

  I'm afraid this isn't a one- or two-liner, but an eight-liner, Hoi. I couldn't think of anything shorter. Let d be a vector of the numbers to "delete".

 [r,c,v] = find(A);
 [v,p] = sort(v);
 v = 1;
 v(d) = 0;
 v = cumsum(v);
 v(d) = 0;
 v(p) = v;
 B = sparse(r,c,v,size(A,1),size(A,2));

B is the desired matrix.

  This depends on your statement that the non-zero elements of A are 1:N and those of B are are to be 1:N-M where M = size(d,2).

Roger Stafford

Subject: FAST algorithm to jenga matrix?

From: Bruno Luong

Date: 29 Mar, 2009 09:33:02

Message: 3 of 11

Here is a five-liner solution, but not much fundamentally different to Roger's solution:

A=[ 0 0 8 0 0 ;
    1 4 0 0 2;
    0 5 3 0 0;
    7 0 0 6 0];

d = [2 6]'; % To be removed

[I J Val]=find(A);
f=ismember(unique(Val),d);
NewVal=cumsum(1-f);
NewVal(f)=0;
B=sparse(I,J,NewVal(Val),size(A,1),size(A,2));

% Alternatively, if no matrix duplicating is required
% then the last line changes to this

[I J Val]=find(A);
f=ismember(unique(Val),d);
NewVal=cumsum(1-f);
NewVal(f)=0;
A(sub2ind(size(A),I,J))=NewVal(Val);

% Bruno

Subject: FAST algorithm to jenga matrix?

From: Bruno Luong

Date: 29 Mar, 2009 10:32:45

Message: 4 of 11

Here is a four-liner solution. I could merge the 2nd and 3rd lines but it does not bring any advantage beside having less lines:

[I J Val]=find(A);
u = unique(Val); % 1:n
[f NewVal]=ismember(u,setdiff(u,d));
B=sparse(I,J,NewVal(Val),size(A,1),size(A,2));

% Bruno

Subject: FAST algorithm to jenga matrix?

From: Bruno Luong

Date: 29 Mar, 2009 10:48:01

Message: 5 of 11

For fun, two-liner solution:

[f NewVal]=ismember(1:max(nonzeros(A)),setdiff(1:max(nonzeros(A)),d));
A(A~=0)=NewVal(nonzeros(A));

Now how to get to one-liner solution (challenge proposed by Roger)?

Bruno

Subject: FAST algorithm to jenga matrix?

From: Bruno Luong

Date: 29 Mar, 2009 12:13:02

Message: 6 of 11

>
> Now how to get to one-liner solution (challenge proposed by Roger)?
>

A=[ 0 0 8 0 0 ;
    1 4 0 0 2;
    0 5 3 0 0;
    7 0 0 6 0];
A=sparse(A)

d = [2 6]'; % To be removed

% One-liner solution !!!
A(A~=0) = subsref(subsasgn([],substruct('()',...
    {setdiff((1:max(nonzeros(A))),d)}), ...
     1:length(setdiff((1:max(nonzeros(A))),d))),...
     substruct('()',{nonzeros(A)}))

% Bruno

Subject: FAST algorithm to jenga matrix?

From: Bruno Luong

Date: 29 Mar, 2009 13:29:01

Message: 7 of 11

Sorry there is a bug in the previous code, it should be this:

% One-liner solution !!!
A(A~=0) = subsref(subsasgn(zeros(1,max(nonzeros(A))),substruct('()',...
    {setdiff((1:max(nonzeros(A))),d)}), ...
     1:length(setdiff((1:max(nonzeros(A))),d))),...
     substruct('()',{nonzeros(A)}))

% Bruno

Subject: FAST algorithm to jenga matrix?

From: Bruno Luong

Date: 29 Mar, 2009 15:35:01

Message: 8 of 11

% Another one-liner solution !!!
A(A~=0) = subsref(cumsum(~ismember(1:max(nonzeros(A)),d)).* ...
   ~ismember(1:max(nonzeros(A)),d),...
   substruct('()',{nonzeros(A)}))

% Bruno

Subject: FAST algorithm to jenga matrix?

From: Roger Stafford

Date: 29 Mar, 2009 16:22:01

Message: 9 of 11

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqn6u7$1s2$1@fred.mathworks.com>...
> ......
> [r,c,v] = find(A);
> [v,p] = sort(v);
> v = 1;
> v(d) = 0;
> v = cumsum(v);
> v(d) = 0;
> v(p) = v;
> B = sparse(r,c,v,size(A,1),size(A,2));
> ......

  Sorry about the careless mistake, Hoi. The third line should read:

 v = ones(size(v));

Roger Stafford

Subject: FAST algorithm to jenga matrix?

From: Hoi Wong

Date: 29 Mar, 2009 22:35:03

Message: 10 of 11

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gqo4f5$qf8$1@fred.mathworks.com>...
> % Another one-liner solution !!!
> A(A~=0) = subsref(cumsum(~ismember(1:max(nonzeros(A)),d)).* ...
> ~ismember(1:max(nonzeros(A)),d),...
> substruct('()',{nonzeros(A)}))
>
> % Bruno

Thanks for your quick reply. I see a lot of ismember, unique, setdiff here which are famous for being slow. I'll set up a time test for all your solutions in a couple of days and see which one is the fastest :)

Subject: FAST algorithm to jenga matrix?

From: Hoi Wong

Date: 30 Mar, 2009 02:33:01

Message: 11 of 11

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqo779$d3g$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqn6u7$1s2$1@fred.mathworks.com>...
> > ......
> > [r,c,v] = find(A);
> > [v,p] = sort(v);
> > v = 1;
> > v(d) = 0;
> > v = cumsum(v);
> > v(d) = 0;
> > v(p) = v;
> > B = sparse(r,c,v,size(A,1),size(A,2));
> > ......
>
> Sorry about the careless mistake, Hoi. The third line should read:
>
> v = ones(size(v));
>
> Roger Stafford

Thanks Roger! I've never given that much thought to the extended parameters for find(), sort() and a 5-argument use for sparse() though I've been using them for a while (sparse is quite new to me though. I'm developing a sparse_cell class/dataType and jengaMatrix is a piece of the puzzle)

My first algorithm was embarassing.......it's complicated, uses cellfun, sum, and runs 100000 times slower than any of yours, and it does not work for non-unique deletion list. Turns out that your 8-line solution is the fastest of all as I expected (because they are all built-in functions). Simple test is the matrix mentioned in my first post, and the second data set was captured from my project.

Here's the link to all of your algorithms and mine as well. jengaMatrixSpeedTest tests them all and generate the report below:

Does all algorithm give the same result for the simple test? true
---------------------------------------------------------------
Is the test matrices cardinal? true
Cardinality preserved? true
Is the deletion list unique? false
Roger: 0.00110589
Bruno1: 0.00870681
Bruno2: 0.02111930
Bruno4: 0.00462781
Bruno5: 0.00282878
Does all algorithm give the same result for the stress test (with non-unique deletion items)? true
Cardinality preserved? true
---------------------------------------------------------------
Hoi: 110.50091451
Roger: 0.00098781
Bruno1: 0.00648331
Bruno2: 0.00672234
Bruno4: 0.00160589
Bruno5: 0.00117171
Does all algorithm give the same result for the stress test (with unique deletion items)? true
Cardinality preserved? true

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us