Efficiency and sorting multidimensional arrays

[zeb]

I've read several post here on sorting multidimensional arrays, but everyone's problem tends to be different, and so are the solutions.

My question is a bit different (I think), and it has to do with efficiency.

I have an array like this:

$MENU['unique_id_1'] = array(
    'allow' => 1,
    'mod' => "short string: 5-15 chars",
    'group' => 11.4,
    'label' => "short string: 10-25 chars",
    'text' => "long string: 50-100 chars",
    'help' => "very long string: 50-1000 chars",
    );
$MENU['unique_id_2'] = array(
    'allow' => 1,
    'mod' => "short string: 5-15 chars",
    'group' => 7.2,
    'label' => "short string: 10-25 chars",
    'text' => "long string: 50-100 chars",
    'help' => "very long string: 50-1000 chars",
    );
$MENU['unique_id_3'] = array(
    'allow' => 1,
    'mod' => "short string: 5-15 chars",
    'group' => 20.9,
    'label' => "short string: 10-25 chars",
    'text' => "long string: 50-100 chars",
    'help' => "very long string: 50-1000 chars",
    );
// and so-on for about 30 unique menu id's...

I need the array ordered by the group key while keeping all associations. I have written my own procedure, but I always thought that it was a bit cumbersome. However, when I looked into other methods using uasort() and array_multisort(), it turned out to take more time than my original method. So I should probably let sleeping dogs lie... but I wanted to make sure I was doing everything correctly. Here is my code for sorting this:

//---------------------------------------------------
// build a $sort array to hold the $MENU group values
//---------------------------------------------------
$sort = array();
foreach ( $MENU as $k => $a )
    {
    $i = $a['group'];
    $sort[ strval( $i ) ] = $k;
    }

//-------------------------------------------------------------
// sort the new $sort array by key (which are the group values)
//-------------------------------------------------------------
ksort( $sort );

//------------------------------------------------------------
// build a clone of the $MENU array with the new keys in order
//------------------------------------------------------------
$newMENU = array();
foreach ( $sort as $menu_key )
    {
    $newMENU[ $menu_key ] = $MENU[ $menu_key ];
    }

//---------------------------------------------------
// overwrite the $MENU array with our new ordered one
//---------------------------------------------------
$MENU = $newMENU;

This takes 0.000786 seconds on average. When I tried these other methods, it took about twice as long to execute:

// version 1... about 0.0018 seconds consistently
uasort( $MENU, 'cmp' );
function cmp( $a, $b )
    {
    return strcmp( $a['group'], $b['group'] );
    }

// version 2... about 0.00147 seconds consistently
uasort( $MENU, 'cmp' );
function cmp( $a, $b )
    {
    if ( $a['group'] == $b['group'] )
        {
        return 0;
        }
    return ( $a['group'] < $b['group'] ) ? -1 : 1;
    }

// version 3... about 0.00135 seconds consistently
uasort( $MENU, 'cmp' );
function cmp( $a, $b )
    {
    if ( $a['group'] < $b['group'] )
        {
        return -1;
        }
    elseif ( $a['group'] > $b['group'] )
        {
        return 1;
        }
    return 0;
    }

Of course we are splitting hairs on versions 2 and 3, but this code is part of a very long script and I am trying to trim as much fat as possible. I didn't figure out how to use array_multisort() for this particular situation, but maybe someone else can provide some suggestions about speed and maybe some other considerations regarding the way my first (and fastest) solution is written.

Thanks!

[Shrike]

Using various timers taken from the microtime() manual page I found uksort() to be up to twice as fast as your approach. Timing functions vary alot though 🙂

[zeb]

I don't know what you are talking about. Replacing uasort with uksort doesn't sort the array the way I want. And it actually takes longer than the other methods: 0.0022 seconds.

Show me the code you used to test this.

[Shrike]

Not by my timing. I used this code:

// Set up data
$menu1 = $MENU;
$menu2 = $MENU;
$menu3 = $MENU;

// Your custom sort
$timestart = microtime();
$sort = array(); 
foreach ( $menu1 as $k => $a ) 
    { 
    $i = $a['group']; 
    $sort[ strval( $i ) ] = $k; 
    } 
ksort( $sort ); 
$newMENU = array(); 
foreach ( $sort as $menu_key ) 
    { 
    $newMENU[ $menu_key ] = $menu1[ $menu_key ]; 
    } 
$menu1 = $newMENU;  

$timeend = microtime();
echo number_format(((substr($timeend,0,9)) + (substr($timeend,-10)) - (substr($timestart,0,9)) - (substr($timestart,-10))),8) . "\n<br>";


// uasort()
$timestart = microtime();
uasort( $menu2, 'cmp' );
$timeend = microtime();
echo number_format(((substr($timeend,0,9)) + (substr($timeend,-10)) - (substr($timestart,0,9)) - (substr($timestart,-10))),8) . "\n<br>";

