Эффективность группы пикселей в пикселях PHP

Question

В настоящее время у меня есть карта 1600 x 1600, хранящаяся в MySQL (2,560,000 записей). Я даю простой 25x25-карту пользователям для взаимодействия. Пользователи могут «требовать» плитки на этой карте. Я хотел бы иметь возможность рассчитать количество открытых граней для плиток, принадлежащих данному пользователю. Я могу разделить это на общую плиту, чтобы определить произвольный рейтинг эффективности.

Все координаты карты просто сохраняются как значения 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 очков, это довольно тяжелое бремя.

Любая помощь очень ценится.

Answer 1

Вот последний блок простого кода, который я придумал, чтобы определить эффективность геометрии. Некоторые названия вещей были изменены. : P

Я работаю с уведомлениями, и все это ajax, поэтому я решил пойти с одиночными проверками на многомерном, а не на другом.

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

Answer 2

Один подход предполагает создание класса 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 

Тогда, наконец, представить a COUNT запрос для «соседних» точек, чтобы определить, сколько из них занято другими пользователями и удалить их из общей суммы.

(Примечание:. Я добавил Todos, где больше работы должно быть сделано)

---

Присущая проблема этого метода состоит в том, что, как группа растет, это займет больше времени и дольше вычислить.

Вам следует рассмотреть возможность использования хранилища ключей в памяти, например Redis. Но да, время поиска (для занятых блоков), во временной сложности, кажется линейным относительно количества записей.