Sum of array of strings to bytes

Question

I'm trying to generate the sum of a collection of strings by calcuating each character's byte value into a sum:

$sum = 0;

foreach( $array as $item ) {
    $bytes = unpack( 'C*', $item );

    for( $i = 1; $i <= count( $bytes ); $i++ ) {
        if( isset( $bytes[$i+1] ) ) {
            $sum += $bytes[$i] - $bytes[$i+1];
        } else {
            $sum -= $bytes[$i];
        }
    }
}

return $sum;

The goal here is to compare past sums with newly generated sums (that is to say, check if there has been a new addition to the collection, suppose Item4) and perform actions if yes.

As such, it's very important that:

1. The algorithm can compute the sum irrespective of the order of the items.
2. The algorithm doesn't get confused by a case where let's say Item3 now becomes temI3 (and therefore the sum value is still the same, even though it's clearly not the same Item).

The whole secondary loop is to check against exactly that: loop through each byte (character) from each Item$i and to the final summ, add the differene between the first and second bytes. If there isn't a next one and we are at the end of the string, simply subtract if from the whole sum.

As such, the following:

Input(s): ['Item1', 'Item2', 'Item3'] / ['Item1', 'Item2', 'Item3'] , output: the same int. Where as ['Item1', 'Item2', 'Ite3m'] outputs a different int.

The performance as of now is as follows:

100000 items across 100 runs: 0.18s / 1000000 items across 100 runs: 2.05s

And although I understand that to parse and do these calculations for a million items in 2s is rather fast for PHP, I still think that, if you look at what the thing does, it's still slow.

Any way to speed this up?

Answer 1

Dont call functions in loop conditions.

Calling count as condition of a for is a common mistake. It has the same behaviour but it is slower because the count function has to be called repeatedly although it returns the same value all the time. Unless the count changes during iterations, prefetch the count before the loop.

Iterate only where body is same

In your for you always check if the element is the last one, to do something else in that case. You better exclude it from the for, and handle the last element separately.

Unpack is not necesary

I wasnt really sure until I benched it, but just accessing individual characters of the strings with the [] operator and using the ord function to get the numeric value of bytes seems quite faster.

Not sure your algorithm is correct

As I've shown in me2 implementation, you are actualy adding just the first charracter of each word and subracting last character of each word twice. It means that none of the characters except first and last in each word is contributing to the resulting sum. Therefore item Item1 is the same as Ixxx1. (Try for $input2 in the code below and see for yourself).

<?php

function op(array $array)
{
    $sum = 0;

    foreach( $array as $item ) {
        $bytes = unpack( 'C*', $item );

        for( $i = 1; $i <= count( $bytes ); $i++ ) {
            if( isset( $bytes[$i+1] ) ) {
                $sum += $bytes[$i] - $bytes[$i+1];
            } else {
                $sum -= $bytes[$i];
            }
        }
    }

    return $sum;
}

function op2(array $array)
{
    $sum = 0;

    foreach( $array as $item ) {
        $bytes = unpack( 'C*', $item );

        $length = count( $bytes );
        for( $i = 1; $i < $length ; $i++ ) {
            $sum += $bytes[$i] - $bytes[$i+1];
        }
        if ($length > 0) {
            $sum -= $bytes[$length];
        }

    }

    return $sum;
}

function me(array $array)
{
    $sum = 0;

    foreach( $array as $item ) {
        $length_1 = strlen($item) - 1;
        for ($i = 0; $i < $length_1; ++$i) {
            $sum += ord($item[$i]) - ord($item[$i + 1]);
        }
        if ($length_1 >= 0) {
            $sum -= ord($item[$length_1]);
        }

    }

    return $sum;
}

function me2(array $array)
{
    $sum = 0;

    foreach( $array as $item ) {
        $length = strlen($item);
        if ($length == 1) {
            $sum -= ord($item[0]);
        } elseif ($length > 1) {
            $sum += ord($item[0]) - 2 * ord($item[$length-1]);
        }
    }

    return $sum;
}

function bench(callable $callback, array $input, int $reps = 10000)
{
    $total = 0;
    for ($i = 0; $i < $reps; ++$i) {
        $start = \microtime(true);
        $callback($input);
        $total +=  \microtime(true) - $start;
    }
    return $total / $reps;

}

$input1 = ['Item1', 'Item2', 'Item3', 'X', ''];
$input2 = ['Ixxx1', 'Ixxx2', 'Ixxx3', 'X', ''];

$outOp = op($input1);
$outOp2 = op2($input1);
$outMe = me($input1);
$outMe2 = me2($input1);

echo 'OP: ' . bench('op', $input1);
echo \PHP_EOL;
echo $outOp;
echo \PHP_EOL;

echo 'OP improved: ' . bench('op2', $input1);
echo \PHP_EOL;
echo $outOp2;
echo \PHP_EOL;

echo 'No unpack: ' . bench('me', $input1);
echo \PHP_EOL;
echo $outMe;
echo \PHP_EOL;

echo 'Me2: ' . bench('me2', $input1);
echo \PHP_EOL;
echo $outMe2;
echo \PHP_EOL;

OP: 3.5921573638916E-6
-169
OP improved: 3.3084869384766E-6
-169
No unpack: 1.4432907104492E-6
-169
Me2: 5.5739879608154E-7
-169