Geek Answers Handbook

How to effectively replace a function with a search?

I am trying to increase the speed of code that works with large datasets. I need to execute the function out = sinc(x) , where x is the double matrix of 2048 by 37499. This is very expensive and is the bottleneck of my program (even when calculating on a GPU).

I am looking for any solution that improves the speed of this operation. I expect this to be achieved by precomputing the vector LookUp = sinc(y) , where y is the vector y = min(min(x)):dy:max(max(x)) , i.e. A vector covering the entire range of expected elements x .

How can I efficiently generate an approximation of sinc(x) from this LookUp vector?

I need to avoid creating a three-dimensional array, as this will consume more memory than I have.

Here is a test to solve interp1:

 a = -15; b = 15; rands = (ba).*rand(1024,37499) + a; sincx = -15:0.000005:15; sincy = sinc(sincx); tic res1 = interp1(sincx,sincy,rands); toc tic res2 = sinc(rands); toc' sincx = gpuArray(sincx); sincy = gpuArray(sincy); r = gpuArray(rands); tic r = interp1(sincx,sincy,r); toc r = gpuArray(rands); tic r = sinc(r); toc

Elapsed time - 0.426091 seconds.
The elapsed time is 0.472551 seconds.
The elapsed time is 0.004311 seconds.
The elapsed time is 0.130904 seconds.

Corresponds to CPU interp1, CPU sinc, GPU interp1, GPU sinc respectively

+6
source share
4 answers

Not sure if I fully understood your problem. But as soon as you have LookUp = sinc(y) , you can use the Matlab interp1 function

 out = interp1(y,LookUp,x)

where x can be a matrix of any size

+3
source

I came to the conclusion that your code cannot be significantly improved. The fastest lookup table is based on simple indexing. For a performance test, just run a test based on random data:

 %test data: x=rand(2048,37499); %relevant code: out = sinc(x);

Now the search is based on whole indices:

 a=min(x(:)); b=max(x(:)); n=1000; x2=round((xa)/(ba)*(n-1)+1); lookup=sinc(1:n); out2=lookup(x2);

Regardless of the size of the lookup table or input data, the last lines in both blocks of code take about the same time. If sinc is evaluated about as fast as the indexing operation, I can only assume that it is already implemented using the lookup table.

+3
source 
 m = min(x(:)); y = m:dy:max(x(:)); LookUp = sinc(y);

now sinc(n) should equal

 LookUp((nm)/dy + 1)

Assuming n is an integer multiple of dy , and is within the range of m and max(x(:)) . To jump to the LookUp index (i.e., the Integer between 1 and numel(y) , first move n , but at least m , then scale it to dy and finally add 1 , because the MATLAB indices are from 1 instead of 0 .

I don’t know that this will make you effective, but give it a try.

You can also put this in an anonymous function to make reading easier:

 sinc_lookup = @(n)(LookUp((nm)/dy + 1))

and now you can just call

 sinc_lookup(n)
+2
source

I found a faster way (if you have an NVIDIA GPU on your PC), however this will return NaN for x=0 , but if for some reason you can deal with NaN or you know it will never be zero:

if you define r = gpuArray(rands); and actually evaluate the sinc yourself in the GPU as:

 tic r=rdivide(sin(pi*r),pi*r); toc

As a rule, this gives me about 3.2 times the speed than the interp1 version in the GPU, and it is more accurate (checked using your code above, repeating 100 times with various random data, having both methods similar to std).

This works because sin and rdivide element separation rdivide also implemented using the GPU (although for some reason there is no sinc ). See: http://uk.mathworks.com/help/distcomp/run-built-in-functions-on-a-gpu.html

+2
source

More articles: