0

На картинке сетка 10х10=100 кубиков.

Создана БД, 100 строк, поля: id,x,y,s. Одна строка = один кубик. x,y - координаты левого верхнего угла кубика. Таким образом перечислены ВСЕ кубики.

В БД хранятся закрашенные области (серый цвет), как несколько строк, у которых поле s=1. координаты левого верхнего угла, т.е. ДВА числа (х,у).

Запросом в БД хочу получить список кубиков данной сетки (они же кубики 1х1, они же строки), которые удовлетворяют условию
1. если под свободным кубиком есть свободный кубик, то я беру оба кубика (т.е. нужны координаты этих обоих кубиков).
2. если свободный кубик имеет справа свободный и под собой свободный и вправо и вниз свободный (т.е. в результате образуется КУБ 2х2), то беру все 4 кубика.
3. Ну и прямоугольники тоже нужны.

Т.е. в итоге для данного рисунка я должен получить:
по 1 условию - id=3,13; id=7,17; id=8,18; id=10,20; id=13,23 и тд. По сути нужен первый результат, дальше отбросить можно.
по 2 условию - id=7,8,17,18; следующий куб 2х2 где-то в центре сетки будет.

Вот так пробовал искать, это искать два свободных (s=0) кубика один под другим, безуспешно:

SELECT t1.id FROM (SELECT * FROM test WHERE s=0 ) t1 WHERE EXISTS
     (SELECT id
      FROM test t2
      WHERE t2.id IN (t1.id + 10, t1.id - 10))

введите сюда описание изображения

поиск кубика 2х2 (левого верхнего угла) по методу sanix (50,60,70,80 не должны светиться зеленым):
введите сюда описание изображения

5
  • 2
    вы издеваетесь? ячеек ведь всего 100шт. сделайте JSON сериализацию, сохранив в БД строку, а когда нужно что-то посчитать - достаньте полностью строку, распарсьте и ищите уже что и как нужно. IMHO нагружать бд для таких случаев - не очень затея.
    – sanix
    29 сен 2016 в 20:48
  • а если 1000х1000? 29 сен 2016 в 20:51
  • 1
    какой максимальный размер? (для 1000x1000 если сериализировать в JSON выйдет около 12мб). Нагружать бд такими операциями, как правило, - плохая затея. А что будет если нужно будет усложнить или изменить задание? .... лучше все это делать уже в бизнес-логике как мне кажется
    – sanix
    29 сен 2016 в 21:00
  • макс 1000х1000. что за бизнес-логика? 29 сен 2016 в 21:06
  • сейчас напишу ответ..)
    – sanix
    29 сен 2016 в 21:21

1 ответ 1

2

Возможно в вашем случае стоило бы и отказаться от такого поиска по базе данных, сделав всю логику поиска в приложении(на любом языке программирования) - это, возможно, будет быстрее на порядок.

UPD: учитывая, что много где вам нужно найти только первое совпадение - то для 1 и 2 случая - быстрее mysql будет все-таки. Для 3-го - в приложении.
Но, если предполагается очень частое изменение данных, то еще не ясно полностью, что быстрее:D

Теперь вернемся к нашей матрице. Раз у вас заранее известны размеры матрицы(NxM), тогда в таблице нет смысла хранить координаты, ведь они высчитываются очень просто, зная ID:
x = (ID % M) - 1;
y = floor(ID/M);

Теперь, насчет поиска:

  1. если под свободным кубиком есть свободный кубик, то я беру оба кубика (т.е. нужны координаты этих обоих кубиков).

Тут алгоритм будет вообще простым: ID кубика под текущим = ID + M;
Значит, нужно искать примерно так: if(ID.s==0 && (ID+M).s==0) ...
Возможно, приведенный ниже вариант запроса SQL не самый быстрый и оптимальный, но рабочий(вместо + 10 должно стоять к-во столбцов в матрице - M):

