Geek Answers Handbook

Base conversion cycle optimization

So, for my cryptography library, I have a basic converter that I use quite often. This is not the most efficient thing in the world, but it works well enough for all input ranges.

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

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

The problem that I am currently facing is that I feed her 2 kilobytes of data, it takes almost 10 seconds to start it. So I decided to optimize it. So far, I have reduced this to about 4 seconds, replacing this entire 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; }

The problem I am facing is how to optimize it (if possible). I think the problem is the number of iteration shifts that are required for large input (for an array of elements 2000, from base 256 to base 10), a total of 4,815,076 iterations.

Any thoughts?

+4
source share
3 answers

Yes, you can optimize it a bit:

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

You will get some reduction in memory and processor use, and it is much more interesting, but not read in the course (:.

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

+1
source

99.9% of the time spent executing this script comes from the inherent need to iterate through the input. Since the code inside foreach is very simple, the only way to reduce execution time is to reduce the number of iterations. If this is not possible, then you have the most efficient version of this feature.

+2
source

I'm not sure but

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

maybe a little faster ...

-1
source

More articles:


All Articles