Increase loop efficiency

[bokehman]

The following code sorts an array and outputs it as string of 5 chars.

Each array member has between 0 and 4 chars. The more characters a member has the earilier in the output string it should be. But if member 4 and meber 6 have the same string length they should appear in the output in that order. The code below works fine but is too slow.

Can you spot a way to speed it up?

$newOrder = '';
for($i = 4; $i > 0; $i--)
{
	foreach($order as $card)
	if(strlen($card) == $i)
	{
		$newOrder .= $card;
		if(strlen($newOrder)>4)
		{
			break(2);
		}
	}
}
$key = substr($newOrder, 0, 5);

[NogDog]

<?php
// test data:
$test = array
(
   'e',
   'bbbb',
   'aaaaa',
   'cccc',
   'dd'
);
// sort function:
function mysort($a, $b)
{
   $diff = strlen($b) - strlen($a);
   if($diff === 0) { $diff = 1; } // maintain original order
   return($diff);
}
// do it:
usort($test, "mysort");
$string = implode('', $test);
echo $string;
?>

[bokehman]

Hi Nogdog, thanks for that!

Unfortunately the double loop seems to be a lot quicker than the usort function. Also I don't know why but it is getting the order wrong. Run the bit of code below to see what I mean.

<?php

$order = array('A' => '', 'K' => 'K', 'Q' => 'Q', 'J' => 'JJJ', 'T' => '', '9' => '', '8' => '', '7' => '', '6' => '', '5' => '', '4' => '', '3' => '3', '2' => '');

#test one

function mysort($a, $b)
{
   $diff = strlen($b) - strlen($a);
   if($diff === 0) { $diff = 1; } // maintain original order
   return($diff);
}

microtime(true); #initialise
$result = 0;
for($i = 0; $i < 1000; $i++)
{
	$test = $order;
	$s = microtime(true);
	usort($test, "mysort");
	$e = microtime(true);

$result += ($e - $s);
}

$string = substr(implode('', $test), 0, 5);

echo '<h3>Nogdog</h3>'.$string;

echo '<br>';

echo round((($result*1000000)/($i+1))-2, 2).' microseconds<br>';



#test two

$result = 0;

for($i = 0; $i < 1000; $i++)
{
	$s = microtime(true);
	$newOrder = '';
	for($k = 4; $k > 0; $k--)
	{
	    foreach($order as $card)
	    if(strlen($card) == $k)
	    {
	        $newOrder .= $card;
	        if(strlen($newOrder)>4)
	        {
	            break(2);
	        }
	    }
	}
	$e = microtime(true);

$result += ($e - $s);
}


echo '<h3>Original</h3>'.substr($newOrder, 0, 5);

echo '<br>';

echo round((($result*1000000)/($i+1))-2, 2).' microseconds<br>';

?>

[NogDog]

I'd guess the sequence difference is due to the "undefined" ordering of equivalent elements of usort(), which I was trying to avoid with the "if" expression in the sort function. 🙁

[NogDog]

PS: Not exactly a fair timing test, since you're copying $order to $test in each test loop for my code but not yours. 😉

[bokehman]

NogDog wrote:

PS: Not exactly a fair timing test, since you're copying $order to $test in each test loop for my code but not yours. 😉

I'm starting the clock at usort and stopping it after. Nothing else in the loop is being timed. Unless I'm missing something. The overhead is about 2 microseconds.

$s = microtime(true);
usort($test, "mysort");
$e = microtime(true);

[NogDog]

Ah, probably my old eyes playing tricks on me again. Maybe they got confused by the initialization call to microtime()? As a friend of mine likes to say, "It sucks getting old, but the alternative is worse."

[bokehman]

Thanks for the input anyway!

[bokehman]

Just in case you are interested here is what I have come up with:

<?php

$order = array('A' => '', 'K' => 'K', 'Q' => 'Q', 'J' => 'JJJ', 'T' => '', '9' => '', '8' => '', '7' => '', '6' => '', '5' => '', '4' => '', '3' => '3', '2' => '');


# test one
$result = 0;
for($i = 0; $i < 1000; $i++)
{
        $newOrder = '';
        $j = 0;
        $s = microtime(true);
        for($k = 4; $k > 0; $k--)
        {
            foreach($order as $card)
            {
                    $j++;
                    if(strlen($card) == $k)
                    {
                        $newOrder .= $card;
                        if(strlen($newOrder)>4)
                        {
                            break(2);
                        }
                    }
            }
        }
        $e = microtime(true);

    $result += ($e - $s);
}


echo '<h3>Double loop</h3>'.substr($newOrder, 0, 5);

echo '<br>';

echo round((($result*1000000)/($i+1))-2, 2).' microseconds<br>Number of loops '.$j.'<br>';


# test two
$result = 0;
for($i = 0; $i < 1000; $i++)
{
        $order;
        $newOrder = '';
        $j = 0;
        $s = microtime(true);
        $quantities = array_map('strlen', $order);
        for($k = 4; $k > 0; $k--)
        {
            $keys = array_keys($quantities, $k);
            foreach($keys as $key)
            {
                    $j++;
                    $newOrder .= $order[$key];
                    if(strlen($newOrder)>4)
                    {
                        break(2);
                    }

            }
}
    $e = microtime(true);

    $result += ($e - $s);
}

echo '<h3>array_map</h3>'.substr($newOrder, 0, 5);

echo '<br>';

echo round((($result*1000000)/($i+1))-2, 2).' microseconds<br>Number of loops '.$j.'<br>';

?>

Result:

[B]Double loop[/B]

JJJKQ
71.66 microseconds
Number of loops 42


[B]array_map[/B]

JJJKQ
32.09 microseconds
Number of loops 3