Pull to refresh

Comments 21

Если я правильно понял, вы рекурсивно выделяете N памяти? Не надо так, особенно, с тегом новичкам. Переучиваться всегда сложнее.

Кажется, это статья из цикла "сейчас я буду объяснять алгоритм, пока не пойму его".

ЗЫ: Выделяет, кажется, в общей сложности 2N (для вложенных уровней рекурсии массивы короче). Непривычно, обычно сортировки делают in-place (если это не махровая функциональщина)

В том-то и дело, что N*lnN памяти. Линейно бы ещё куда ни шло, ведь классический merge тоже подразумевает копию массива.

Да не, O(N). Прикиньте момент, когда рекурсия дошла до дна: на самом верхнем уровне (сортируем массив длиной N) выделено два массива по N/2, уровнем ниже (сортируем массив длиной N/2) два по N/4 и так далее. В сумме 2N.

Тут больше доставляет, что будет проделано O(N) выделений из кучи. Сама сортировка, мне кажется, за этим потеряется.

уровнем ниже (сортируем массив длиной N/2) два по N/4 и так далее
но уровнем ниже нам нужно отсортировать ДВА массива по N/2, то есть выделяем 4 по N/4. Разве нет?

Вызовы для правой и левой части происходят последовательно. Т.е. к моменту возврата для одной из частей – вся её цепочка выделений (фу, гадость-то какая) уже схлопнется, память (кроме return value) может быть освобождена.

Спасибо за замечание. Полностью согласен с тем, что с точки зрения использования памяти данное решение неэффективно.

Память, в конце-концов, относительно дешёвая. Как там с быстродействием? Количеством выполненных операций(нагрузка на процессор)? диапазон этих показателей для наилучшего/наихудшего варианта.

А зачем тут вообще память то выделять?

Меняем объекты списка сначала в парах, потом в четверках, и. т д. И лучше в цикле, а не рекурсией, ибо рекурсия и стек жрет, и время на вызовы-возвраты.

Если хочется ускорить процесс, то создаем буфер и индексами, или указателями на обьекты и сортируем его. Тогда экономим время на многократном свапе объектов.

В парах можно. А вот в четвёрках и дальше у вас поменять уже без дополнительной памяти не получится. Там может оказаться надо переместить 2/3 правого массива в начало, а левый и оставшуюся 1/3 правого склеить вперемешку. Тогда непонятно, куда деть первые 2/3 левого массива так, чтобы это было быстро, не рушило порядок элементов в нём, и элементы можно было отличить от оставшихся элементов правого массива.

Иногда доступна ТОЛЬКО РЕКУРСИЯ, в функциональных языках, к примеру. Выполняя сортировку в цикле сложно будет её распараллелить в случае огромных объёмов, а совершая сортировку рекурсией, в принципе это не сложно. Все эти кажущиеся странные алгоритмы предназначены для функционального программирования, а там своя специфика и свои преимущества. Несмотря на избыточность по потреблению памяти, алгоритм этот будет гораздо легче распараллелить или сделать его на каком-то поточном процессоре будущего, который одновременно может исполнять разные стадии сортировки, в отличие от типичного процессора, который в каждый момент времени работает только с одним элементом. И тут становится актуальным именно копирование данных, хоть оно и приводит к дублированию, но зачастую копирование без возможности последующей модификации(возврат значения в те же ячейки) очень ускоряет работу кеша процессора(нет необходимости синхронизировать кеш между ядрами, выгружать кеш-линию обратно в RAM и т.д.), в итоге растёт производительность в целом и очень значительно.

Не вижу принципиальной разницы для распараллеливания, цикл, или рекурсия. И даже наоборот. Переписывая алгоритм на vhdl мне намного проще работать с циклами, чем с рекурсией.

И независимо от языка рекурсия более ресурсоемка. Просто оно прячется под капот.

У рекурсии один несомненный плюс. Краткость записи и простота понимания.

В привычных нам языках программирования это так и есть - рекурсия более ресурсоёмка, но в функциональном - рекурсия это единственный способ, нет там циклов в принципе. Краткость записи - это далеко не плюс, и простоты понимания там тоже нет, напротив понять рекурсию довольно сложная задача т.к. требует задействования пространственного мышления. Это больше похоже на фокус, в котором мало движений но очень сложно понять и научиться его правильно выполнять.
Кстати, цикл на функциональном языке весьма ресурсоёмкая операция.

Да, я ошибся. Простым способом попарным обменом не обойтись. Нужен еще буфер размером с исходный.

левая половина от 0 до длина/2

А если длина будет нечетным числом?

Полагаю тут забыли округлить.

Выражение длина/2 округлится автоматически в меньшую сторону, поскольку на вход в метод подаётся тип данных int, который представляет собой целочисленное значение. Размер массива, как и индексы его элементов, не могут быть дробными.

делал такую сортировку без рекурсии и буфера, по скорости страдает конечно, так как много проверок, но памяти требуется только sizeof(src[x]) для обмена.

а анимацию "Сортировка слиянием" вы сами делали или с просторов сети?

Да, обычным циклом будет экономнее. Я преследовал цель использовать рекурсию, поэтому без жертв не обошлось.

Гифки нашел в сети.

Если говорим об экономии, то экономия в чём? В тактах процессора очень врятли. Давненько уже до многих дошло прозрение что read-only участки памяти работают быстрее в целом, т.к. находятся исключительно в кеше ядра процессора и никуда больше не синхронизируются, что очень важно для многопоточных алгоритмов. Если вдруг другой процесс захочет прочитать ячейку которая могла изменится, он будет ждать пока кеш-линия будет выгружена из кеша в RAM, потом обратно в кеш того ядра где выполняется процесс... это очень огромные накладные расходы.

Экономнее с точки зрения расхода памяти.
Прочитал ваши комментарии с большим удовольствием, спасибо!

Sign up to leave a comment.

Articles