Speeding up to find minimum value using min() function

Hi,

I have to calculate the current distribution of two nonlinear resistors. To do that I’m searching for the closest index and value of an array.

For example.

[a,b]=min(abs(c-s))

c is an n x 1 array. c increases monotonically

c represents the characteristics of the resistors.

s is a 1 x m array and sinusoidal shaped

s represents the impressed current.

With index b I calculate the voltage drop and the current of each resistor.

Any suggestions to speed up the code?

[Torsten]

c-s will be an nxm matrix and b will be an 1xm vector.

Is it this what you want ?

[Michael Walter]

exactly.

I calculate for every given Datapoint in s the index for current distribution.

[Jan]

What are typical sizes of the inputs? Do you have a C compiler installed?

[Michael Walter]

c is round about 5000x1 and s is about 1x800.

The size is not the problem, but I have to repeat this function over and over again, because the current distribution will change the temperature and therefore the current characteristics. For a given time the temperature is assumed constant. After that period the temperature is calculated based on power losses and with that new temperature the new characteristics c is calculated. Then the function [a,b]=min(abs(c_new-s_new)) is called again.

The min function requires 85% of execution time

I have no c-compiler installed but I can install a compiler.

[Jan]

The size matters, because the creation of the intermediate matrix c-s is time consuming. Then the RAM access is the bottleneck.

Answer 1

[Bruno Luong]

Alternative way

% Fake data
c=cumsum(rand(1,10000));
s=c(end)*rand(1,10000);

cpad = [-Inf c Inf];
b = discretize(s,cpad);
b = b -1 + (cpad(b)+cpad(b+1)<2*s);
a = c(b);

[Michael Walter]

Thank you. Seems to work. Isn't as fast as Jan's solution but more stable.

Any suggestions for non-monotonically c arrays? See the 'Data.mat' below Jan's answer

[Bruno Luong]

Jusr sort c first

% Fake data, not sorted
c=rand(1,10000);
s=rand(1,10000);

[cs,is] = sort(c);
cpad = [-Inf cs Inf];
b = discretize(s,cpad);
b = b - 1 + (cpad(b)+cpad(b+1)<2*s);
b = is(b);
a = c(b);

[Bruno Luong]

I like Jan's method. Combine with sort this is the code

% Fake data, not sorted
c=rand(1,10000);
s=rand(1,10000);

[cs,is] = sort(c);
cm = (cs(1:end-1) + cs(2:end))/2;
cpad = [-Inf cm Inf];
b = discretize(s,cpad);
b = is(b);
a = c(b);

[Michael Walter]

Thank you.

I'm a newbie at Matlab forum. Is it possible to accept Jan's solution too?

[Bruno Luong]

No you can't accept multiple answers.

Answer 2

[Matt J]

c=c(:)';

b=interp1(c,1:numel(c),s,'nearest');

a=abs(c(b)-s)

Answer 3

[Jan]

c        = c(:);   % Make it a column vector to be sure
nc       = numel(c);
bin      = [c(1); (c(1:nc-1) + c(2:nc)) * 0.5; c(nc)];
[~, idx] = histc(s, bin);
value    = abs(c(idx) - s(:));

bin contains the start point, midpoints and final point of the intervals of c.

histc uses a binary search to find the index of the value in c for each element of s. This avoids to create the large matrix c - s. Unfortunately MathWorks decided to replace the working histc by histcounts, which has some performance problems.

See also: interp1('nearest')

c = linspace(0, 1, 1e4);
s = rand(1, 1e5);

tic;
[a, b] = min(abs(c(:) - s(:).'));
toc

Elapsed time is 3.400639 seconds.

tic;
c       = c(:);
nc      = numel(c);
bin     = [c(1); (c(1:nc-1) + c(2:nc)) * 0.5; c(nc)];
[~, b2] = histc(s, bin);
% Alternative, seems to be faster:
% [~, ~, b2] = histcounts(s, bin);
a2      = abs(c(b2) - s(:));
toc

Elapsed time is 0.013202 seconds.

isequal(b, b2)

ans = logical
   1

max(abs(a(:) - a2(:)))

ans = 0

[Michael Walter]

Your Code is insanely fast. Thank you.

But the index b2 is partially 0.

Any idea what’s the problem?

I have also to annotate that I calculate the current distribution of resistor and for example a diode.

The I-V characteristics are measured. Below the forward voltage of the diode there is some measurement noise which leads to non-monotonic c-array. Any idea that your code works with non-monotonically characteristics. I thought about sort() but that’s quiet slow.

Edit: I just saw the histcounts variant. I will try it.

Edit2: When the values of s (see picture) are zero b2 is also zero.

Edit3: b2(b2==0)=1 solves the indexing problem but thats inelegant.

[Jan]

Can you provide some input data, which reproduce the problem?

HISTC replies 0, if the data are not inside the bins. So you can expand the first an last bins to the maximal values of s:

% bin = [c(1);   (c(1:nc-1) + c(2:nc)) * 0.5; c(nc)];  % Original
bin   = [min(s); (c(1:nc-1) + c(2:nc)) * 0.5; max(s)];

If you know the values in advance, you can save the time for searching min and max.

[Michael Walter]

Here are some input data. c1/s1 works with b2(b2==0)=1; c2/s2 has some measurment noise so that c2 isn't monotonically. c3/s3 is a special one, everything is zero. c3/s3 is for the case that i have only one resistor. I thought it's easier to calculate this state intead of using if statement.

Edit: I solved c2/s2 by manipulating the input data

[Michael Walter]

Also a very good solution. Thank you