Оптимизация алгоритма PHP

Question

Я построил класс, который находит наименьшее число, делящееся на все числа в заданном диапазоне.

Это мой код:

class SmallestDivisible 
{ 

    private $dividers = array(); 

    public function findSmallestDivisible($counter) 
    { 
     $this->dividers = range(10, 20); 

     for($x=1; $x<$counter; $x++) { 

      if ($this->testIfDevisibleByAll($x, $this->dividers) == true) { 
       return $x; 
      } 
     } 
    } 

    private function testIfDevisibleByAll($x, $dividers) 
    { 
     foreach($dividers as $divider) { 
      if ($x % $divider !== 0) { 
       return false; 
      } 
     } 

     return true; 
    } 
} 

$n = new SmallestDivisible(); 

echo $n->findSmallestDivisible(1000000000); 

Этот класс находит число, которое делится на все числа в диапазоне от 1 до 20 ($this->dividers).

Я знаю, что он работает хорошо, так как я тестировал его с другими, более низкими диапазонами, но, к сожалению, он не может найти решение для range(10, 20) в течение 30 секунд - и это время, после которого останавливается PHP-скрипт.

Параметр, который подается на метод findSmallestDivisible, является потолком группы номеров, которые скрипт собирается проверить (например, от 1 до $counter (1000000000 - это выполнение)).

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

Answer 1

Ваше решение является грубой силой и просто ужасно.

Вместо этого, как насчет обработки его математически? Вы ищете наименьшему общему кратному чисел в вашем диапазоне, так что ...

function gcd($n, $m) { 
    $n=abs($n); $m=abs($m); 
    list($n,$m) = array(min($m,$n),max($m,$n)); 
    while($r = $m % $n) { 
     list($m,$n) = array($n,$r); 
    } 
    return $n; 
} 
function lcm($n, $m) { 
    return $m * ($n/gcd($n,$m)); 
} 

function lcm_array($arr) { 
    while(count($arr) > 1) { 
     array_push($arr, lcm(array_shift($arr),array_shift($arr))); 
    } 
    return array_shift($arr); 
} 

var_dump(lcm_array(range(10,20))); 
// result int(232792560) 

Это означает, что исходный код должен был бы сделать 232,792,560 итераций, не удивительно, что он взял так долго!

Answer 2

Ваша цель - простой математический расчет с именем the least common multiple, но с использованием грубой силы для вычисления это совершенно неправильно (как вы уже выяснили).

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

Объяснение, описанное в разделе «A method using a table», действительно быстрое и не требует много памяти. Вы сохраняете только самый левый столбец таблицы (числа, которые вы хотите получить для lcm) и самый правый столбец (текущий шаг). Если вы его реализуете, я предлагаю вам скопировать код prime numbers в вашу программу, чтобы избежать их вычисления.

Answer 3

Вот еще одно решение, с которым я пришел.

Короче говоря, алгоритм будет вычислять LCM (lesast common multiple) для группы чисел.

class Lcmx 
{ 

    public $currentLcm = 0; 

    private function gcd($a, $b) 
    { 
     if ($a == 0 || $b == 0) 
      return abs(max(abs($a), abs($b))); 

     $r = $a % $b; 
     return ($r != 0) ? 
      $this->gcd($b, $r) : 
      abs($b); 
    } 

    private function lcm($a, $b) 
    { 
     return array_product(array($a, $b))/$this->gcd($a, $b); 
    } 

    public function lcm_array($array = array()) 
    { 
     $factors = $array; 
     while(count($factors) > 1) { 

      $this->currentLcm = $this->lcm(array_pop($factors), array_pop($factors)); 
      array_push($factors, $this->currentLcm); 
     } 

     return $this; 

    } 
} 

$l = new Lcmx; 
echo $l->lcm_array(range(1, 20))->currentLcm; 
//232792560