Sorting x and y coordinates in an array in PHP most efficently?

Question

Currently I have an array that contains x and y coordinates of various positions.

ex. $location[0]['x'] = 1; $location[0]['y'] = 1

This indicates id 0 has a position of (1,1).

Sometimes I want to sort this array by x, and other times by y.

Currently I am using array-multisort() to sort my data, but I feel this method is inefficient since every time before I sort, I must make a linear pass through the $location array just to build the index (on the x or y key) before I can invoke the array-multisort() command.

Does anyone know a better way to do this? Perhaps it is a bad idea even to store the data like this? Any suggestions would be great.

Answer 1

You could use usort() which lets you choose how your array elements are compared.

// sort by 'y'
usort($location, 'cmp_location_y');

// or sort by 'x'
usort($location, 'cmp_location_x');

// here are the comparison functions
function cmp_location_x($a, $b) {
    return cmp_location($a, $b, 'x');
}

function cmp_location_y($a, $b) {
    return cmp_location($a, $b, 'y');
}

function cmp_location($a, $b, $key) {
    if ($a[$key] == $b[$key]) {
     return 0;
    } else if ($a[$key] < $b[$key]) {
     return -1;
    } else {
     return 1;
    }
}

Answer 2

keeping the arrays and the multisort you have, changing the structure to something like the following would eliminate the need for a previous pass:

$locations = array( 
    'x' => $x_coordinates,
    'y' => $y_coordinates,
    'data' => $data_array
);

then just use the array_multisort() on all columns.

Answer 3

Something like what jcinacio said. With this class you can store and sort all sorts of data really, not just locations in different dimensions. You can implement other methods like remove etc as needed.

class Locations {
    public $locations = array();
    public $data = array();
    public $dimensions = 2;

    public function __construct($dimensions = null)
    {
     if (is_int($dimensions))
      $this->dimensions = $dimensions;
    }

    public function addLocation()
    {
     $t = func_num_args();

     if ($t !== $this->dimensions)
      throw new Exception("This Locations object has {$this->dimensions} dimensions");

     $args = func_get_args();

     for ($i = 0; $i < $t; $i++)
      $this->locations[$i][] = $args[$i];

     return $this;
    }

    public function sortByDimension($dimension = 1) 
    {
     if ($dimension > $this->dimensions)
      throw new Exception("Wrong number of dimensions");

     --$dimension;

     $params[] = &$this->locations[$dimension];

     for ($i = 0, $t = $this->dimensions; $i < $t; $i++) {
      if ($i === $dimension)
       continue;

      $params[] = &$this->locations[$i];
     }

     call_user_func_array('array_multisort', $params);

     return $this;
    }
}

test data:

$loc = new Locations(3);

$loc
    ->addLocation(1, 1, 'A')
    ->addLocation(2, 3, 'B')
    ->addLocation(4, 2, 'C')
    ->addLocation(3, 2, 'D')
;
$loc->sortByDimension(1);
var_dump($loc->locations);
$loc->sortByDimension(2);
var_dump($loc->locations);

Answer 4

You want to keep using multisort.

I made a quick benchmark of usort and array_multisort. Even at a count of only 10 multisort with building an index is faster than usort. At 100 elements it's about 5 times faster. At around 1000 elements improvement levels off right at a magnitude faster. User function calls are just too slow. I'm running 5.2.6

$count = 100;

for ($i = 0; $i < $count; $i++)
{
  $temp = array('x' => rand(), 'y' => rand());
  $data[] = $temp; 
  $data2[] = $temp; 
}

function sortByX($a, $b) { return ($a['x'] > $b['x']); }

$start = microtime(true);
usort($data, "sortByX");
echo (microtime(true) - $start) * 1000000, "<br/>\n";

$start = microtime(true);
foreach ($data2 as $temp)
  $s[] = $temp['x'];
array_multisort($s, SORT_NUMERIC, $data2);
echo (microtime(true) - $start) * 1000000, "<br/>\n";

PHP currently doesn't have an array_pluck function like ruby. Once it does you can replace this code

foreach ($data2 as $temp)
    $s[] = $temp['x'];`

with

$s = array_pluck('x', $data2);