Page 1 of 2

Increase loop efficiency

Posted: Wed Nov 15, 2006 9:12 am
by 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?

Code: Select all

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

Posted: Wed Nov 15, 2006 11:21 am
by volka
maybe it's faster if you first sort the array via usort and then iterate the array until you have 5 characters.
usort uses the quicksort algorithm, it's quite fast. see http://en.wikipedia.org/wiki/Quicksort

Posted: Wed Nov 15, 2006 1:26 pm
by bokehman
I tried usort and it takes 3x longer than the double loop.

Posted: Wed Nov 15, 2006 1:33 pm
by timvw
It all depends on the size of input (the number of items to sort)....

In general i would do it as following:

Build pairs of (string value, string length), thus avoiding the overhead of calling strlen during the sorting process itself.
And then sort the pairs using the length attribute.
And then return the values of the pairs.

Posted: Wed Nov 15, 2006 1:52 pm
by volka
timvw wrote:Build pairs of (string value, string length), thus avoiding the overhead of calling strlen during the sorting process itself.
php's strlen() is not as costly as the "old C sz-strings" strlen(). The length of a string is stored, it does not need to be calculated each time strlen() is called.
bokehman wrote:I tried usort and it takes 3x longer than the double loop.
Then we're probably not talking about member 4 and 6 but 40000 and 312000 ;)
Maybe it's possible to narrow down the search domain before all elements are in that huge array.

Posted: Wed Nov 15, 2006 2:15 pm
by bokehman
I'm guessing you mean something like this:

Code: Select all

foreach($test as $member)
{
	$quantities[] = strlen($member);
}
array_multisort($quantities, SORT_DESC, $test);
If so that is quite a bit faster but for some reason the sort order is wrong. The following code demonstrates both points.

Code: Select all

<?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++)
{
	$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>Double loop</h3>'.substr($newOrder, 0, 5);

echo '<br>';

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


# test two
$result = 0;
for($i = 0; $i < 1000; $i++)
{
	$test = $order;
	$quantities = array();
	$s = microtime(true);
	foreach($test as $member)
	{
		$quantities[] = strlen($member);
	}
	array_multisort($quantities, SORT_DESC, $test);
	$e = microtime(true);
		
	$result += ($e - $s);
}

echo '<h3>array_multisort</h3>'.implode($test);

echo '<br>';

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


?>

Posted: Wed Nov 15, 2006 2:25 pm
by bokehman
volka wrote:
bokehman wrote:I tried usort and it takes 3x longer than the double loop.
Then we're probably not talking about member 4 and 6 but 40000 and 312000 ;)
Maybe it's possible to narrow down the search domain before all elements are in that huge array.
It is just the 13 item array posted above and it take 160 microseconds compared to 65 with the double loop. Tim's method is taking 30 but I can't get it to work right.

Posted: Wed Nov 15, 2006 2:32 pm
by volka
Ah ok. Milliseconds is a scale unit I don't care about ;) Good luck.

Posted: Wed Nov 15, 2006 2:56 pm
by bokehman
volka wrote:Ah ok. Milliseconds is a scale unit I don't care about ;) Good luck.
I said microseconds not milliseconds and when you are doing a brute force search saving a few microseconds adds up to a lot of time. I rewrote my original function and got down from 3 milliseconds to 156 microseconds of which this loop is taking 65. That's almost half. if I could get Tim's idea to work I could save another 30.

Posted: Wed Nov 15, 2006 3:34 pm
by feyd

Code: Select all

<?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++)
{
        $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>Double loop</h3>'.substr($newOrder, 0, 5);

echo '<br>';

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


# test two
$result = 0;
for($i = 0; $i < 1000; $i++)
{
        $test = $order;
        $quantities = array();
        $s = microtime(true);
        foreach($test as $member)
        {
                $quantities[] = strlen($member);
        }
        array_multisort($quantities, SORT_DESC, $test);
        $e = microtime(true);
               
        $result += ($e - $s);
}

echo '<h3>array_multisort</h3>'.implode($test);

echo '<br>';

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



# test three
$result = 0;
for($i = 0; $i < 1000; $i++)
{
        $test = $order;
        $s = microtime(true);
        $quantities = array_map('strlen', $order);
        array_multisort($quantities, SORT_DESC, $test);
        $e = microtime(true);
               
        $result += ($e - $s);
}

echo '<h3>array_multisort Part 2</h3>'.implode($test);

echo '<br>';

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



?>

Code: Select all

Double loop
JJJKQ
172.72 microseconds

array_multisort
JJJ3KQ
65.34 microseconds

array_multisort Part 2
JJJ3KQ
30.5 microseconds

Posted: Wed Nov 15, 2006 3:46 pm
by bokehman
feyd: That's a huge improvement but there is something wrong with my implementation of array_multisort. Notice in your last two results the "3" is out of turn. Any idea what is going wrong?

Posted: Wed Nov 15, 2006 3:50 pm
by feyd
Other than the output being six characters, it's technically sorted correctly as the character '3' falls before 'K'. That's simple enough to truncate to five characters, if that's what you're worried about.

Posted: Wed Nov 15, 2006 4:16 pm
by bokehman
Point taken about how the function works but for me the double loop produces the correct output and the order is crutial.

I thought array multisort ordered the second array based on the first. I didn't realise the second played any part in the sort order.

Posted: Wed Nov 15, 2006 4:36 pm
by feyd
Do you want numbers stripped out? It's pretty simple to do on the front end with array_filter() and ctype_alpha(), depending on how you want the results...

Posted: Wed Nov 15, 2006 4:41 pm
by bokehman
feyd wrote:Do you want numbers stripped out?
No I just need the order right. They are playiing cards and I am trying to sort them. Don't worry for the minute because I might be on to something.