0
$\begingroup$

If I have two arrays containing max and min points which make up an envelope. It's quick to test if any point in a given data array goes outside of that envelope using:

 for (int i = 0; i < envMax.size(); i++)
    {
        if ((data[i] < envMin[i]) || (data[i] > envMax[i]))
        {
            return false;
        }
    }
    return true;

However, my data array can be large and I have to load the max and min envelope data from a file for each new data array which needs testing (just the way the system works). So it might be quicker to just use a smaller number of points for the envelope and interpolate. But whats the quickest way of doing this with a reduced number of points. I can do (sudo code):

for each data point
find min and max envelope point before and after data point
calculate equation of line between two points
put in data "x" value
check resultant y value.

Alternatively I can just generate N max and min envelope points (where N is = length(data)) (same thing really)...

But this seems computational exhausting. I can't believe I am the first person to want to do this so is there an accepted (fastest) method / algorithm type?

EDIT:

The problem is essentially this: Check that the blue line is within the green lines. But doing it when the number of points describing the green lines is much less than the number of points describing the blue line.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Searching for a value in a unsorted array is going to be O(n) lower bound. Nothing you can really do to help that other than doing a bit of preprocessing on the data (which will itself take O(n)). $\endgroup$ – ratchet freak May 25 '18 at 10:57
  • 1
    $\begingroup$ Pseudocode doesn't derive from the unix command "sudo". $\endgroup$ – Yuval Filmus May 25 '18 at 11:47
  • $\begingroup$ Ha, I'm dyslexic, I spell it how it sounds. :) $\endgroup$ – Tim Mottram May 25 '18 at 11:55
  • 1
    $\begingroup$ @TimMottram I was once very confused by somebody talking about "persuade-o-code" until I realized he was making the opposite mistake to you -- pronouncing it like it's spelled. :-) $\endgroup$ – David Richerby May 25 '18 at 12:32
1
$\begingroup$

From the short description you give, I infer that you consider that fetching the envelope data from disk is a bottleneck.

Even assuming that the envelope values change with every dataset (so that there is no reuse), you figure seems to show that there are as many data points as there are envelope points. So if you completely avoided the fetching of the envelope, you could at best hope for a threefold improvement, and virtually no improvement in case there is reuse.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.