SELECT t1.id FROM `test` AS t1 WHERE t1.s = 0 AND 
    (SELECT t2.id FROM `test` AS t2 WHERE t2.id = t1.id + 10 AND t2.s = 0)

Важно: ответ приходит как номер верхней угловой ячейки, т.е.: введите сюда описание изображения
Значит в коде, чтобы получить ячейку снизу - нужно взять ID+M.

  1. если свободный кубик имеет справа свободный и под собой свободный и вправо и вниз свободный (т.е. в результате образуется КУБ 2х2), то беру все 4 кубика.

Тут суть алгоритма такая же: проверить текущую ячейку, следующую ID+1, ниже ID+M и по диагонали ID+M+1:

SELECT t1.id FROM `test` AS t1 WHERE t1.s = 0 AND 
(SELECT t2.id FROM `test` AS t2 WHERE t2.id = t1.id + 1 AND t2.s = 0) AND 
(SELECT t2.id FROM `test` AS t2 WHERE t2.id = t1.id + 10 AND t2.s = 0) AND 
(SELECT t2.id FROM `test` AS t2 WHERE t2.id = t1.id + 11 AND t2.s = 0)
AND MOD(t1.id, 10)

Тут также в ответе будет номер верхней угловой, значит нужно будет вычислить остальные ячейки по уже известному алгоритму.

UPD: чтобы не искало крайние правые ячейки 50,60,70,80 - нужно исключить их из поиска. Сделать это довольно легко: AND MOD(t1.id, M) - т.е. эти ячейки не должны быть кратны числу столбцов(10 в данном случае).

  1. Ну и прямоугольники тоже нужны.

Пока не придумал :)

UPD(поиск, другой способ): писать sql-запросы и код я не стану. просто опишу способ. этот способ нужен для поиска больших свободных областей, т.е. если размер больше, скажем, 16 ячеек, то он - в самый раз.

Он состоит из 2 этапов, которые могут повторяться:
1. Берем из бд X id-ников(но чтобы были полные столбцы)
2. Ищем в них нужную область, если находит - все ок, если нет - возвращаемся на шаг 1, но только берем X айдишников со сдвигом X

Пример - найти 6х8(на матрице 1000x200): (брал специально не квадраты) итого вся матрица имеет 200к ячеек. Это много, чтобы за 1 запрос все тащить из БД - возьмем часть, например, 100x200.
В коде, на php, получив это все в массив делаем поиск, но уже более умный, который исключает повторную проверку неподходящих ячеек(можно глянуть ссылку или поискать алгоритм в инете, не стану описывать), в коде проверка будет идти раз в 10 точно быстрее.
Если нашли - то ок, но если нет - запрашиваем новую порцию ячеек и дальше ищем(не забывая совместить области со старыми ячейками) и т.д., пока не найдется, если найдется:D

UPD(как искать в массиве ячейку):
Найти первую свободную ячейку. Потом расширяться по правилу увеличения каждой стороны на 1. Например, ищем 6x6:

  • взяли 1 ячейку
  • прибавили справа или снизу(мы перебираем же сверху вниз и слева вправо) ячейку
  • потом добавили уже 2 ячейку по какой-то стороне
  • потом еще 2
  • потом 3
  • еще 3
  • и т.д... т.е. расширяем сразу всю сторону(НЕ ПО ОДНОЙ ЯЧЕЙКЕ, а сразу всю сторону проверяем, ПОТОМУ-ЧТО ОБЛАСТЬ ПРЯМОУГОЛЬНАЯ)

можно и еще дооптимизировать алгоритм(скажем сначала проверять ячейки по краям прямоугольника, потом проверить диагональ, а потом уже проверять по сторонам, но это не особо сильно ускорит)

Все ячейки, которые проверены и не подходят - можно ставить 1:D

UPD: ссылка на pdf, где описывается как искать такие области.

2
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещен в чат.
    – user177221
    9 окт 2016 в 10:11
  • не соображу, как сделать ,если надо снизу вверх идти (также слева направо) 28 окт 2016 в 21:02

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.