function cmp( $a, $b )
{
	if( $a['group'] == $b['group'] ) return 1;
	return ( $a['group'] < $b['group'] ) ? -1 : 1;
}

// uksort()
$timestart = microtime();
uksort( $menu3, 'cmp2' );
$timeend = microtime();
echo number_format(((substr($timeend,0,9)) + (substr($timeend,-10)) - (substr($timestart,0,9)) - (substr($timestart,-10))),8) . "\n<br>";

function cmp2( $a, $b )
{
	global $menu3;
	if( $menu3[$a]['group'] == $menu3[$b]['group'] ) return 1;
	return ( $menu3[$a]['group'] < $menu3[$b]['group'] ) ? -1 : 1;
}

Results:

0.00007010 
0.00002885 
0.00002789 

My timing function might be screwed (it's taken from the microtime() page). But it's at least screwed for all three tests.

[mrhappiness]

i don't like that global thing...

but for me shrike's uasort is faster than your code zeb

[zeb]

When I copy and paste that code and run it 50 times with my actual $MENU array with 35 keys... these are the averages that I get:

// on my server
0.0004579
0.0006822
0.0012260

// on my local development machine:
0.0009910
0.0020009
0.0028626

my method (albeit cumbersome) is clearly faster.

[Shrike]

Very strange, I wasn't expecting that at all. The turnaround point where your version becomes faster isn't even especially high (about 10-15 array indices). These are the results for a 1000 index array, sorted 10 times:

Array
(
    [0] => 0.00702190
    [1] => 0.01208615
    [2] => 0.01383209
    [3] => 0.01366806
    [4] => 0.01377511
    [5] => 0.01284695
    [6] => 0.01399922
    [7] => 0.01269197
    [8] => 0.01329494
    [9] => 0.01532602
)
Array
(
    [0] => 0.04704595
    [1] => 0.04613900
    [2] => 0.05318093
    [3] => 0.04483795
    [4] => 0.04571795
    [5] => 0.04492188
    [6] => 0.04571509
    [7] => 0.05122900
    [8] => 0.05050111
    [9] => 0.04428101
)
Array
(
    [0] => 0.06702209
    [1] => 0.06296802
    [2] => 0.06507587
    [3] => 0.06399703
    [4] => 0.06362414
    [5] => 0.06624985
    [6] => 0.06659603
    [7] => 0.06530094
    [8] => 0.06412816
    [9] => 0.06427789
)

function makeArray()
{
	for( $i = 1; $i <= 1000; $i++ )
	{
		$MENU['unique_id_' . $i] = array (
		'allow' => 1, 
		'mod' => "short string: 5-15 chars", 
		'group' => rand( 1, 10000 ),
		'label' => "short string: 10-25 chars", 
		'text' => "long string: 50-100 chars", 
		'help' => "very long string: 50-1000 chars",
		);
	}
	return $MENU;
}

So three hundreths of a second faster. Maybe not noticeable but worth having. If you were to wrap your code in a function to facilitate reuse I'm sure it'll incur a small performance hit too.

[zeb]

That is really interesting. So as the array gets larger, the sorting functions (uasort/uksort and our cmp) start to slow down. That makes a lot of sense now that I look at it... the only sorting my first method uses is ksort() - which I'm sure all by itself is faster than the custom versions. The other two methods using uasort() and uksort() start having more and more values to compare against each other as the array grows. My first method has a bit of overhead built in because it loops through two arrays with foreach, but that overhead becomes insignificant once the arrays get bigger.

I can actually rewrite my method to be ~50% faster by sorting floats rather than strings. I think that was something that I neglected to emphasize, the groups are all floats, but I had originally stored them as strings (see the very top code box in my first post). In order to keep those values from being converted to integers when I add them to the $sort array as keys, I needed to cast them as strings. So the ksort() function actually ends up sorting the keys as strings (I think, unless PHP converts them to floats before it compares them). Your code already has them created as integers. If I start out by writing the group values without quotes (as floats), and then store these group values as floats in the $sort array and use the same $MENU keys as the keys, then I can shorten my method like so:

$sort = array();  

foreach ( $menu1 as $k => $a )  

    {  

    $sort[ $k ] = $a['group'];
    }  

asort( $sort );  

$menu1 = array_merge( $sort, $menu1 );

I get these averages:

// on my server
0.0004860 // original method
0.0002349 // rewritten method
0.0006693 // uasort()
0.0012040 // uksort()

// on my local development machine
0.0008676 // original method
0.0004644 // rewritten method
0.0019807 // uasort()
0.0028697 // uksort()

Like you said, "Maybe not noticeable but worth having" ... definitely worth having. As I said before, there is soooo much more code being executed: 15000+ lines...