kb
16.10.2012 09:09 04a3831c
То ли я чего-то не понимаю, но почему всякие хаскели и скалы пишут квиксорт примерно таким образом?
def sortList(list: List[Int]): List[Int] = list match {
case Nil => Nil
case head :: tail => sortList(tail.filter(_ < head)) ::: head :: sortList(tail.filter(_ >= head))
}
В смысле, разве этот .filter() будет проходить не два раза по одному и тому же списку? Разве не правильнее сделать какой-нибудь split, возвращающий тупл из элементов "больше" и "меньше", и тут уже правильно их распихать?
Ну и вообще надо бы поисследовать что еще там такого, что тормозит https://jazzy.id.au/default/2012/10/16/b...
28 comments
recommend
bookmark
subscribe
будет два раза, да. Да и вообще, это не quicksort, так как quicksort — конкретный алгоритм, определённый на массивах с доступом к элементу за O(1). А не эта срань.
и да, под "split" я имел в виду Data.List.span (в случае с х-лем)
а я вот не знаю, где там доступ к элементу на O(1) нужен, кроме первоначального выбора pivot'а (который здесь тоже хитро берется тупо первым).
а собственно перестановка элементов относительно пивота?
да, что-то я тупой сейчас.
так квиксорт пишут исключительно для захвата внимания человека, открывшего страничку почитать наискосок. всем же приятно написать квиксорт в одну строчку. вот и хуярят этот стандартный пример. но если у автора есть хоть немного совести (как у Joe Armstrong'а) то на следующих десяти страницах он объясняет, что приведённый пример говно и рассказывает как это надо делать правильно.
ну просто в данном случае автор вообще искажает аргументы, говоря, что "вот это — идиоматическая скала, и посмотрите какая она говно". а я считаю, что если уж уступаешь алгоритмической сложностью в пользу читаемости кода, то это уже совершенно другой код, и мерять их по скорости просто тупо (ну, разве что чисто из интереса).
не могу не запостить сюда:
ну, кстати, если серьезно — то нужно взять и уеб^^^ переписать (чтоб по честному) так, чтоб состояние (а именно, весь массив) передавалось в виде хвостовой рекурсии. что в лиспах, что в х-лях всяких. но получится такое нечитаемое говно что аж страшно представить (вместе с счетчиком "перестановки" и т.п.).
p.s.: надо будет попробовать, что ли.
чего только люди не «пробуют», лишь бы на плюсах не писать
на плюсах писать пробовал. как-нибудь еще попробую обязательно.
но это ведь не будет так же весело, а другой цели у меня особо и нету.
на плюсах писать не весело? да ты метапрограмминг, похоже, не осилил. там же функциональщина чистой воды
Поддвачиваю этого баттхертворка.
только рекомендую тщательно делить код на "весело" и "для реального использования". quicksort на списках — это может и весело (хотя, как по мне, так печально), но в реальное использование не рекомендую.
MPL-страпончика всей компашке
нет, ну можно и на массивах (хаскельных или других). вопрос только в том, как, убеждать компилятор / интерпретатор в том, что "я сейчас разберу и соберу массивчик, а ты на самом деле только два элемента местами поменяй. ок?".
зачем если есть функциональщина? впрочем, глупый спор.
> глупый спор
> psto.net
Тому, кто никогда не пердолился в Boost.MPL, Spirit и прочих няшек, не понять.
о да, детка. компилируй меня полностью
У меня есть некоторые сомнения относительно того, что няшкой можно считать такие, пусть и гениальные, но ОЧЕНЬ вербозные штуки.
Boost.MPL норм. не очень-то и вербозно
Хуле тут вербозного? https://github.com/0xd34df00d/leechcraft...
Я больше к спириту претенизю предъявляю.
На тех же литералах из С++11, наверное, было бы лаконичней реализовано.
нет, всё же, не понял. перестановка там только в случае "in place" варианта делается. в остальных же строятся новые списки / массивы.
ну вот, остальные варианты и не являются quicksort.