How to improve sparse array indexed assignment in MATLAB?

2 次查看（过去 30 天）
Nadatimuj
Nadatimuj 2022-3-2
编辑： Nadatimuj 2022-3-7
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 个评论
David Hill
David Hill 2022-3-2
In the example you create a 16x18 sparse array. Do not understand where to index your -1/+1 values into.
Nadatimuj
Nadatimuj 2022-3-3
编辑：Nadatimuj 2022-3-3
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.

请先登录，再进行评论。

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

回答（2 个）

David Hill
David Hill 2022-3-3
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 个评论
显示 3更早的评论
David Hill
David Hill 2022-3-3
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 2022-3-5
编辑：Nadatimuj 2022-3-7
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.

请先登录，再进行评论。

Matt J
Matt J 2022-3-3
编辑：Matt J 2022-3-3
Ran in:
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 个评论
显示 1更早的评论
Matt J
Matt J 2022-3-3
编辑：Matt J 2022-3-3
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 2022-3-5
@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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Sparse Matrices 的更多信息

标签

产品


版本

R2021b

Community Treasure Hunt

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

Start Hunting!

Translated by