Most efficient way of reordering an array with a known order

I have an array that is given to me in random order. The array is an array of arrays, and I am given an order to place the array in based on a key that exists in each sub-array.

For example, I am given the array array(array('id' => 1), array('id' =>开发者_运维知识库; 2)). I am told to order the arrays in the order (2,1) based upon the key 'id' of each sub-array.

What is the most efficient way to do this in PHP?

PHP does allow you to write your own sort functions. I can't vouch for the efficiency of this solution, but it will work and is supported by the language directly, so I like it.

For your case you would write something like this:

function custom_sort_by_id($a, $b) {
    // If the two IDs are the same, no sorting should be done
    if ($a['id'] == $b['id']) {
     return 0;
    }

    return ($a['id'] < $b['id']) ? -1 : 1;
}

You would then call this function as follows:

usort($myarray, "custom_sort_by_id");

So, if for example you have the following starting array:

array(3) {
  [0]=>
  array(2) {
    ["id"]=>        int(3)
    ["value"]=>     int(1)
  }
  [1]=>
  array(2) {
    ["id"]=>        int(2)
    ["value"]=>     int(2)
  }
  [2]=>
  array(2) {
    ["id"]=>        int(1)
    ["value"]=>     int(3)
  }
}

You'll receive the following result:

array(3) {
  [0]=>
  array(2) {
    ["id"]=>        int(1)
    ["value"]=>     int(3)
  }
  [1]=>
  array(2) {
    ["id"]=>        int(2)
    ["value"]=>     int(2)
  }
  [2]=>
  array(2) {
    ["id"]=>        int(3)
    ["value"]=>     int(1)
  }
}

Efficiency depends a lot on what you would be doing with the data, so this is really hard to answer. The most efficient way would be to recognize that PHP arrays are actually ordered maps, and construct the array with an id key from the very beginning. Also note that regular sort functions won't work if you need to place the array in a random order:

<?php

function add ($needle, &$haystack)
{
    $haystack[$needle['id']] = $needle;
}

$map = array();
add (array('id' => 1), $map);
add (array('id' => 10), $map);
add (array('id' => 100), $map);
add (array('id' => 1000), $map);
add (array('id' => 10000), $map);

$order = array(1,10000,10,1000,100);

foreach ($order as $o)
    print_r ($map[$o]);

well the fastest way would be to create another array of the same size, loop through the random array and place them according to the id.

this is assuming that the id's are in order (aka 1 to however many there are)

if this is not the case, then you will need to loop through them one after another finding the lowest value and either swapping it with another value or move it to another temporary array.

There are other things to consider to, such as, how large the list is, if the list is really large then you could use something like a quick sort, although for smaller lists something like a bubble or insertion sort works just fine.

http://en.wikipedia.org/wiki/Sorting_algorithm

I think the most cpu efficient (although not too memory efficient) way would be to do it in 2 passes:

1. make an associative array with a corresponding key:

   foreach ($array as $item) $ids[$item['id']] = $item;
   

2. construct the result in given order:

   foreach ($order as $id) $result[] = $ids[$id];