Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Спасибо за статью.
Ссылочная прозрачность же, а не мемоизация?
Было бы интересно ещё про Fusion (как несколько map/filter/… выливаются в один цикл). Это, так сказать, обратный случай, где в обычных языках мы платим, а в ленивом — нет, за счёт высокой абстракции.
Ссылочная прозрачность же, а не мемоизация?
Было бы интересно ещё про Fusion (как несколько map/filter/… выливаются в один цикл). Это, так сказать, обратный случай, где в обычных языках мы платим, а в ленивом — нет, за счёт высокой абстракции.
Всегда пожалуйста.
Я, если честно, не сильно разбираюсь в переводах терминов на русский, и возможны некоторые неточности. В англоязычной литературе я встречал и понятие sharing, и memoization, скорее всего я просто не понял разницы между ними.
А что насчёт Fusion, как я понимаю, это весьма редкая техника оптимизации, которую даже нужно отдельно включать. Может быть я поковыряю её на досуге и отпишусь о результатах.
Я, если честно, не сильно разбираюсь в переводах терминов на русский, и возможны некоторые неточности. В англоязычной литературе я встречал и понятие sharing, и memoization, скорее всего я просто не понял разницы между ними.
А что насчёт Fusion, как я понимаю, это весьма редкая техника оптимизации, которую даже нужно отдельно включать. Может быть я поковыряю её на досуге и отпишусь о результатах.
«Но в строгом языке это расточительно, так как придётся отсортировать весь список. Но с ленивыми вычислениями, мы отсортируем список до третьего элемента и остановимся,»
Как это вы сортируете список «до 3 элемента»?
Чтобы найти эти элементы все равно весь список придется просмотреть.
Как это вы сортируете список «до 3 элемента»?
Чтобы найти эти элементы все равно весь список придется просмотреть.
Ну дак его ж не надо досортировывать до конца.
другими словами хаскел быдет использовать selection sort со сложностью O(n^2) там где все используют O(n log n)?
неприятный сюрприз.
неприятный сюрприз.
Никто этого не говорил.
Ну почему же? Можно, к примеру, сортировать qsort'ом, и при каждом разбиении идти только в меньшую половинку(за исключением случая, когда там мало элементов).
Так у qsort сложность в худшем случае и есть O(n^2).
Но ведь обычно рассматривается средний случай. И тогда уж точно отсортировать только половину будет быстрее, чем весь список.
Хых. Так это всё-равно будет медленней, чем выбрать известное количество K наименьших элементов — у которого сложность O(log(K) N). Когда скорость важна, нужно использовать специальный алгоритм. Беда Haskell в том, что он не позволит прямо выразить такой вот алгоритм, если вообще это возможно, то придётся танцевать с бубном, и в итоге, всё равно, будет медленней. Хых…
Идея того примера была в том, чтобы показать, что в ленивом языке такой подход будет быстрее, чем в строгом. А так то да, специальный алгоритм лучше.
В среднем, алгоритм с qsort'ом будет работать быстрее, т.к. работает за O(N), см. мой комментарий ниже.
Вы, вероятно, упоминаете интуитивный алгоритм в 1 пробег с чем-то вроде стека в руках. Я давно не писал на хаскеле, но вот — то, что пишется за пару минут(извините за некоторую корявость):
И это работает медленнее, чем take и самописный qsort(а также медленнее, чем take и встроенный sort из Data.List).
Вы, вероятно, упоминаете интуитивный алгоритм в 1 пробег с чем-то вроде стека в руках. Я давно не писал на хаскеле, но вот — то, что пишется за пару минут(извините за некоторую корявость):
sink a (r1:rs) | r1 > a = r1:(sink a rs)
sink a l = a:l
kmin k len r (a:l) = kmin k len1 r1 l
where
r1 = if len<k then sink a r
else drop 1 $ sink a r
len1 = if len<k then len+1 else len
kmin _ _ r _ = r
mink k l = reverse $ kmin k 0 [] l
И это работает медленнее, чем take и самописный qsort(а также медленнее, чем take и встроенный sort из Data.List).
Ну давайте прикинем сложность этого алгоритма. В среднем, мы на каждой итерации будем брать половину списка до тех пор, пока там не станет k элементов, после чего просто выдадим их.
Итого мы сделаем операций: N + N/2 + N/4 +..+k, что не превосходит 2N, так что асимптотическая сложность — O(N).
Разумеется, все мои рассуждения не точны, но, думаю, суть ясна. Да, есть худший случай, где оно работает примерно за O(N^2-k^2), но это беда qsort'а. В среднем время работы линейно.
Итого мы сделаем операций: N + N/2 + N/4 +..+k, что не превосходит 2N, так что асимптотическая сложность — O(N).
Разумеется, все мои рассуждения не точны, но, думаю, суть ясна. Да, есть худший случай, где оно работает примерно за O(N^2-k^2), но это беда qsort'а. В среднем время работы линейно.
«и при каждом разбиении идти только в меньшую половинку»
Половинку? При qsort нет половинок. Там берется опорный элемент и остальные элементы располагаются левее-правее относительно этого элемента. То есть попась в случай, когда опорный элемент оказался в хвосте — очень даже вероятно.
Разумеется, для определенной части данных можно избежать сортировки — но говорить «отсортируем до 3 элемента» — это просто вводить в заблуждение. В подавляющем большинстве случаев будет массовая и затратная операция над данными.
Половинку? При qsort нет половинок. Там берется опорный элемент и остальные элементы располагаются левее-правее относительно этого элемента. То есть попась в случай, когда опорный элемент оказался в хвосте — очень даже вероятно.
Разумеется, для определенной части данных можно избежать сортировки — но говорить «отсортируем до 3 элемента» — это просто вводить в заблуждение. В подавляющем большинстве случаев будет массовая и затратная операция над данными.
То есть попась в случай, когда опорный элемент оказался в хвосте — очень даже вероятно.
Столь же вероятно, сколь и попасть в случай, когда «опорный элемент» окажется в начале. Итого в среднем он оказывается в середине списка, т.е. делит список на «половинки».
Прочитайте мой комментарий выше, там нестрого, на пальцах пояснено, почему алгоритм будет работать за O(N).
В подавляющем большинстве случаев будет массовая и затратная операция над данными.
В каком, простите, подавляющем большинстве? Что есть массовая и затратная операция? В среднем такой алгоритм будет работать за O(N). Вы случайно не считаете, что «в подавляющем большинстве случаев» qsort работает за O(N^2)?
А Вы что, считаете что o(n) это мало?
А вы можете найти k наименьших элементов в массиве/списке менее, чем за O(N)? То есть не проходя весь массив/список?
если представить программиста, который пишет, ну… скажен на С или на go, он напишет просто один цикл по списку и выберет все три значения за 1 проход. За O(N) при любых данных.
А подход take 3 sort список, выберет то же самое за O(N) (если вы конечно правильно отгадали как именно действует haskell) в среднестатистическом случае. А в случае «плохих» данных результат будет хуже.
То есть как раз и весь разговор о том, что автор выбрал неудачный пример для демонстрации преимуществ. Если бы он просто написал take 3 [какая то тяжелая обработка x | x < — список], вопросов бы не возникло.
Но вариант take 3 sort список — пример провокационный и рождающий больше вопросов, чем дающий ответы.
А подход take 3 sort список, выберет то же самое за O(N) (если вы конечно правильно отгадали как именно действует haskell) в среднестатистическом случае. А в случае «плохих» данных результат будет хуже.
То есть как раз и весь разговор о том, что автор выбрал неудачный пример для демонстрации преимуществ. Если бы он просто написал take 3 [какая то тяжелая обработка x | x < — список], вопросов бы не возникло.
Но вариант take 3 sort список — пример провокационный и рождающий больше вопросов, чем дающий ответы.
Как я уже говорил, тот пример должен был показать, что из за ленивости Хаскеля, остальная часть списка не будет сортироваться, а в строгом языке будет. В этом и была демонстрация преимуществ.
В haskell'е вам тоже никто не запрещает пройти циклом по списку и подсчитать все, что нужно. Фишка в том, что можно написать нечто в среднем то же самое(и даже немного быстрее) в одну строчку. Более того, я не знаю, как работает стандартная сортировка (sort из Data.List), но на моем нетбуке она немного обгоняет как пробег по массиву, так и qsort(в плохих случаях).
Вообще пример с qsort я привел как самый очевидный, наверняка что-то подобное можно сделать и, к примеру, с mergesort.
Пока гипотетический C/go программист писал свой пробег по циклу, его товарищ написал на haskell'e одну строку и оставшиеся две минуты неспешно пил горячий кофе, с легкой усмешкой поглядывая на соседа.
Вообще пример с qsort я привел как самый очевидный, наверняка что-то подобное можно сделать и, к примеру, с mergesort.
Пока гипотетический C/go программист писал свой пробег по циклу, его товарищ написал на haskell'e одну строку и оставшиеся две минуты неспешно пил горячий кофе, с легкой усмешкой поглядывая на соседа.
Дабы было проще понять:
head $ sort lst
Выдаст минимальный элемент.
Сравните, во что это выльется ленивому и энергичному языку?
head $ sort lst
Выдаст минимальный элемент.
Сравните, во что это выльется ленивому и энергичному языку?
Так если мне нужно будет наименьший элемент, то я на энергичном языке напишу какой-нибудь minlist с оптимизацией под AVX и OpenCL, и всё.
А если мне не нужна будет скорость, буду писать в Bash: cat list | sort | head. Кстати, будет то же самое по способу вычисления. При этом, всё энергично, просто семантика у операций несколько другая.
А если мне не нужна будет скорость, буду писать в Bash: cat list | sort | head. Кстати, будет то же самое по способу вычисления. При этом, всё энергично, просто семантика у операций несколько другая.
Если бы всё было так просто, не было бы таких понятий, как итератор.
А всё действительно именно так просто. Но так же просто и то, что люди склонны к усложнениям, даже когда в этом нет необходимости: потому что итератор — это круто, а правильно организованные данные и простой цикл — нет, не звучит :) К сожалению именно так. Огромное количество сложного софта написано без всяких итераторов и всё прекрасно работает.
Итераторы нужны не для усложнения, а для разделения алгоритмов.
Куда как проще и понятнее написать:
filterData = filter somePredicate
translateData = map someOp
И затем
filterData. translateData $ data
и всё это выльется в один цикл.
Нежели
for (… )
{
if (somePredicate(*b))
result.push_back(someOp(*b))
}
Так как в первом случае код разнесён в разные места (а что если эти обработки пишут разные люди?), а во втором — всё намешано в кучу.
Мы, конечно, во втором случае тоже можем разнести в разные места, но тогда в энергичном языке у нас получится 2 цикла, а не один. А если обработок будет больше, чем 2? То и циклов будет сотня. Вот и придумывают всякие yield'ы, и отнюдь не ради забавы.
Куда как проще и понятнее написать:
filterData = filter somePredicate
translateData = map someOp
И затем
filterData. translateData $ data
и всё это выльется в один цикл.
Нежели
for (… )
{
if (somePredicate(*b))
result.push_back(someOp(*b))
}
Так как в первом случае код разнесён в разные места (а что если эти обработки пишут разные люди?), а во втором — всё намешано в кучу.
Мы, конечно, во втором случае тоже можем разнести в разные места, но тогда в энергичном языке у нас получится 2 цикла, а не один. А если обработок будет больше, чем 2? То и циклов будет сотня. Вот и придумывают всякие yield'ы, и отнюдь не ради забавы.
Эмс. А что мешает в энергичном языке писать то же самое? Те же самые map (Scheme же call-by-value язык)? И, вероятно, мы с вами под интераторами понимаем разные вещи. Вы имеете в виду итераторы как в Python?
в «неленивом языке» это выльется в min(список). в неленивом языке никто не будет сортировать массив чтобы взять минимум.
В строгом языке это как раз таки и не выльется в min(список), поэтому никто и не будет сортировать его чтобы взять минимум.
Вы не поверите, но в «ленивом» языке тоже никто не будет сортировать весь массив. Отсортируется то, что нужно, остальное останется в стороне.
В неленивых языках поэтому куча абстракций типа итератор и енумератор. Так что на деле не всё так просто.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ленивые вычисления