Применение динамического программирования для создания лучших макетов для веб-форм
Программирование веб-форм обычно не связано с рекурсивными алгоритмами или методами оптимизации, но в этой статье мы покажем проблему, с которой мы столкнулись, и то, как нам удалось решить ее с помощью эффективного алгоритма, применяя рекурсию и динамическое программирование: создание красивого формы!
Проблема: создать красивую форму
Давайте поговорим о проблеме. Клиент должен был иметь возможность создавать на экране несколько форм с разными наборами полей. Поскольку количество форм будет все время расти, необходим «создатель форм»: он будет принимать «описание формы» (по сути, список полей в указанном порядке) в качестве входных данных и создавать правильную экранную форму в качестве вывода. . Например, показанный ниже фрагмент формы может быть создан нашей системой.
Однако была проблема, дополнительное условие: форма должна была «красиво выглядеть», применяя выравнивание, чтобы получить равные поля. Но (всегда есть но) ширина полей не обязательно была такой, чтобы все строки были заполнены, поэтому вам нужно было разбивать строки и растягивать поля, чтобы добиться желаемого вида.
Если вы знакомы с внутренними деталями системы набора текста TEX, вы, возможно, знаете об алгоритме разбиения строк алгоритм Кнута-Пласса, который решает вопрос красивого разделения абзацев. То, что мы делаем здесь, по сути является той же проблемой (на самом деле мы могли бы основывать нашу логику на упомянутом алгоритме), но мы хотим сосредоточиться на пути к правильному алгоритму.
Чтобы лучше понять проблему, давайте представим, что у нас есть пять полей шириной 7, 2, 5, 3 и 6 соответственно, которые должны отображаться в строках шириной 10.
Как мы можем действовать? Некоторые небольшие эксперименты показывают, что вы не можете обойтись менее чем с 3 строками, а 4 или более строк приводят к слишком большому нерациональному использованию пространства. (На самом деле «пустого места» в рядах не будет, так как мы не будем оставлять места вокруг блоков, а сделаем их шире, чтобы они поместились. В любом случае нам нужно знать, сколько свободного места останется на каждую строку, чтобы затем решить, как расширить блоки на ней.)
Итак, как мы можем разместить эти блоки в три ряда? Первая возможность — применить «жадный» алгоритм: разместить как можно больше блоков в строке, прежде чем переходить к новой строке. При таком подходе мы получим следующий макет.
Но это не единственная возможность! Если мы не включим 2-блок в первую строку, а вместо этого переместим его в следующую строку, это приведет к другим альтернативам. Например, мы можем полностью заполнить второй ряд блоками 2, 5 и 3 и получить другой макет.
И еще один макет: вместо заполнения второй строки мы могли бы переместить 3-блок в последнюю строку, и это было бы результатом.
Мы также можем рассмотреть решения с 4 или 5 строками, но они требуют добавления слишком большого количества пустого пространства — хотя ниже мы уточним, что мы подразумеваем под этим.
Какое предпочтительное решение — какое из них следует считать лучшим? Нам нужно установить метрику, чтобы решить, какой макет следует считать оптимальным. Мы должны определить формулу для расчета стоимости строки с точки зрения того, сколько дополнительных отступов мы добавили. Учитывая этот вариант, мы предпочитаем добавлять меньшие пробелы во многих строках, чем добавлять большие пробелы в несколько строк. Итак, давайте определим стоимость строки как добавленное пространство, но в квадрате, и тогда общая стоимость будет суммой стоимости всех строк.
Зачем возводить числа? Представьте, что вам нужно добавить 2 пробела: если вы добавите их все в одну строку, стоимость будет 2²=4, но если вы добавите 1 пробел в две строки, стоимость будет всего 1²+1²= 2. Возведение в квадрат чисел перед их добавлением делает наличие большого количества маленьких чисел предпочтительнее, чем меньшее количество больших. Очевидно, что возведение в квадрат — не единственный возможный способ заставить числа вести себя так, как мы хотим (почему бы не возвести в куб? или возвести в степень?), но это простое решение, которое хорошо работает, так что давайте воспользуемся им.
При таком определении стоимость первого макета будет 1²+2²+4²= 1+4+16= 21, второго — 3²+0²+4²= 9+0+16= 25, а третьего — 3². +3²+1²= 9+9+1= 19. Таким образом, мы считаем, что последнее должно быть результатом нашего алгоритма… но как мы это закодируем? Обратимся к этому.
Решение: алгоритм динамического программирования
Как мы можем найти подходящие разрывы строк для нашей формы? Очень очевидный (и ужасный!) способ сделать это — попробовать все возможные точки разрыва между блоками и посмотреть, какая комбинация выглядит лучше, но количество тестируемых комбинаций растет экспоненциально с количеством блоков, так что этот подход совершенно не подходит. вне вопроса. Мы должны сделать лучше!
Предположим, у нас есть список ширины блоков; в нашем случае [7, 2, 5, 3, 6]. У нас также есть максимальная ширина для каждой строки: MW. Давайте подумаем рекурсивно: как лучше распределить отступы между блоками? Обобщим: если мы хотим оптимально распределить фрагмент блоков с позиции p на позицию q, мы можем использовать приведенную ниже логику — и применяя ее с p, указывающим на первый блок, и q на последний блок, решит нашу первоначальную проблему.
- суммировать ширины всех полей от p до q включительно; назовите эту сумму s
- если s не превышает MW, стоимость этого фрагмента составляет (MW-s)², и больше ничего не нужно делать; мы не можем сделать ничего лучше, разбив фрагмент на две или более строк.
- если s превышает MW, нам нужно добавить несколько разрывов строк… но где? Решение рекурсивное: попробуйте разбить фрагмент на две части всеми возможными способами (первая часть пойдет от p до r, а вторая от r+ от 1 до q) и посмотрите, какое разделение дает наименьшую стоимость; это ваше решение.
Можем ли мы это закодировать? Конечно; в JavaScript подойдет следующее. (Код неполный; например, мы не записываем найденные разрывы и не заполняем поля — давайте просто сосредоточимся на поиске лучших разрывов, что является нашей главной проблемой здесь.) Предположим, что у нас есть totalWidth (x,y), которая вычисляет сумму ширин блоков от x до y.
const costOfFragment = (p, q) => {
const s = totalWidth(p, q);
// fits in single row?
if (s <= MW) return (MW - s) ** 2;
// no fit; try row breaks
let opt = Infinity;
for (let r = p; r < q; r++) {
const newTry = costOfFragment(p, r) + costOfFragment(r + 1, q);
if (newTry < opt) opt = newTry;
}
return opt;
};
Если поля помещаются в одну строку, мы возвращаем стоимость без дальнейших действий. В противном случае мы начинаем пробовать разные разрывы строк, используя r, и вычисляем стоимость возможного разрыва строки в try, рекурсивно вызывая costOfFragment. . Наилучшее (наименьшее) достигнутое значение сохраняется в opt.
Эта логика работает! Давайте посмотрим, как мы обработаем наши пять блоков сверху, чтобы они поместились в ряды шириной 10. Начиная с пяти блоков, нам придется попробовать четыре возможных разделения, поскольку блоки не помещаются в один ряд.
На приведенной выше диаграмме показаны все возможные попытки расщепления; давайте добавим информацию о затратах, чтобы найти лучшее решение. Числа, выделенные красным цветом, — это затраты, рассчитанные в соответствии с нашим определением возведения в квадрат и суммирования.
Напомним правила расчета затрат:
- если у вас нет разделения, to cost — это добавленное пространство в квадрате: например, в левом нижнем углу у вас есть один [5], который стоит 25 (вам нужно добавить 5 пробелов, чтобы получить 10), [ 3,6] стоит 1 (1 добавленное место в квадрате), [5,3] стоит 4 (2 добавленных места в квадрате) и [6] стоит 16 (4 добавленных места в квадрате).
- общая стоимость ряда строк — это просто сумма отдельных разбиений — например, если вы разделите [5,3,6] на две строки с [5] и [3,6], стоимость составит 26 (25 из 5 и 1 из 3+6), и если вы разделите его на [5,3] и [6], стоимость составит 20 (16 плюс 4).
- если у вас есть разделение, стоимость является минимальной стоимостью всех возможных разделений в строках. Например, снова в нижнем левом углу стоимость разделения [5,3,6] равна 20, минимальная стоимость двух возможных разделений с отдельными затратами 26 и 20.
Наша логика дает результат, который мы обсуждали выше, и оптимальное решение для наших пяти блоков стоит 19 и требует трех строк: одна только с 7-блоком, другая с 2- и 5-блоками, и последняя с 3- и 6-блоков. Здорово!
Но…
Оптимизация с помощью динамического программирования
Есть проблема с описанным выше процессом… алгоритм медленный — в основном потому, что он повторяет несколько вычислений снова и снова. Диаграмма ниже показывает это; каждый цветной блок вычисляется более одного раза.
Мы можем добиться большего успеха, применяя Динамическое программирование: метод решения сложной проблемы путем разбиения ее на более простые версии той же задачи, решения которых где-то хранятся, чтобы избежать повторного использования. делать расчеты.
В нашем случае, как мы можем пропустить повторяющиеся вызовы? Очевидно, мы могли бы создать и обновить кеш результатов вручную, но нам это не нужно, потому что мы уже знаем, как решить эту проблему: запоминание! По сути, если вы возьмете функцию и запомните ее, вы получите новую, которая ведет себя точно так же, за исключением того, что она кэширует вычисляемые результаты; если вы вызовете мемоизированную функцию с параметрами, которые вы уже передали ранее, она не будет выполнять никаких вычислений и вместо этого вернет значение из кеша.
Мы уже видели другое использование мемоизации для оптимизации вызовов API; посмотрите мою статью Memoize JavaScript Promises for Performance для этого. Мы разработали собственную функцию запоминания, но вы также можете выбрать очень эффективную библиотеку fast-memoize, помимо других возможностей.
Сколько работы мы бы избежали? На диаграмме ниже показаны улучшенные результаты: все серые блоки не нуждаются в пересчете, и, в частности, стрелки указывают на места, где рекурсия даже не понадобилась, потому что работа уже была проделана.
На диаграмме выше серым цветом отмечены блоки, которые не нужно пересчитывать, потому что необходимая работа уже была проделана ранее и сохранена. Если вы сравните этот рисунок с предыдущими, то заметите, что две части диаграммы (там, где зеленые стрелки) больше не отображаются — это вызовы, которые не понадобились из-за кеширования.
С точки зрения кодирования изменения минимальны.
const costOfFragment = memoize((p: number, q: number) => {
.
. no changes here!
.
});
Это делает это! Оптимизированный алгоритм выполняет минимальную работу и быстро находит хорошее разделение.
Резюме
Мы описали актуальную проблему, возникшую в результате запроса клиента, и то, как нам удалось решить ее оптимизированным способом с применением динамического программирования и мемоизации, чтобы перейти от правильного, но медленного алгоритма к также правильному, но быстрому алгоритму. с минимальными изменениями. Эти же методы можно применять во многих других контекстах для столь же хороших улучшений производительности; все вокруг победы!
