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 件のコメント
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 日
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 件のコメント
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 ExchangeLarge Files and Big Data についてさらに検索

製品


リリース

R2021b

Community Treasure Hunt

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

Start Hunting!

Translated by