Действительно ли «разделяй и властвуй» выигрывает от увеличения выделения памяти?
Я только что закончил кодировать некоторые классические алгоритмы «разделяй и властвуй» и задал следующий вопрос: (больше для любопытства)
Следует признать, что во многих случаях алгоритм «разделяй и властвуй» работает быстрее, чем традиционный алгоритм; например, в быстром преобразовании Фурье он улучшает сложность с N ^ 2 до Nlog2N. Однако благодаря кодированию я обнаружил, что из-за «деления» у нас появляется больше подзадач, что означает, что нам нужно создавать больше контейнеров и выделять больше памяти для подзадачи. Подумайте об этом, в сортировке слиянием мы должны создавать левый и правый массив в каждой рекурсии, а в быстром преобразовании Фурье мы должны создавать нечетные и четные массивы в каждой рекурсии. Это означает, что мы должны выделить больше памяти во время алгоритма.
Итак, мой вопрос в действительности, такой как в C ++, действительно ли выигрывают такие алгоритмы, как «разделяй и властвуй», когда нам также приходится увеличивать сложность в распределении памяти? (Или выделение памяти вообще не займет времени выполнения, а его стоимость равна нулю?)
Спасибо за помощь мне!
Решение
Почти все, что касается оптимизации, является компромиссом между одним ресурсом и другим — в традиционном проектировании это, как правило, «затраты против материала».
В вычислениях компромиссом часто является «время против использования памяти».
Я не думаю, что есть один простой ответ на ваш реальный вопрос — он действительно зависит от алгоритма — и в реальной жизни это может привести к компромиссным решениям, когда проблема делится на более мелкие части, но не ВСЕ, вплоть до минимальный размер, только «до тех пор, пока он не будет более эффективным делить его».
Выделение памяти не является операцией с нулевой стоимостью, если мы говорим о new а также delete, Объем стековой памяти близок к нулю после того, как операционная память заполнена физической памятью стека — для большинства архитектур это не более одной дополнительной инструкции, чтобы освободить место в стеке, и иногда одна дополнительная инструкция при выходе, чтобы вернуть память обратно ,
Реальный ответ, как почти всегда, когда дело доходит до производительности, заключается в сравнении различных решений.
Другие решения
Полезно понимать, что получение «на один уровень лучше» в терминах больших чисел (например, переход от n ^ 2 к n или от n к log n) обычно имеет большое значение. Рассмотрим ваш пример Фурье.
В O(n^2)с n=100 ты смотришь на 10000, и с n=1000 Вы получаете целый миллион, 1000000, С другой стороны, с O(n*log(n)) ты получаешь 664 за n=100 а также 9965 в n=1000, Более медленный рост должен быть очевидным.
Разумеется, выделение памяти стоит ресурсов, как и некоторый другой код, необходимый для разделения и завоевания, например, для объединения частей. Но вся идея в том, что накладные расходы от дополнительных выделений и тому подобное намного, намного меньше, чем дополнительное время, которое потребуется для небольшого алгоритма.
Время дополнительных выделений обычно не является проблемой, но использование памяти может быть само собой. Это один из фундаментальных компромиссов программирования. Вы должны выбрать между скоростью и использованием памяти. Иногда вы можете позволить себе дополнительную память, чтобы получить более быстрые результаты, иногда вы должны сохранить всю память. Это одна из причин, по которой не существует «окончательного алгоритма» для многих задач. Скажем, слияние отлично, работает в O(n * log(n)) даже в худшем случае, но для этого требуется дополнительная память. Если вы не используете версию на месте, которая затем работает медленнее. Или, может быть, вы знаете, что ваши данные, вероятно, уже почти отсортированы, и тогда что-то вроде сглаживания подходит вам лучше.