如何存储和重置PHP数组指针？

Question

我有一个关联数组，例如：

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

然后我执行

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

问题在于IsPrime函数也要遍历$primes数组。

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

这会破坏我正在迭代的数组指针。

我希望能够在IsPrime()函数中保存和恢复数组的内部指针，以避免出现这种副作用。有没有什么方法可以做到这一点？

- Hugh Bothwell

Answer 1

您可以“保存”数组的状态：

$state = key($array);

而“还原”（不确定是否有更好的方法）：

reset($array);

while(key($array) != $state)
    next($array);

- strager

---

这个效果是正确的，但在数组大小上是O(n)，使得我的算法成为O(n^2)是不可接受的。我在想扩展reset($arr, $key=0)会有多难呢？（重置到开头还是指定的键值对？） - Hugh Bothwell

这个答案可能不是“最佳实践”，但在我看来，它是回答问题的正确答案。 - aurora

Answer 2

不要依赖于数组指针，使用迭代器来替代。您可以将外部代码替换为：

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

- troelskn

---

（拍额头）好的，这个可以用 - 我以为foreach()使用数组自己的指针，但显然不是。它确实重置了数组内部指针，这有点奇怪的副作用？ - Hugh Bothwell

我不确定foreach的内部实现方式，但它维护了自己的状态。我不记得曾经在PHP中使用数组指针来遍历列表。 - troelskn

顺便说一句，对于您的值使用关联数组有点奇怪。我会使用一个普通列表，然后使用in_array()来检查值是否存在。 - troelskn

Answer 3

怎样再建立一个整数->整数的数组呢？其中索引是从0到n的连续数字，值则为关联数组的索引。这样就可以得到如下结果：

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

而不是直接引用$prime，你会使用$prime[$pointer[$i]]或类似的东西吗？

- wolfie

Answer 4

如果速度不是问题，而且您没有推动php内存限制，最快的解决方案就是复制您的质数数组并迭代2个不同的数组。

$awesomePrimes=$primes;

然后将您的函数中的globals和foreach更改为$awesomePrimes

- smazurov

---

对于包含 200 万项的数组，它使用额外的 68MB 内存 - 并非世界末日，但似乎有些浪费。 - Hugh Bothwell

Answer 5

在其中一个迭代中使用“for”循环。例如在IsPrime方法中使用此循环：

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

这样，方法中将不会使用内部数组指针。

- farzad