Сортировать координаты X и Y в массиве в PHP наиболее эффективно?

Question

В настоящее время у меня есть массив, который содержит координаты x и y различных позиций.

ех.

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

Указывает, что id 0 имеет позицию (1,1).

Иногда я хочу отсортировать этот массив по x, а иногда по y.

В настоящее время я использую array_multisort() для сортировки своих данных, но я чувствую, что этот метод неэффективен, поскольку каждый раз перед сортировкой я должен выполнить линейный проход через массив $location только для построения индекса (на x или клавишу y), прежде чем я смогу вызвать команду array_multisort().

Кто-нибудь знает лучший способ сделать это? Может быть, это плохая идея, даже хранить такие данные? Любые предложения будут великолепны.

Answer 1

Вы хотите продолжать использовать мультисортировку.

Я сделал быстрый тест usort и array_multisort. Даже при подсчете только 10 мультисортов построение индекса происходит быстрее, чем usort. На 100 элементах это примерно в 5 раз быстрее. Приблизительно в 1000 элементах улучшения улучшаются прямо на порядок быстрее. Вызовы пользовательских функций слишком медленные. Я бегу 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 не имеет функции array_pluck, такой как ruby. После этого вы можете заменить этот код

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

с

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

Answer 2

Вы можете использовать usort () , который позволяет вам выбирать, как сравнивать элементы массива.

// 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 3

Что-то вроде того, что сказал Джинасио. С помощью этого класса вы можете хранить и сортировать все виды данных, а не только места в разных измерениях. При необходимости вы можете реализовать другие методы, такие как удаление и т. Д.

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;
    }
}

данные испытаний:

$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

сохраняя имеющиеся у вас массивы и мультисортировку, изменяя структуру на что-то вроде следующего, вы исключите необходимость в предыдущем проходе:

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

, тогда просто используйте array_multisort () для всех столбцов.