How to improve sparse array indexed assignment in MATLAB?

2 Ansichten (letzte 30 Tage)
Nadatimuj
Nadatimuj am 2 Mär. 2022
Bearbeitet: Nadatimuj am 7 Mär. 2022
Hi, how can I improve indexed assignment to a sparse matrix? Please refer to line 29 and 31 of the attached code that is simply trying to read the attached txt file and put +1 for positive values and -1 for negative values and generate a matrix. How can I speed it up? Thanks.
An example function call will be: A= cnf_to_A('quinn.txt');
  2 Kommentare
David Hill
David Hill am 2 Mär. 2022
In the example you create a 16x18 sparse array. Do not understand where to index your -1/+1 values into.
Nadatimuj
Nadatimuj am 3 Mär. 2022
Bearbeitet: Nadatimuj am 3 Mär. 2022
sorry for not being clearer. This is a SAT solver CNF format.
The following lines are just comments:
c quinn.cnf
c
p cnf 16 18
This last line indicates the size of the matrix 18 by 16
Then the follwoing lines correspond to the matrix rows:
1 2 0
-2 -4 0
3 4 0
-4 -5 0
5 -6 0
6 -7 0
6 7 0
7 -16 0
8 -9 0
-8 -14 0
9 10 0
9 -10 0
-10 -11 0
10 12 0
11 12 0
13 14 0
14 -15 0
15 16 0
where, the 0 at the end of each line indicates end of line. Take the 2nd line as an example, -2 -4 0 which indicates that the 2nd and 4th element of the 2nd row should be -1.
another example is the 17th line, where 14 -15 0 means the 14th and 15th element of 17th row should be +1 and -1.
Thanks for your help.

Melden Sie sich an, um zu kommentieren.

Antworten (2)

David Hill
David Hill am 3 Mär. 2022
s=readmatrix('quinn.txt','Range','C3:D3');
r=readmatrix('quinn.txt','NumHeaderLines',3);
X=sparse(s(2),s(1));
ra=abs(r(:,1:2));
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*[1 1];
X(linIndex(:))=rv(:);
  5 Kommentare
David Hill
David Hill am 3 Mär. 2022
Try this:
File='irregular.txt';
fid=fopen(File);
count=1;
while ~feof(fid)
tline = fgetl(fid);
tline = strtrim(tline);
if (tline(1)=='p' || tline(1)=='P')
c=count;
elseif (tline(1)=='c' || tline(1)=='C')
cc=count;
end
count=count+1;
end
fclose(fid);
s=readmatrix(File,'Range',sprintf('C%d:D%d',c,c));
r=readmatrix(File,'NumHeaderLines',max(c,cc));
X=sparse(s(2),s(1));
ra=abs(r);
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*ones(1,size(ra,2));
linIndex=linIndex(linIndex>0);
rv=rv(~isnan(r)&r~=0);
X(linIndex)=rv;
Nadatimuj
Nadatimuj am 5 Mär. 2022
Bearbeitet: Nadatimuj am 7 Mär. 2022
This is an edited response: It still takes long time (~140 s) for the last line for ULTRA large instances (please see attched competion.zip file for example which is a 2020 SAT competition instance). My original version took 127s. I think as @Matt J suggested, we must create the sparse matrix from the scratch with indices, otherwise it is not making it faster.
One minor comment, someone should initialize cc= 0 because come CNF files do not have comment lines.
function [A] = cnf_to_A(cnffile, varargin)
fid=fopen(cnffile);
count=1;
cc=0;
while ~feof(fid)
tline = fgetl(fid);
tline = strtrim(tline);
if (tline(1)=='p' || tline(1)=='P')
c=count;
elseif (tline(1)=='c' || tline(1)=='C')
cc=count;
end
count=count+1;
end
fclose(fid);
s=readmatrix(cnffile,'FileType','text','Range',sprintf('C%d:D%d',c,c));
r=readmatrix(cnffile,'FileType','text','NumHeaderLines',max(c,cc));
A=sparse(s(2),s(1));
ra=abs(r);
rv=ones(size(ra));
rv(r<0)=-1;
linIndex=s(2)*(ra-1)+(1:s(2))'.*ones(1,size(ra,2));
linIndex=linIndex(linIndex>0);
rv=rv(~isnan(r)&r~=0);
A(linIndex)=rv;
end
Thanks.

Melden Sie sich an, um zu kommentieren.


Matt J
Matt J am 3 Mär. 2022
Bearbeitet: Matt J am 3 Mär. 2022
Assigning into an existing sparse matrix is fundamentally a slow thing. If you are creating a matrix from scratch, use the sparse() command, not assignment:
Jdata=[
1 2 0
-2 -4 0
3 4 0
-4 -5 0
5 -6 0
6 -7 0
6 7 0
7 -16 0
8 -9 0
-8 -14 0
9 10 0
9 -10 0
-10 -11 0
10 12 0
11 12 0
13 14 0
14 -15 0
15 16 0];
N=size(Jdata,1);
rows=(1:N)';
I=[rows,rows];
J=abs(Jdata(:,1:2));
S=sign(Jdata(:,1:2));
A=sparse(I,J,S);
spy(A)
  3 Kommentare
Matt J
Matt J am 3 Mär. 2022
Bearbeitet: Matt J am 3 Mär. 2022
Thank you very much. This code is giving me error:
I fixed it.
Also, as I am discussing with @David Hill above, the data is not always regular like this, it can be irregular too:
That's not really an important aspect. You would need to build I,J,S differently in the irregular case, but the point about avoiding assignment is the same.
Nadatimuj
Nadatimuj am 5 Mär. 2022
@Matt J Yes now I understand that the real point is to have the row and column indices and create the sparse matrix later. Thank you very much.

Melden Sie sich an, um zu kommentieren.

Kategorien

Mehr zu Large Files and Big Data finden Sie in Help Center und File Exchange

Produkte


Version

R2021b

Community Treasure Hunt

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

Start Hunting!

Translated by