Improving script perfomance

Question

Improving script perfomance

Navigation

#1 by (1 votes)

1

Well, I'm doing the following challenge:

The following iterative sequence is defined by the set of integers   positive where:

n - > n / 2 (if n is even) n -> 3n + 1 (if n is odd)

Using the above rules and starting with the number 13, we would generate the   following sequence:

13 40 20 10 5 16 8 4 2 1

What can be seen from this sequence (starting at 13 and ending   in 1) is that it contains 10 items. Although not yet   mathematically proved, is hoping that, given an integer number   the sequence will always be 1.

Which positive integer below 1 million produces the sequence with more   items?

NOTE: Your code needs to run in less than 5 seconds for the case of   1 million.

But I can not get the script to run in less than 13 seconds.

jpklzm$ time php teste.php 
Resposta: 837799
Iterações: 525
real    0m13.737s
user    0m13.203s
sys 0m0.117s

How can I improve the performance of this script?

<?php
$count = 1;
$hicount = 0;
$hicountOwner = 0;
$n = 0;
for($i = 1; $i < 1000000; $i++){
  $n = $i;
  while($n != 1){
    $n = ($n % 2 === 0) ? $n/2 : ($n * 3) + 1;
    $count++;
  }
  if($count > $hicount){
    $hicount = $count;
    $hicountOwner = $i;
  }
  $count = 1;
}
echo 'Resposta: ',$hicountOwner,PHP_EOL;
echo 'Iterações: ',$hicount;
?>

php desempenho

asked by anonymous 28.09.2016 / 04:30

1 answer

Select the most repeated data in a column and display them Discover link in python

score 1 · Accepted Answer

So, guys, I was able to meet the challenge. I made a cache to store the data of operations that had already been done for other numbers and with that I was able to reduce the execution of the code to 1.5s.

Here is the code for anyone who wants to take a look:

<?php
ini_set('memory_limit', '-1');
$limit = 1000000;
$hicount = 0;
$hicountOwner = 0;
$n;
$cache = array(0);

for ($i = 0; $i < sizeof($cache); $i++) {
    $cache[$i] = -1;
}
$cache[1] = 1;

for ($i = 1; $i <= $limit; $i++) {
    $n = $i;
    $j = 0;
    while ($n != 1 && $n >= $i) {
        $j++;
        $n = ($n % 2 === 0) ? $n/2 : ($n * 3) + 1;
    }
    $cache[$i] = $j + $cache[$n];
    if ($cache[$i] > $hicount) {
        $hicount = $cache[$i];
        $hicountOwner = $i;
    }
}
echo 'Resposta: ',$hicountOwner,PHP_EOL;
echo 'Iterações: ',$hicount;
?>