Page 1 of 1

Cheapest mathmatical mutli-dimensonal array sort cost?

Posted: Thu Nov 06, 2008 12:50 pm
by darkdss
Hi guys, I ran into a problem.
So currently I have an array like this:

Code: Select all

 
$users =    array(array('id'=> 1, 'username' => 'user', 'age' => 42),
        array('id'=> 2, 'username' => 'user', 'age' => 22));

etc.

My goal is to sort this array by age.

Right now I am currently sorting it with array_multisort() which we know is an O(nlogn) algorithm (since all PHP sorting methods are implementations of quicksort).

However before you can use this function I need to run a foreach loop on $users to make an index for the array_multisort() function:

Code: Select all

foreach $users as $key => $row) {
    $user_age[$key]  = $row['age'];
}
 
Running this snip of code gives us a running time O(n).

My question is this. Does this slow down the overall performance? I am shooting for an algorithm that MUST BE an O(nlogn) running time (the worst case O(n^2) from quicksort is ok too) but the current way I have it set up it performs O(nlogn) + O(n).

Any thoughts or how to better approach this?

Thanks for any help :)

Re: Cheapest mathmatical mutli-dimensonal array sort cost?

Posted: Thu Nov 06, 2008 1:08 pm
by darkdss
Or is it since the overall running time is O(n) + O(n log n) the O(n log n) dominates and the overall running time becomes O(n log n) no matter?

Re: Cheapest mathmatical mutli-dimensonal array sort cost?

Posted: Fri Nov 07, 2008 5:59 pm
by josh
darkdss wrote:However before you can use this function I need to run a foreach loop on $users to make an index for the array_multisort() function ... My question is this. Does this slow down the overall performance?
yes

Re: Cheapest mathmatical mutli-dimensonal array sort cost?

Posted: Sat Nov 08, 2008 8:40 am
by Hannes2k
Hi,
don't worry about the performance. Sorting thousands of items won't be a problem and I guess your $users array doesn't have 10 000 or 100 000 items, or?

But you can also use usort() instead of array_multisort:

Code: Select all

 
//Untested
function ageCmp($a, $b)
{
    return ($a['age'] - $b['age']);
}
 
$users = array(array('id'=> 1, 'username' => 'user', 'age' => 42),
         array('id'=> 2, 'username' => 'user', 'age' => 22)); 
 
usort($users, "ageCmp");
foreach ($users as  $value) {
    echo $value['username'].": ".$value['age']."<br>";
}
 
 
But I don't now if this is faster, so you have to test both solutions.