How to iterate efficiently when some sub intervals results are known

Question

You have a function that always inputs an interval (natural numbers in this case), this function returns a result, but is quite expensive on the processor, simulated by sleep in this example:

function calculate($start, $end) {

    $result = 0;

    for($x=$start;$x<=$end;$x++) {
        $result++;
        usleep(250000);
    }

    return $result;
}

In order to be more efficient there is an array of old results, that contains the interval used an the result of the function for that interval:

$oldResults = [
    ['s'=>1, 'e'=>2, 'r' => 1],
    ['s'=>2, 'e'=>6, 'r' => 4],
    ['s'=>4, 'e'=>7, 'r' => 3]
];

If I call calculate(1,10) the function should be able to calculate new intervals based on old results and accumulate them, In this particular case it should take the old result from 1 to 2 add that to the old result from 2 to 6 and do a new calculate(6,10) and add that too. Take in consideration that the function ignores the old saved interval from 4 to 7 since it was more convenient to use 2-6.

This is a visual representation of the problem:

Of course in this example, calculate() is quite simple and you can just find particular ways to solve this problem around it, but in the real code calculate() is complex and the only thing I know is that calculate(n0,n3)==calculate(n0,n1)+calculate(n1,n2)+calculate(n2,n3).

I cannot find a way to solve the reuse of the old data without using a bunch of IF and foreach, I'm sure there is a more elegant approach to solve this.

You can play with the code here.

Note: I'm using PHP but I can read JS, Pyton, C and similar languages.

Answer 1

if you are certain that calculate(n0,n3)==calculate(n0,n1)+calculate(n1,n2)+calculate(n2,n3), then it seems to me that one approach might simply be to establish a database cache.

you can pre-calculate each discrete interval, and store its result in a record.

$start = 0;
$end = 1000;

for($i=1;$i<=$end;$i++) {
   $result = calculate($start, $i);
   $sql = "INSERT INTO calculated_cache (start, end, result) VALUES ($start,$i,$result)";
   // execute statement via whatever dbms api
   $start++;
}

now whenever new requests come in, a database lookup should be significantly faster. note you may need to tinker with my boundary cases in this rough example.

function fetch_calculated_cache($start, $end) {

    $sql = "
      SELECT SUM(result)
      FROM calculated_cache
      WHERE (start BETWEEN $start AND $end)
        AND (end BETWEEN $start AND $end)
    ";

    $result = // whatever dbms api you chose

    return $result;
}

there are a couple obvious considerations such as:

• cache invalidation. how often will the results of your calculate function change? you'll need to repopulate the database then.
• how many intervals do you want to store? in my example, I arbitrarily picked 1000
• will you ever need to retrieve non-sequential interval results? you'll need to apply the above procedure in chunks.