Как эффективно выполнять итерацию, когда известны некоторые результаты подсерий

Question

У вас есть функция, которая всегда вводит интервал (в этом случае натуральные числа), эта функция возвращает результат, но на процессоре довольно дорога, имитируется sleep в этом примере:

function calculate($start, $end) { 

    $result = 0; 

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

    return $result; 
} 

для того, чтобы быть более эффективным, есть массив старых результатов, который содержит интервал использовал результат функции для этого интервала:

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

Если я позвоню calculate(1,10) функция должна иметь возможность вычислять новые интервалы на основе старых результатов и накапливать их. В этом конкретном случае старый результат должен принимать от 1 до 2, что добавляет старый результат от 2 до 6 и делает новый calculate(6,10) и добавляет, что слишком. Учитывайте, что функция игнорирует старый сохраненный интервал от 4 до 7, поскольку было удобнее использовать 2-6.

Это визуальное представление задачи:

Конечно, в этом примере, calculate() довольно просто, и вы можете просто найти конкретные пути решения этой проблемы вокруг него, но в реальном коде calculate() является комплекс, и единственное, что я знаю, это то, что calculate(n0,n3)==calculate(n0,n1)+calculate(n1,n2)+calculate(n2,n3).

Я не могу найти способ решить проблему повторного использования старых данных, не используя кучу IF и foreach, я уверен, что существует более элегантный подход к решению этого вопроса.

Вы можете играть с code here.

Примечание: Я использую PHP, но я могу читать JS, Pyton, C и подобные языки.

Answer 1

Если вы уверены, что calculate(n0,n3)==calculate(n0,n1)+calculate(n1,n2)+calculate(n2,n3), то мне кажется, что одним из подходов может быть просто создание кеша базы данных.

вы можете предварительно вычислить каждый дискретный интервал и сохранить его результат в записи.

$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++; 
} 

теперь, когда появляются новые запросы, поиск базы данных должен быть значительно быстрее. обратите внимание, что вам может понадобиться возиться с моими граничными случаями в этом грубом примере.

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; 
} 

Есть несколько очевидных соображений, таких как:

• кэш недействительности. как часто меняются результаты вашей функции calculate? вам нужно будет повторно заполнить базу данных.
• Сколько интервалов вы хотите сохранить? в моем примере, я произвольно выбрал 1000
• вам когда-нибудь понадобится получить результаты без последовательного интервала? вам необходимо применить описанную выше процедуру в кусках.

Answer 2

я писал:

function findFittingFromCache($from, $to, $cache){ 
    //length for measuring usefulnes of chunk from cache (now 0.1 means 10% percent of total length) 
    $totalLength = abs($to - $from); 
    $candidates = array_filter($cache, function($val) use ($from, $to, $totalLength){ 
     $chunkLength = abs($val['e'] - $val['s']); 
     if($from <= $val['s'] && $to >= $val['e'] && ($chunkLength/$totalLength > 0.1)){ 
      return true; 
     } 
     return false; 
    }); 
    //sorting to have non-decremental values of $x['s'] 
    usort($candidates, function($a, $b){ return $a['s'] - $b['s']; }); 
    $flowCheck = $from; 
    $needToCompute = array(); 
    foreach($candidates as $key => $val){ 
     if($val['s'] < $flowCheck){ 
      //already using something with this interval 
      unset($candidates[$key]); 
     } else { 
      if($val['s'] > $flowCheck){ 
       //save what will be needed to compute 
       $needToCompute[] = array('s'=>$flowCheck, 'e'=>$val['s']); 
      } 
      //increase starting position for next loop 
      $flowCheck = $val['e']; 
     } 
    } 
    //rest needs to be computed as well 
    if($flowCheck < $to){ 
     $needToCompute[] = array('s'=>$flowCheck, 'e'=>$to); 
    } 
    return array("computed"=>$candidates, "missing"=>$needToCompute); 
} 

Это функция, которая возвращает вам два массива, один «вычисленных» Держится найдено уже вычисленных штук, второй «отсутствует» имеет пробелы между ними, которые должны быть вычислены еще.

Внутри функции есть порог 0,1, который дисквалифицирует куски менее 10% от общей искомой длины, вы можете переписать функцию для отправки порога в качестве параметра или полностью исключить его.

Я предполагаю, что результаты будут сохранены и после вычисления добавлены в кеш ($ oldResults), которые могут иметь любую форму (например, база данных, предложенная Джеффом Пакеттом). Не забудьте добавить все вычисленные фрагменты и целую длину в кеш.

Я извиняюсь, но я не могу найти способ без циклов и сослагательного наклонения

Работа демо: link