Pull to refresh

Когда память критичнее, чем время

Algorithms *
Tutorial

time: 1h 34 m 13 s  vs  memory: 10 388 MB

Многие задачи, решаемые с помощью динамического программирования, немилосердно относятся к памяти. Часто требуется хранить O(n⋅m) значений, что при больших n и m становится настоящей проблемой. В этой статье я расскажу об относительно общем способе сэкономить память за счёт времени работы.

Определения и обозначения


Пусть есть некоторая задача, которая требует ответа в виде <k, path(k)>, где k — результат, а path(k) — один из возможных способов этот результат достичь. При этом, k зависит от двух множеств A и B с мощностями n и m, и его можно выразить с помощью линейной рекурсии от m и n. Для лучшего понимания стоит обратиться к примеру такой задачи; скажем, задаче о поиске редакционных расстояния и предписания. Почитать о ней можно на Википедии, а посмотреть визуализатор — тут[осторожнее с хабраэффектом]. Далее я расчитываю, что читатель понимает, что происходит.
Очевидно, что наиболее оптимальный по времени способ получить искомое — восходящая динамика по обоим аргументам, хранящая все n⋅m промежуточных значений, и работающая, соответственно, за O(n⋅m) времени. Для пущего удобства положим n = max(m, n) (да, переназначим; иначе я буду постоянно путаться), тогда время работы и объём занимаемой памяти можно оценить как O(n2).

Оказия: память-то конечна!


Чтобы представить, что n может оказаться свыше девяти тысяч, не нужно иметь большой фантазии; как и не нужно быть гением, чтобы догадаться, что затея «отхапать себе несколько десятков гигабайт памяти» заранее обречена на провал. Зато вот времени у нас как правило существенно больше, чем мы с радостью и воспользуемся. К этому моменту читатель должен понимать, что такое восходящая динамика, и с чем её едят, ровно как и осознавать, что такое линейная рекурсия. Хотя, у лентяев есть и другой вариант: верить мне на слово:) Очевидно, что для вычисления очередного значения функции понадобится только константное(чаще всего равное двум) число строк, а это — явный намёк на то, что можно использовать O(n) памяти. Но вместе с тем, если мы храним только фиксированное число строк, то мы рано или поздно будем вынуждены «забыть» старые данные, чтобы вычислить новые. А поскольку на выходе эти старые данные тоже понадобятся, нужно будет считать их снова. Получается простой алгоритм:
  1. Установим iPos = jPos = n;
  2. Вычислим значения функции с (0,0) по (iPos, jPos), при каждом переходе на новую строку удаляя самую старую (таким образом, число строк будет постоянно, обозначим это за k);
  3. Когда дойдём до (iPos, jPos), запомним шаги, которые требуются, чтобы дойти от (iPos — k, k') до (iPos, jPos), где k' — точка, в которую ведёт путь из уже забытой строки
  4. Установим iPos = iPos — k, jPos = k';
  5. Если iPos и jPos не оказались нулями(или меньше), возвращаемся к шагу 2
  6. Значение и путь найдены
Узреть этот алгоритм в действии на примере поиска редакционных расстояния и предписания можно по ссылке, данной выше.
Нетрудно заметить, что алгоритм работает за O(n3), но зато потребляет всего O(n) памяти.

Возможны варианты


Наверняка многие задались вопросом: «А можно ли сделать что-нибудь среднее?» Да, можно. Начнём с O(√n⋅n) памяти и O(√n⋅n2) времени. Собственно, изменения тут будут незначительны: вместо того, чтобы хранить k последних строчек, мы будем хранить √n (для придирчивых: max(k, √n) при маленьких n). Это увеличит потребляюмую память в √n раз, но зато и соответственно уменьшит время: n3/√n = √n⋅n2. Немножко подумав, можно понять, что ∀ε∈[0,1] можно решить задачу, потребляя O(n2+ε) времени и O(n2-ε) памяти. Визуализация для ε = 0.5 доступна в том же визуализаторе.

Послесловие


Работающий пример для задачи о поиске редакционных расстояния и предписания можно найти рядом с визуализатором и на зеркале. Только пожалуйста, не нужно рассказывать мне о Java Coding Conventions, ибо отношения к делу не имеет.
Удачи! :)
Tags:
Hubs:
Total votes 53: ↑49 and ↓4 +45
Views 2.4K
Comments Comments 28