Improving Script Performance

Asked

Viewed 140 times

1

Guys, 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 rules above 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 observed from this sequence (starting at 13 and ending paragraph 1) is that it contains 10 items. Although it is not yet mathematically proven, is hoping that, given an integer any positive, the sequence will always come in 1.

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

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

But I can’t 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 performance

  • There is nothing in the statement that needs to be PHP. Need?

  • Yes, in this particular case it was asked to do in php, which is already a cost for performance.

  • 1

    Wouldn’t the largest be 837799 with 525 iterations? For 999904 makes 259. Besides, several numbers return equal amount. Which of these should have priority? All or the first one you find?

  • you’re right @Danielomine, there’s something wrong with my logic to return 142615 iterations with 999904.

  • If I remove the is and assign the value in the $n variable manually I get the right number of iterations, but for some reason when I pass the number by the $i it returns me this giant value, any idea?

  • I found the problem in logic, I will fix in the code. Anyway I still need help with performance. Thanks @Danielomine!

  • 2

    You don’t need to change almost anything. The problem is the Count being reset at the wrong point. Just from tapping my eye on the code I saw that this section was wrong and I tested it. Then I could see that it is the $Count.

  • 1

    Add the $count = 1; a line above the while($n != 1){

  • 1

    Then remove the $count = 1 that is within the parole.

  • Thank you, @Danielomine.

Show 5 more comments

1 answer

1


So, guys, I made it through 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’s 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;
?>

Browser other questions tagged php performance

You are not signed in. Login or sign up in order to post.