Detecting "a and b are the same variable" in O(1) via pointers
2 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
I know Matlab uses copy-on-write; that is, if I assign a=b and then never modify a and b, they point to the same chunk of memory. So, in theory, it should be possible to detect that a and b are two copies of the very same matrix with a O(1) pointer comparison, no matter how large they are, in contrast to something like all(a==b). Is there a way to do it in practice?
Alternative formulation, if you are familiar with Java: Matlab's comparisons work like Java's a.equals(b). Is there anything that works like java's a==b?
Use case: I would like to implement low-rank matrices by storing nxr vectors u,v such that M=u*v' is the sparse matrix, and r<<n.
The sum of u1*v1'+ u2*v2' in general has rank 2r, however, if u1==u2 then I can just sum v1 and v2 without any rank increase. In order to optimize for these cases, I need a fast way to check whether u1==u2. Typically this case will arise from u1 and u2 being constructed with the same matrix and never modified, so it is a good tradeoff to check only for "address equality".
0 commentaires
Réponse acceptée
Friedrich
le 3 Fév 2012
Hi,
if you need O(1) try a mex function:
#include "mex.h"
void mexFunction( int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[] )
{
if ((mwSize)mxGetPr(prhs[0]) == (mwSize)mxGetPr(prhs[1]))
mexPrintf("equal \n");
else
mexPrintf("not equal \n");
}
There is not error checking so far. So be carefull. But basically, it takes the pointer to the data and check if its the same adress.
>> a = rand(100);
>> b = a;
>> equal_test(a,b)
equal
Or:
>> a = rand(100);
>> b = a(1);
>> equal_test(a,b)
not equal
Or
>> a = {'text',[1 3 4]};
>> b = a
>> equal_test(a,b)
equal
2 commentaires
Friedrich
le 3 Fév 2012
Yes, they are read only inputs to a mex. So you can get the adress pretty fast and easy. But you cant modify them. This will most likly crash ML.
In order to add a return value to that mex function simply do:
void mexFunction( int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[] )
{
if (nrhs == 2)
plhs[0] = mxCreateLogicalScalar((mwSize)mxGetData(prhs[0]) == (mwSize)mxGetData(prhs[1]));
}
Plus de réponses (1)
David Young
le 3 Fév 2012
I tried experimenting (in ver 2011b). I used
a = rand(5000);
b = a;
tic; isequal(a, b); toc
to test. On my laptop, the time was about 0.05s (fastest over many trials).
This very slow time indicates that isequal does not do a pointer equality test before checking the data. This seems to me very surprising: it's such an obvious optimisation.
I then updated the last element of b and timed again. The comparison time was consistently 50% greater after the copy. It puzzled me that updating b made any consistent difference to the time if pointer equality isn't checked, but I expect it's a cache effect.
This isn't really an answer - more a suggestion that if someone does not give a better reply it might be worth contacting MathWorks support to ask why isequal is so slow in the trivial case of identical pointers. (There's no need for a separate user function for this, since MATLAB doesn't allow pointer manipulation - isequal should just do it efficiently.)
2 commentaires
David Young
le 3 Fév 2012
OK, yes I see that point, though if getting "no" was much faster than the operations you need to perform in that case, an efficient isequal would still help.
But indeed, an "isidentical" would give you just what you need. I wonder if a MEX function can reliably and simply check this?
Voir également
Catégories
En savoir plus sur Write C Functions Callable from MATLAB (MEX Files) dans Help Center et File Exchange
Produits
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!