Разворот односвязного списка. Swift Edition

[Dasdy]

Было бы также интересно попробовать решить задачу с хвостовой рекурсией, и сравнить с двумя приведёнными вариантами. Я не сильно знаком со Swift, но, поскольку он основан на LLVM, ожидал бы, что TCO поддерживается. Также это должно решить проблему с недостатком ресурсов компьютера.

[Zuy]

Поэтому о константной сложности по выделяемой памяти для рекурсивного алгоритма речь уже не идет.

А разве она когда-то вообще шла о константной сложности по выделению памяти для рекурсивных алгоритмов? По-моему ваше первое утверждение, где вы пишете, что оба алгоритма имеют сложность по памяти О(1) абсолютно неверно. Может стоит сразу написать про эту особенность? А то вдруг ктото дочитает только до половины статьи и так и запомнит, что оба алгоритма одинаковы по потреблению памяти.

[hummingbirddj]

Согласен, подредактировал! Спасибо!

[V1tol]

У меня с вашим кодом для размерности 10000 получились следующие цифры:

Reverse took 0.000501788999827113 seconds
Recursive took 0.0005243940013315296 seconds

Компилировал из коммандной строки:

swiftc -Ounchecked linkedlist.swift

Между -Ounchecked и -O разница в пределах погрешности.

P.S. А вы пробовали использовать indirect enums? Мне кажется, как раз то что нужно для реализации связанного списка.

[hummingbirddj]

Не пробовал, честно говоря! Потому что сам не додумался. Но натыкался на такой подход: medium.com/@rgcottrell/how-to-reverse-a-linked-list-in-swift-c60112aa848f
Выглядит, по крайней мере, любопытно!

[V1tol]

Прогнал сейчас код на базе indirect enums из вышеприведённой статьи, на 10000 элементов получилось так:

Reverse took 0.0016365060000680387 seconds

У меня получилось медленнее в 3 раза, скорее всего из-за постоянного создания новых енамов. Хотя енамы должны быть дешевле с точки зрения памяти.

[omaksim]

При чем здесь вообще Swift?