Как упростить алгоритм заполнения одномерного массива?

Question

[Almaz_Ilyasov]

Здравствуйте, помогите, пожалуйста, попроще решить одну задачку, может, я что-то пропустил.

Имеется пустой одномерный массив.

Необходимо при заполнении ячейки массива (a) убедиться, что из ближайших к нему n ячеек заполнено не более m.

Банальнее всего пройтись циклом:

$result = true;
for($i=$a-$n;$i<=$a+n;$i++)
{
 $c = 0;
 for($j=$i;$j<=$i+n;$j++)
 {
  if($arr[$j]==true)
  {
   $c++;
  }
 }
 if($c>$m)
 {
  $result = false;
  return $result;
 }
}

Есть идеи, как упростить алгоритм?
Может, вообще php заранее решил проблему, и есть готовая функция?

Comments

[Almaz_Ilyasov]

Вообще исходная задача: не допустить запись на занятия чаще чем 4 раза в 10 дней.

Answer 1

[Vampiro]

Вы правы, эту задачу действительно уже давно упростили:
хранят расписание в базе данных, а количество занятий узнают запросом вида

select count(id) as 'ok' from tableName where `owner`=:ownerId and (`date` between :lowDate and :hiDate)

Comments

[Vampiro]

и, кстати, в вашем алгоритме $result и $arr выглядят белыми воронами. Не думали их заменить на $r и $a?

[Almaz_Ilyasov]

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

[Vampiro]

Алгоритм - нет. Скорость - да.

Answer 2

[demolishka]

Заведите второй массив, в котором, при записи на k-ый день, прибавляйте единичку на отрезке [k-n;k+n]. Теперь ваша задача свелась к проверке того, что значение в k-ой ячейке второго массива не больше m-1. Осталось научиться быстро прибавлять на отрезке и запрашивать значение k-го элемента.
Один из вариантов - дерево отрезков. Умеет выполнять операции прибавления на отрезке и запроса суммы на отрезке за O(log(n)).

И да, для вашей исходной, а не обобщенной, задачи реализация моего решения не прибавит скорости.

Comments

[Almaz_Ilyasov]

Интересный вариант, но для исходной задачи и правда не подойдет

Answer 3

[Snewer]

Ваш код достаточно производителен

Comments

[Сергей Протько]

@Snewer я думаю автор имел в виду не производительность, а читаемость.

[Almaz_Ilyasov]

не, я именно про производительность

[Snewer]

@Fesor читаемость когда?) Думаю это лишнее