Increase loop efficiency

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Increase loop efficiency

Post 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);
User avatar
volka
DevNet Evangelist
Posts: 8391
Joined: Tue May 07, 2002 9:48 am
Location: Berlin, ger

Post 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
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

I tried usort and it takes 3x longer than the double loop.
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post 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.
User avatar
volka
DevNet Evangelist
Posts: 8391
Joined: Tue May 07, 2002 9:48 am
Location: Berlin, ger

Post 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.
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post 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>';


?>
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post 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.
User avatar
volka
DevNet Evangelist
Posts: 8391
Joined: Tue May 07, 2002 9:48 am
Location: Berlin, ger

Post by volka »

Ah ok. Milliseconds is a scale unit I don't care about ;) Good luck.
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post 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.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post 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
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post 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?
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post 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.
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post 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.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post 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...
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post 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.
Post Reply