4

I have an associative array, ie

$primes = array(
  2=>2,
  3=>3,
  5=>5,
  7=>7,
  11=>11,
  13=>13,
  17=>17,
  // ...etc
);

then I do

// seek to first prime greater than 10000
reset($primes);
while(next($primes) < 10000) {}
prev($primes);

// iterate until target found
while($p = next($primes)) {
      $res = doSomeCalculationsOn($p);

      if( IsPrime($res) )
          return $p;
}

The problem is that IsPrime also loops through the $primes array,

function IsPrime($num) {
    global $primesto, $primes, $lastprime;

    if ($primesto >= $num)
        // using the assoc array lets me do this as a lookup
        return isset($primes[$num]);

    $root = (int) sqrt($num);
    if ($primesto < $root)
        CalcPrimesTo($root);

    foreach($primes as $p) {       // <- Danger, Will Robinson!
        if( $num % $p == 0 )
            return false;

        if ($p >= $root)
            break;
    }

    return true;
}

which trashes the array pointer I am iterating on.

I would like to be able to save and restore the array's internal pointer in the IsPrime() function so it doesn't have this side effect. Is there any way to do this?

Improve this question
0

5 Answers 5

Reset to default
5

You can "save" the state of the array:

$state = key($array);

And "restore" (not sure if there's a better method):

reset($array);

while(key($array) != $state)
    next($array);
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Um... the right effect, but this is O(n) in the size of the array, which makes my algorithm O(n^2) which is unacceptable. I wonder how hard it would be to extend reset($arr, $key=0) ? (Reset to start or to specified key-value?)
This answer might not be "best practice", but it's the correct answer to the question, ... imo.
4

Don't rely on array pointers. Use iterators instead.

You can replace your outer code with:

foreach ($primes as $p) {
  if ($p > 10000 && IsPrime(doSomeCalculationsOn($p))) {
    return $p;
  }
}
Improve this answer

3 Comments

(smacking forehead) OK, this works - I thought foreach() used the array's own pointer, but apparently not. It does reset the array internal pointer, which is kind of an odd side-effect?
I'm not sure how the internal implementation of foreach works, but it maintains its own state. I don't remember ever using array pointers to traverse lists in PHP.
Btw. it's kind of odd to use an assoc array for your values. I would use a plain list, and then use in_array() to check if a value exists.
0

If speed is not an issue and you aren't pushing php memory limits the quickest solution is just to duplicate your primes array and iterate 2 different ones.

$awesomePrimes=$primes;

Then change globals and foreach in your function to $awesomePrimes

Improve this answer

1 Comment

For an array containing 2 million items, that uses an extra 68MB of memory - not the end of the world, but seems wasteful.
0

How about doing one more array of int -> int, where the the index is a running number from 0 to n and the value is the index of the associative array? So, you would have:

$pointer = array(
  0 => 2,
  1 => 3,
  2 => 5,
  // ...
);

and instead of referring directly to $prime you would use $prime[$pointer[$i]], or something similar?

Improve this answer

Comments

0

use a "for" loop for one of your iterations. for example use this loop in your IsPrime method:

$primesLength = count($primes); // this is to avoid calling of count() so many times.
for ($counter=0 ; $counter < $primesLength ; $counter++) {
    $p = $primesLength[$counter];
    if( $num % $p == 0 )
            return false;

    if ($p >= $root)
            break;
}

this way the internal array pointer will not be used in the method.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.