优化进制转换循环

Question

对于我的加密库，我有一个进制转换器，我经常使用它。虽然不是世界上最有效的工具，但对于所有输入范围都能很好地工作。

主要的工作由回调循环完成：

    $callback = function($source, $src, $dst) {
        $div       = array();
        $remainder = 0;
        foreach ($source as $n) {
            $e         = floor(($n + $remainder * $src) / $dst);
            $remainder = ($n + $remainder * $src) % $dst;
            if ($div || $e) {
                $div[] = $e;
            }
        }
        return array(
            $div,
            $remainder
        );
    };
    while ($source) {
        list ($source, $remainder) = $callback($source, $srcBase, $dstBase);
        $result[]                  = $remainder;
    }

基本上，它会接受在$srcBase中的数字数组并将其转换为在$dstBase中的数字数组。例如输入为array(1, 1), 2, 10，将得到array(3)作为结果。另一个例子是array(1, 0, 0), 256, 10会得到array(1, 6, 7, 7, 7, 2, 1, 6)（数组的每个元素都是$dstBase中的单个“数字”）。

我现在面临的问题是，如果我输入2kb的数据，它需要近10秒才能运行。因此，我开始优化它。到目前为止，我已经通过用递归循环来替换整个结构，将其降低到大约4秒左右：

    while ($source) {
        $div       = array();
        $remainder = 0;
        foreach ($source as $n) {
            $dividend  = $n + $remainder * $srcBase;
            $res       = (int) ($dividend / $dstBase);
            $remainder = $dividend % $dstBase;
            if ($div || $res) {
                $div[] = $res;
            }
        }
        $result[] = $remainder;
        $source   = $div;
    }

我面临的问题是如何进一步优化它（如果可能的话）。我认为问题在于大量迭代操作，例如对于一个2000元素的数组，从基数256转换到基数10，总共需要4815076次迭代。

您有什么想法吗？

- ircmaxell

Answer 1

99.9%的执行时间来自于遍历输入，这是必须的。由于foreach内部的代码非常基础，所以唯一减少执行时间的方法就是减少迭代次数。如果不可能减少迭代次数，那么你已经拥有了最有效率的函数版本。

- VettelS

---

这正是我的观点。不是如何优化$x % $y，而是如何改变算法以减少所需的迭代次数... - ircmaxell

Answer 2

可以进行一些优化：

$source_count = count($source);
while ($source) {
    $remainder = $i = 0;
    foreach ($source AS &$n) {
        $dividend = $n + $remainder * $srcBase;
        $remainder = $dividend % $dstBase;
        $res = ($dividend - $remainder) / $dstBase;
        if ($i || $res)
            $source[$i++] = $res;
    }
    for ($j=$i; $j < $source_count; $j++)
        unset($source[$i]);
    $source_count=$i;
    $result[] = $remainder;
}

或者更快，但更晦涩难懂：

$source_count = count($source);
while ($source) {
    $remainder = $i = 0;
    foreach ($source AS &$n) {
        if (($res = ($dividend - ($remainder = ($dividend = $n + $remainder * $srcBase) % $dstBase)) / $dstBase) || $i)
            $source[$i++] = $res;
    }
    for ($j=$i; $j < $source_count; $j++)
        unset($source[$i]);
    $source_count=$i;
    $result[] = $remainder;
}

你会获得一些内存和CPU使用量的减少，这样做更加有趣，但当然不可读（：）。

但是就个人而言，我认为你正在错误的方式上实现它。我认为你应该使用一些快速的C代码来完成这种任务（通过使用系统调用或编写/安装现有的PHP模块）。而且我认为像Hip-Hop PHP、Zend Optimized等代码优化器/编译器可以在这种情况下显著提高性能。

- XzKto

Answer 3

我不确定，但是

$dividend  = $remainder * $srcBase + $n;

可能需要快一点...

- powtac

---

你怎么想的？为什么那样会更快呢？ - ircmaxell

曾经读过有关内部数学运算的方式，但我不确定。它是关于首先阅读整个函数，但当*首先被使用时，PHP可以在不阅读下一个标记的情况下开始数学运算... - powtac

它仍然需要查看下一个标记，因为还有其他更高优先级的运算符。因此，这不会有任何区别（或者如果有区别，则最多只有纳秒级别的差异）... - ircmaxell