php - 优化碱基转化循环

Question

因此，对于我的密码学库，我有一个 base converter我经常使用。它不是世界上最有效的东西，但它适用于所有输入范围。

大部分工作由回调循环完成:

    $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，总共需要 4,815,076 次迭代)。

有什么想法吗？

Answer 1

执行此脚本所用时间的 99.9% 源自迭代输入的内在需要。由于 foreach 中的代码非常基础，减少执行时间的唯一方法是减少迭代次数。如果这不可能，那么您将拥有此功能的最高效版本。