First non-zeros of a sparse array

1 次查看（过去 30 天）
Martin
Martin 2013-7-26
Hi, I'm searching for the fastest way to get the index of the first non zero element of a sparse array. Only nonzeros have been "created" when I built this sparse matrix ==> searching the first nonzero is the same as searching the element with the smallest index.
The array are not very big (~5,000 maximum) but I have to process it millions of times. (find the first nonzero of each array)
Their length are equal, of the form n*(2^k) (n and k are constant), and I know that the first non-zero element is of the form m*(2^k) + 1. I thus tried to do it with a while loop, going through the array with (2^k) step, but it still takes time.
There is probably a way to find it faster.
Thanks!

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

采纳的回答

the cyclist
the cyclist 2013-7-26
编辑：the cyclist 2013-7-26
This code takes about 2.5 seconds to run on my machine.
% Create a sparse array [10% filled]
x = sparse(5000,1);
x(randsample(5000,500)) = 1;
% Find the first element, a million times
idx = zeros(1000000,1);
tic
for n=1:1000000
idx(n) = find(x,1);
end
toc
  3 个评论
显示 1更早的评论
the cyclist
the cyclist 2013-7-26
You don't need to make the temp array:
firstNonZero(iAction, iState) = find(P{iAction}(iState,:),1);
Does that help?
Martin
Martin 2013-7-29
No, unfortunately it does not help. Thanks anyway.

请先登录，再进行评论。

更多回答（2 个）

per isakson
per isakson 2013-7-26
编辑：per isakson 2013-7-26
Did you try
ix = find( A ~= 0, 1, 'first' );
and something like
ix = find( A("m*(2^k) + 1") ~= 0, 1, 'first' );
"non zero element" does that imply an integer array?
.
Doc says:
"[row,col] = find(X, ...) returns the row and column indices of the nonzero entries in the matrix X. This syntax is especially useful when working with sparse matrices."
James Tursa
James Tursa 2013-7-26
编辑：James Tursa 2013-7-26
You can use a mex routine for this, but you will need a C compiler to compile it. E.g., create a file called firstNonZeroMex.c with the contents below and then compile it with the mex function. Unfortunately, if you are on a 64-bit system then you will have to get and install a C compiler yourself since 64-bit MATLAB does not come with one installed. Not sure how this compares timing wise, but I would expect it to be fast compared to m-file methods that have to copy a lot of data to get at the rows. The mex function below does not copy any of the rows to get the job done.
/***********************************************************************
* firstNonZeroMex returns first non-zero from each row of each sparse
* matrix in a cell array of sparse matrices.
*
* Syntax: F = firstNonZeroMex(C)
*
* Where: C = Cell Array of sparse matrices, all the same row size
* F = First non-zero values of the C{i}
*
* If there is no non-zero in a particular row, returns 0 for that spot.
* The result for C{i} row j will be in F(i,j).
*
* Programmer: James Tursa
* Date: 25-July-2013
***********************************************************************/
#include "mex.h"
#ifndef MWSIZE_MAX
# define mwSize int
# define mwIndex int
#endif
void firstNonZero(double *pr, mxArray *cell, mwSize e, mwSize m);
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
mxArray *cell;
mwSize i, m, n, e;
double *pr;
if( nrhs != 1 || !mxIsCell(prhs[0]) ) {
mexErrMsgTxt("Need one cell array input");
}
if( nlhs > 1 ) {
mexErrMsgTxt("Too many outputs");
}
e = mxGetNumberOfElements(prhs[0]);
if( e == 0 ) {
mexErrMsgTxt("Input is empty");
}
cell = mxGetCell(prhs[0],0);
if( cell == NULL ) {
mexErrMsgTxt("One or more of the cells is empty");
}
if( !mxIsSparse(cell) || !mxIsDouble(cell) ) {
mexErrMsgTxt("One or more of the cells is not double sparse");
}
for( i=0; i<e; i++ ) {
cell = mxGetCell(prhs[0],i);
if( cell == NULL ) {
mexErrMsgTxt("One or more of the cells is empty");
}
if( !mxIsSparse(cell) || !mxIsDouble(cell) ) {
mexErrMsgTxt("One or more of the cells is not double sparse");
}
if( i == 0 ) {
m = mxGetM(cell);
plhs[0] = mxCreateDoubleMatrix(e,m,mxREAL);
pr = mxGetPr(plhs[0]);
} else {
if( mxGetM(cell) != m ) {
mexErrMsgTxt("One or more cells is mismatched in size from other cells");
}
}
firstNonZero(pr, cell, e, m);
pr++;
}
}
void firstNonZero(double *pr, mxArray *cell, mwSize e, mwSize m)
{
mwSize k, n, nrow;
mwIndex *ir, *jc;
mwIndex j, x, y;
double *pc, *pj;
n = mxGetN(cell);
pc = mxGetData(cell);
ir = mxGetIr(cell);
jc = mxGetJc(cell);
k = 0;
for( y=0; y<n; y++ ) {
nrow = jc[y+1] - jc[y];
for( x=0; x<nrow; x++ ) {
pj = pr + (*ir) * e;
if( *pj == 0.0 ) {
*pj = *pc;
k++;
if( k == m ) return;
}
ir++;
pc++;
}
}
}
  1 个评论
Martin
Martin 2013-7-29
Thanks James. I'll try first to compute what I want at the moment I fill these matrices. If it is still slow, I'll try your solution. Thanks for your time.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 C Shared Library Integration 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by