TrueElseFalse & Seren
TrueElseFalse TrueElseFalse
Seren Seren
TrueElseFalse TrueElseFalse
Привет, Серафима. Я тут пытаюсь быструю сортировку на мэйнфрейме семидесятых годов запустил – постоянно переполнение стека, если не встроить процедуру разделения. Как думаешь, стоит ли кешировать выбор опорного элемента, чтобы глубину рекурсии контролировать?
Seren Seren
Кажется, типичная головная боль с рекурсией. Мемоизация может помочь, но всё равно упрёшься в лимит стека, если продолжать рекурсировать на больших подмассивах. Попробуй, может, хвостовую рекурсию в цикле или переходи на итеративный алгоритм быстрой сортировки для этих старых машин. Так ты не перегрузишь стек вызовов и не заставишь старый процессор 70-х работать на пределе.
TrueElseFalse TrueElseFalse
Спасибо, попробую версию с итерациями, может, добавлю сторожевой цикл. Старый процессор всё ещё вредничает из-за хвостовой рекурсии, так что оставлю ручной стек и надеюсь, что ничего не взорвётся снова. Спасибо за помощь!
Seren Seren
Рада, что нашёл выход. Следи за размером стека и, может, добавь защиту для стража. Расскажи, как всё сложится.
TrueElseFalse TrueElseFalse
Окей, сделал—добавил сторожевого охранника и ручной стек, который удваивается с каждым проходом. Процессор семидесятых всё ещё ворчит, но, по крайней мере, стек больше не взрывается. Сообщу, если что-нибудь ещё всплывёт.
Seren Seren
Прикольный апгрейд. Удвоение стека защитит от переполнения, но следи за использованием памяти – эти старые процессоры на любом даже незначительном выделении спотыкаются. Если опять вылезет ошибка, можно будет посмотреть вариант с фиксированным блоком или гибрид с сортировкой вставками для маленьких подмассивов. Буду рада помочь, если что-нибудь еще вылезет.