![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Clojure, last
По мотивам: http://tonsky.livejournal.com/266027.html
Часто ли нужно найти последний элемент последовательности?
Впрочем, я не очень понимаю, причем тут полиморфизм к оптимизации last для векторов - по-моему, другое имя для метода работающего O(1) для конкретной реализации (вектор) вместо O(n) для произвольных последовательностей - это вполне разумная идея.
Рассуждать об производительности алгоритма гораздо проще, зная, что вызов всегда отрабатывает за известное время, а не "в зависимости от того, что за реализацию мы туда передали".
По-моему, очевидно, что не нужно делать обобщенную реализацию, например quicksort, передавая ей абстракцию "последовательность"+"функция получения n-ного элемента", потому что единственный вариант, в котором это работает - мутабельный массив с O(1) для доступа и замены элемента. Соответственно и алгоритмы, использующие last обобщать и надеятся на оптимальную реализацию в некотором роде бессмысленно.
Часто ли нужно найти последний элемент последовательности?
Впрочем, я не очень понимаю, причем тут полиморфизм к оптимизации last для векторов - по-моему, другое имя для метода работающего O(1) для конкретной реализации (вектор) вместо O(n) для произвольных последовательностей - это вполне разумная идея.
Рассуждать об производительности алгоритма гораздо проще, зная, что вызов всегда отрабатывает за известное время, а не "в зависимости от того, что за реализацию мы туда передали".
По-моему, очевидно, что не нужно делать обобщенную реализацию, например quicksort, передавая ей абстракцию "последовательность"+"функция получения n-ного элемента", потому что единственный вариант, в котором это работает - мутабельный массив с O(1) для доступа и замены элемента. Соответственно и алгоритмы, использующие last обобщать и надеятся на оптимальную реализацию в некотором роде бессмысленно.
no subject
no subject
attoparsec и text -- одни из наиболее скоростных библиотек на хаскеле. Краткость в них принесена в жертву производительности (не думаю, кстати, что можно добиться такой же производительности где бы то ни было с сохранением абстрактных интерфейсов коллекций и итераторов).