mysql — PHP Pixel Map Эффективность группы
В настоящее время у меня есть карта 1600 x 1600, хранящаяся в MySQL (2 560 000 записей). Я предоставляю пользователям простую карту 25×25 для взаимодействия. Пользователи могут «претендовать» плитки на этой карте. Я хотел бы иметь возможность рассчитать количество открытых граней для плиток, принадлежащих данному пользователю. Я могу разделить это на общее количество плиток, чтобы определить произвольный рейтинг эффективности.
Все координаты карты просто сохраняются как значения X / Y.
Я ищу что-то, что потенциально может обработать массив указанных значений X / Y и определить, сколько открытых граней доступно для каждой принадлежащей группы. Например…
0 = player
x x x x x
x x 0 x x
x x x x x
4 open faces
x x x x x
x x 0 x x
x x 0 x x
x x x x x
6 open faces
x x x x x
x x x 0 x
x x 0 x x
x x x x x
8 open faces
Прямо сейчас я делаю некоторые неэффективные циклы массива, чтобы вычислить это. У меня есть простой счетчик, затем я перебираю массив всех значений и ищу значения + -1 в каждом направлении X и Y, чтобы уменьшить количество. Каждый цикл добавляет 0-4 к общему счетчику в зависимости от количества находок. Неотъемлемая проблема этого метода заключается в том, что по мере роста группы вычисление займет все больше времени. Поскольку одна группа может потреблять 20 000 баллов больше, это довольно обременительно.
Любая помощь с благодарностью.
Решение
Один подход будет включать создание Point учебный класс. Например:
class Point {
public $x;
public $y;
public function __construct($x, $y){
$this->x = $x;
$this->y = $y;
}
public function getNeighbors(){
// TODO: What if we are at the edge of the board?
return array(
new Point($x+1, $y+1),
new Point($x+1, $y-1),
new Point($x-1, $y+1),
new Point($x-1, $y-1),
);
}
}
Создайте экземпляры из этого класса для каждой точки, занятой пользователем:
// Generate array of Points from database
$user_points = array(new Point(134, 245), new Point(146, 456));
Выполните итерацию, чтобы сгенерировать всех соседей:
// Get a flat array of neighbor Points
$neighbors = array_merge(array_map(function($point){
return $point->getNeighbors();
}, $user_points));
// TOOD: Remove Points that are equal to values in $user_points
Затем, наконец, представьте COUNT запросите «соседние» точки, чтобы определить, сколько заняты другими пользователями, и удалить их из общего количества.
(Примечание: я добавил TODO, где нужно проделать больше работы.)
Неотъемлемая проблема этого метода заключается в том, что по мере роста группы вычисление займет все больше времени.
Вы должны рассмотреть возможность использования хранилища ключей в памяти, например Redis. Но да, время поиска (для занятых блоков) по сложности времени кажется линейным по отношению к количеству записей.
Другие решения
Вот последний блок простого кода, который я придумал, чтобы определить геоэффективность. Некоторые названия вещей были изменены. :П
Я работаю с уведомлениями, и все в порядке, поэтому я решил пойти с одиночными проверками isset на многомерном, а не на что-то еще.
$sql = 'SELECT map_x, map_y FROM Map WHERE person_id = :person_id';
$query = $DB->prepare($sql);
$query->execute(array(':nation_id' => $this->person_id));
$counter = 0;
$coords = array();
while($row = $query->fetch())
{
++$counter;
$coords[$row['map_x']][$row['map_y']] = 1;
}
$faces = 0;
foreach($coords as $x => $batch)
{
foreach($batch as $y => $junk)
{
$hits = 4;
if(isset($coords[$x + 1][$y]))
{
--$hits;
}
if(isset($coords[$x - 1][$y]))
{
--$hits;
}
if(isset($coords[$x][$y - 1]))
{
--$hits;
}
if(isset($coords[$x][$y + 1]))
{
--$hits;
}
$faces += $hits;
}
}