Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: please help optimize this ('find' is too slow)
Date: Mon, 8 Dec 2008 04:06:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 25
Message-ID: <ghi6f9$3um$1@fred.mathworks.com>
References: <gh46f4$pg2$1@fred.mathworks.com> <gh7ror$eno$1@fred.mathworks.com> <gh7vs8$fgq$1@fred.mathworks.com> <gh9faq$fb4$1@fred.mathworks.com> <gh9qmi$l5c$1@fred.mathworks.com> <gh9ske$6he$1@fred.mathworks.com> <gha1vj$850$1@fred.mathworks.com> <ghefbe$ell$1@fred.mathworks.com> <gher83$sfd$1@fred.mathworks.com> <ghfk6p$mu6$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1228709161 4054 172.30.248.37 (8 Dec 2008 04:06:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 8 Dec 2008 04:06:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:505525


"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message 
> .......
>   As to coming up with a fundamentally improved method of indexing on the 'ny' line, I'm afraid that might be very difficult to do.  This problem has come up in earlier threads and I was unable then to find a way of speeding up more than the first coordinate set computation.  And unfortunately I'm no smarter now than I was then.
> .......

  Perhaps I surrendered too soon in that previous article, Jayveer.  A method has occurred to me that would first require doing the kind of sorting I previously mentioned three times rather than one time, once for each coordinate direction.  That is, there would be three sorts done just one time each for a given run which look like this:

[t,rx] = sort([Lx,Ux,X]);
[t,ry] = sort([Ly,Uy,Y]);
[t,rz] = sort([Lz,Uz,Z]);

(where X = P(1,:), Y = P(2,:), and Z = P(3,:) in your terminology.)

  However sorts are time consuming operations and the question is whether doing these one time each would already make the total time excessive even before doing any other processing.  How important is that one sort I previously recommended in the whole timing picture?  You didn't mention how long it was taking as compared with other operations.

  Assuming the above timing is not excessive, then a for-loop can be devised which operates on the cells, fifty-three cells at a time, rather than one at a time.  Each pass through the loop would take more time than one pass in your loop but there will be many fewer loops, 1/53-rd as many in fact.

  Just to give a tantalizing outline of the method, for each coordinate an array of elements as long as X, Y, or Z, is computed in which each element's 53 bits are 1 or 0 according as the corresponding point's coordinate falls within the 53 cells' various lower and upper limits.  These three arrays are then combined using 'bitand' calls to obtain a single bit in each of the 53 bit positions that is 1 or 0 according as the corresponding whole cubic cell contains the point or not.  Then the 'log2' function can be used to convert to the appropriate c value to be placed in the PiC array as you do in your code.

  As you can probably guess, the number 53 derives from the fact that this is the maximum number of bits that can be contained in any one double precision integer in Matlab's double format.

  So, does any of this interest you, or do the three fearsome sorts already rule this method out?

Roger Stafford