优化基准转换回路 [英] Optimizing Base Conversion Loop

问题描述

所以，我的密码库，我有一个的基地转换的，我经常使用。这不是世界上最有效的事情，但它工作得很好输入的所有范围。

So, for my Cryptography Library, I have a base converter that I use quite often. It's not the most efficient thing in the world, but it works quite well for all ranges of input.

这项工作的大部分是由回调循环完成的：

The bulk of the work is done by the callback loop:

    $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 。因此，一个例子投入将是阵列（1,1），2，10 这将使阵列（3）结果是。另一个例子是阵列（1，0，0），256，10 这将使阵列（1，6，7，7，7， 2，1，6）（数组中的每个元素是一个数字的 $ dstBase 。

Basically, it takes an array of numbers in $srcBase and converts them to an array of numbers in $dstBase. So, an example input would be array(1, 1), 2, 10 which would give array(3) as a result. Another example would be array(1, 0, 0), 256, 10 which would give array(1, 6, 7, 7, 7, 2, 1, 6) (each element of the array is a single "digit" in the $dstBase.

我现在面临的，现在的问题是，如果我给它的数据2KB，它需要近10秒运行。所以我已经开始着手优化。到目前为止，我把它降低到约4秒这个递归循环更换的整体结构：

The problem I'm now facing, is if I feed it 2kb of data, it takes almost 10 seconds to run. So I've set out to optimize it. So far, I have it down to about 4 seconds by replacing that whole structure with this recursive loop:

    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迭代计）。

The problem I'm facing, is how to optimize it further (if that's even possible). I think the problem is the shear number of iterations it takes for the large input (for a 2000 element array, from base 256 to base 10, it takes 4,815,076 iterations in total).

有什么想法？

推荐答案

是的，它可以优化的一点：

Yes, it can be optimized a little:

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

甚至更快，但比较模糊：

or even faster, but more obscure:

$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使用率减少，这是更有趣，但五言不可读（：

You will get some memory and CPU usage reduction and it is much more fun but of cource unreadable (:.

不过，我个人认为你正在做了错误的方式。我认为你应该使用一些快速C $ C $下这样的任务（通过使用系统调用或写入/安装现有的PHP模块）。我认为，code优化/喜欢的Hip-Hop PHP，Zend的优化等编译器可以大大在这种情况下提高性能。

But personally I think you are doing it the wrong way. I think you should use some fast C code for this kind of task(by using system call or writing/installing existing PHP module). And I think that code optimizers/compilers like Hip-Hop PHP,Zend Optimized etc. can dramatically increase performance in this case.

这篇关于优化基准转换回路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！