Комментарии 8
Было бы также интересно попробовать решить задачу с хвостовой рекурсией, и сравнить с двумя приведёнными вариантами. Я не сильно знаком со Swift, но, поскольку он основан на LLVM, ожидал бы, что TCO поддерживается. Также это должно решить проблему с недостатком ресурсов компьютера.
Поэтому о константной сложности по выделяемой памяти для рекурсивного алгоритма речь уже не идет.
А разве она когда-то вообще шла о константной сложности по выделению памяти для рекурсивных алгоритмов? По-моему ваше первое утверждение, где вы пишете, что оба алгоритма имеют сложность по памяти О(1) абсолютно неверно. Может стоит сразу написать про эту особенность? А то вдруг ктото дочитает только до половины статьи и так и запомнит, что оба алгоритма одинаковы по потреблению памяти.
НЛО прилетело и опубликовало эту надпись здесь
У меня с вашим кодом для размерности 10000 получились следующие цифры:
Компилировал из коммандной строки:
Между -Ounchecked и -O разница в пределах погрешности.
P.S. А вы пробовали использовать indirect enums? Мне кажется, как раз то что нужно для реализации связанного списка.
Reverse took 0.000501788999827113 seconds
Recursive took 0.0005243940013315296 seconds
Компилировал из коммандной строки:
swiftc -Ounchecked linkedlist.swiftМежду -Ounchecked и -O разница в пределах погрешности.
P.S. А вы пробовали использовать indirect enums? Мне кажется, как раз то что нужно для реализации связанного списка.
Не пробовал, честно говоря! Потому что сам не додумался. Но натыкался на такой подход: medium.com/@rgcottrell/how-to-reverse-a-linked-list-in-swift-c60112aa848f
Выглядит, по крайней мере, любопытно!
Выглядит, по крайней мере, любопытно!
При чем здесь вообще Swift?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разворот односвязного списка. Swift Edition