Комментарии 29
Очередная демонизация Хаскеля, аплодирую стоя.
+6
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
> что он предлагает услуги по F#-консалтингу.
Вот на это очень похоже, потому что только из-за слов "Правильное решение оказалось в 10 раз длиннее, чем намного более простое решение на F# и в целых 100 раз длиннее, чем оригинальный изуродованный алгоритм на Хаскеле." можно сделать однозначный вывод, что автор до конца не разбирается в технической реализации Хаскеля, так как от F# он отличается кардинально, общее у них разве что функциональный принцип, с таким же успехом можно сказать что например на Scala это делается ещё проще, что то в этом роде.
Особенно примечательно использование словосочетания «изуродованный алгоритм», так как вышеприведенный код на Хаскеле не читаемый в принципе, ни типов, имена переменных x xcv df sdf lj ahf as;dfh as;kldfh a;sdfj a'sdfj, какой то набор символов. Я вот одного не пойму, вот человек был нормальным писал на императивных языках но как только он взял в руки Хаскель то у него появляется неудержимое желание сделать спагетти совершенно неясного кода, а с переменные превратить в разбросанные куски различных сочетаний двух-трех букв испорченного генератора паролей.
Спрашивается, ну вот почему ты в своем C# так не пишешь? Почему? Ужас какой то. Ну не въехал ты в Хаскель, ничего страшного, занимайся другими языками, но такие статьи похожи на бессильную злобу.
Вот на это очень похоже, потому что только из-за слов "Правильное решение оказалось в 10 раз длиннее, чем намного более простое решение на F# и в целых 100 раз длиннее, чем оригинальный изуродованный алгоритм на Хаскеле." можно сделать однозначный вывод, что автор до конца не разбирается в технической реализации Хаскеля, так как от F# он отличается кардинально, общее у них разве что функциональный принцип, с таким же успехом можно сказать что например на Scala это делается ещё проще, что то в этом роде.
Особенно примечательно использование словосочетания «изуродованный алгоритм», так как вышеприведенный код на Хаскеле не читаемый в принципе, ни типов, имена переменных x xcv df sdf lj ahf as;dfh as;kldfh a;sdfj a'sdfj, какой то набор символов. Я вот одного не пойму, вот человек был нормальным писал на императивных языках но как только он взял в руки Хаскель то у него появляется неудержимое желание сделать спагетти совершенно неясного кода, а с переменные превратить в разбросанные куски различных сочетаний двух-трех букв испорченного генератора паролей.
Спрашивается, ну вот почему ты в своем C# так не пишешь? Почему? Ужас какой то. Ну не въехал ты в Хаскель, ничего страшного, занимайся другими языками, но такие статьи похожи на бессильную злобу.
+1
НЛО прилетело и опубликовало эту надпись здесь
При всём при этом, у меня есть личные конкретные баттхёрты от quality of implementation в случае конкретного ghc — в сколь угодно нетривиальных параллельных программах GC начинает жрать непомерно много времени, потому что GC там хоть и параллельный, но не конкурентный, привет stop-the-world, если даже всего один HEC выжрал свой и соседние allocation area. Но это не свойство языка, впрочем. Либо, не отрицаю, я просто не умею писать многопоточные программы на хаскеле.
Проблема тут не в quality of implementation, а в tradeoff между throughput и latency и предсказуемости того, сколько памяти может отжирать программа на пустом месте. Если важна latency и пофиг на память, то можно идти путём go. Если не важен sharing структур между потоками, то можно делать как Erlang.
В целом ветка non-blocking-gc есть, но те тесты, что были показали, что в большинстве случаев усложнение реализации не окупается. Ну и важно помнить, что до ghc 8.0 очень неудачные RTS опции по умолчанию. Так
+RTS -A254m -qb0 -ki{size-of-l1-cache}
зачастую очень сильно улучшает поведение (после 8.0 -qb0
не нужно, т.к. он выставляется динамически).0
Автор действительно предлагает услуги по F# консалтингу, но его аргументы обычно очень адекватные.
Алгоритм на Хаскеле «изуродованный» (bastardized в оригинале), потому что это не решето Эратосфена, а совсем другой алгоритм. В упомянутой научной статье его называют поэтому кодовым именем «unfaithful sieve». Оказывается, он даже хуже, чем реализация «в лоб» на императивном языке («trial division»). В лоб—это для каждого числа искать все его делители. В статье есть и анализ сложности. У нормального решета Θ(n log log n) (почти линейная, можно сказать). У unfaithful sieve—Θ(n^2/(log n)^2). У решения в лоб—Θ(n^(3/2)/(log n)^2). А на F# можно легко написать нормальный алгоритм, потому что в нем есть изменяемое состояние.
Справедливости ради, весь код (кроме первого из двух строчек) взят из постов и комментов людей, которые пытались реализовать эту параллельную быструю сортировку. В статье есть ссылки, они все до сих пор рабочие. То есть там вообще нет кода автора. А люди эти вроде как апологеты Хаскеля (в отличие от автора, да).
Алгоритм на Хаскеле «изуродованный» (bastardized в оригинале), потому что это не решето Эратосфена, а совсем другой алгоритм. В упомянутой научной статье его называют поэтому кодовым именем «unfaithful sieve». Оказывается, он даже хуже, чем реализация «в лоб» на императивном языке («trial division»). В лоб—это для каждого числа искать все его делители. В статье есть и анализ сложности. У нормального решета Θ(n log log n) (почти линейная, можно сказать). У unfaithful sieve—Θ(n^2/(log n)^2). У решения в лоб—Θ(n^(3/2)/(log n)^2). А на F# можно легко написать нормальный алгоритм, потому что в нем есть изменяемое состояние.
Справедливости ради, весь код (кроме первого из двух строчек) взят из постов и комментов людей, которые пытались реализовать эту параллельную быструю сортировку. В статье есть ссылки, они все до сих пор рабочие. То есть там вообще нет кода автора. А люди эти вроде как апологеты Хаскеля (в отличие от автора, да).
+4
Просто, Haskell по факту не является языком общего назначения. Глупо, к примеру, требовать того же от SQL.
-6
Харроп то ладно, он всегда был жирным троллем, который не умеет цитировать даже собственные reddit треды, в чем легко можно убедиться пройдя по ссылкам в его посте, но он хотя бы полезный, т.к. пару раз (не преувеличение) после поднятого хайпа интересные вещи в компилятр допиливали.
Но тут интереснее спросить у автора, а насколько у него глубокий уровень экспертизы в Haskell для того, чтобы оставлять подобные
[quote]Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.[/quote]
Если охота потроллить haskell советую взять более современные посты, например, про hashtable и поспрашивать у haskell-истов почему они тормозят. Это гораздо полезнее интереснее и ближе к реальности.
Но тут интереснее спросить у автора, а насколько у него глубокий уровень экспертизы в Haskell для того, чтобы оставлять подобные
[quote]Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.[/quote]
Если охота потроллить haskell советую взять более современные посты, например, про hashtable и поспрашивать у haskell-истов почему они тормозят. Это гораздо полезнее интереснее и ближе к реальности.
+4
Мой пост, мне хочется верить, тоже полезный, потому что дает возможность сформировать более взвешенное мнение о чисто функциональных языках и их ограничениях. А так же о том, как осторожно надо относиться к хайпу по поводу какой бы то ни было технологии.
Я на Хаскеле не пишу. Тем не менее, если я правильно понимаю, правильное решето Эратосфена без priority queue в нем, скорее всего, до сих реализовать нельзя. И занимает оно все равно больше строчек, чем решето на любом императивном языке.
Я на Хаскеле не пишу. Тем не менее, если я правильно понимаю, правильное решето Эратосфена без priority queue в нем, скорее всего, до сих реализовать нельзя. И занимает оно все равно больше строчек, чем решето на любом императивном языке.
+3
Мой пост, мне хочется верить, тоже полезный, потому что дает возможность сформировать более взвешенное мнение о чисто функциональных языках и их ограничениях.
Не уверен ни про взвешенное, ни про ограничия. Мнение Харропа никогда взвешенным не было, хотя некоторые вещи он подмечает хорошо. Но, чтобы отделить зерна от плевел в его потах нужно понимать как и почему, все работает, т.е. разбираться в функциональных языках на хорошем уровне.
А так же о том, как осторожно надо относиться к хайпу по поводу какой бы то ни было технологии.
Вот с этим согласен, в т.ч. и про функциональные языки и там не все идеально.
Тем не менее, если я правильно понимаю, правильное решето Эратосфена без priority queue в нем, скорее всего, до сих реализовать нельзя.Более-менее осмысленное императивное (а решето эратосфена это императивный алгоритм) решение можно было получить, когда появились массивы (array), библиотека от 2007 года, статью искать лень. С появлением пакетаvector
2008 год, но не входит в стандарт, стало ещё проще. Учитывая, чтоST
уже было, то можно даже изолировать алгоритм и получить чистый результат какer n = V.toList $ runST $ do { x <- new 0; run x ; return $ unsafeFreeze x }
.
При этом строчек будет столько же или меньше, вот некоторые будут выглядеть хуже, т.к. вместо привычного всемa[i] = 0
будетunsafeWrite a i
, в случае не возникающего в задачеa[i] = b[j]
будет ещё хужеunsafeWrite a i =<< unsafeRead b j
. Для меня учитывая количество получаемых плюсов этот синтаксис большой проблемой не является.
Почему там был использован prioity queue я не знаю, видимо кому-то хотелось получить алгоритм полностью в функциональном стиле, но я не знаю как это можно сделать эффективно без хорошей поддержи компилятора и более продвинутой системы типов, которой в ghc ещё нет. И главное я не знаю зачем нужно пиать полностью функциональную версию в чисто императивном алгоритме, если в языке есть прекрасная поддержка императивности и локализуемой изменяемости.
+2
Лучше бы TimSort написали.
0
За всё надо платить. То что, например, системы реального времени медленнее систем общего назначения никого не удивляет. А то что иммутабельность порождает сложности в некоторых алгоритмах это прямо трагедия. К тому же автор слукавил, параллельность пока
-1
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Если ограничиться заголовком статьи, то вот накопал у себя в архивах с личными экспериментами:
{-# LANGUAGE ScopedTypeVariables #-}
import Control.Parallel (par, pseq)
import System.Random (randomRIO)
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
greater `par` lesser `par` lesser ++ x : greater
where lesser = quicksort [y | y <- xs, y <= x]
greater = quicksort [y | y <- xs, y > x]
main :: IO ()
main = do
(randoms :: [Int]) <- mapM (const $ randomRIO (1, 9)) $ take 50000 $ repeat 1
print $ quicksort randoms
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Параллельная быстрая сортировка на Хаскеле и как нелегко её оказалось написать