Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Как писать решения на Хаскеле
- Программы на Хаскеле компилируются на сервере с помощью GHC 7.6.1. Компилятор запускается со следующими опциями:
- ghc -v0 -O %1
- Вы можете скачать компилятор на [этой странице](http://www.haskell.org/ghc/).
- ## Пример решения задачи
- Пример решения задачи [1000. A + B problem](http://acm.timus.ru/problem.aspx?space=1&num=1000) на Хаскеле:
- main = do
- [a, b] <- (map read . words) `fmap` getLine
- print (a+b)
- Можно было бы также воспользоваться функцией `sum` и написать
- main = interact $ show . sum . map read . words
- ---
- Пример решения задачи [1001. Обратный корень](http://acm.timus.ru/problem.aspx?space=1&num=1001) на Хаскеле:
- main = interact $
- unlines . reverse . map (show.sqrt.fromInteger.read) . words
- Этот код работает 1.9 секунды.
- К сожалению, в Хаскеле стандартный тип `String` крайне неэффективен; если требуется считать или вывести много чисел, как в этой задаче, придётся прибегать к различным ухищрениям.
- Во-первых, модуль `Data.ByteString.Char8` содержит строковый тип, основанный на массиве (а не на связном списке символов). Во-вторых, теперь мы не можем использовать стандартные функции `read` и `show` для ввода/вывода чисел; если аналог `read` ещё есть, то `show` уже придётся писать свой.
- import Data.List
- import Data.Char
- import Data.Maybe
- import qualified Data.ByteString.Char8 as B
- Для чтения чисел применим функцию `readInteger`.
- readD :: B.ByteString -> Double
- readD = fromInteger . fst . fromJust . B.readInteger
- Выводить число придётся самостоятельно. Обратите внимание, что `iPart` и `fPart` имеют тип `Integer`; тут он быстрее, чем `Int64`.
- showD :: Double -> B.ByteString
- showD n = B.pack $ show iPart ++ '.' : fDigs
- where
- (iPart, fPart) = quotRem (round (10000 * sqrt n)) 10000
- fDigs = let s = show fPart
- in replicate (4 - length s) '0' ++ s
- Теперь всё довольно прозаично. Вывести числа одним куском не получится из-за ограничения по памяти в 16 MiB, так что с каждым числом работаем отдельно.
- main = B.getContents >>=
- mapM_ (B.putStrLn.showD) . reverse . map readD . B.words
- Новый код выполняется 0.16 секунды.
- ## Массивы
- Рекомендуется пользоваться unboxed массивами (`UArray` из `Data.Array.Unboxed` и `STUArray` из `Data.Array.ST`), так как они в несколько раз быстрее.
- Если производительности всё ещё недостаточно, помогут функции `unsafeRead`, `unsafeWrite` и `unsafeAt` из `Data.Array.Base`. Они не производят проверок на принадлежность индекса границам массива, а также считают, что массив индексируется от 0.
- ## Map и Set
- Если в качестве ключей в Map или Set выступает `Int`, как это часто бывает, используйте `Data.IntMap` (`Data.IntSet`), оптимизированные специально для `Int`.
- ## Ленивость
- Никакое выражение в Хаскеле не вычисляется, пока оно не понадобится. То есть, можно вывести первый элемент бесконечного списка. Можно возвести 10 в 1000000 степень — и ничего не случится, пока вы не попытаетесь, например, вывести значение на экран.
- Проблема кроется в том, что невычисленные значения (*thunks*) занимают много памяти, а на их вычисление тратится определённое «лишнее» время. Пример: строчка
- foldl (+) 0 [1..1000]
- , когда придёт пора её вычислять, сначала развернётся в пямяти в
- (((...(0 + 1) + 2) + 3) + ... 999) + 1000
- , что может привести к переполнению стека или неоправданно возросшему времени выполнения.
- С ленивостью можно бороться тремя способами:
- 1. Использование функций и структур данных, форсирующих вычисления (обычно помечены словом *Strict* или одинарной кавычкой — `foldl'`, `Data.Map.Strict`, `UArray` и т.д.)
- 2. Связывание значений при помощи `seq`. ``f (a `seq` b)`` означает, что при вычислении `b` будет автоматически вычислено и `a`, даже если оно нигде потом не понадобится.
- 3. Восклицание. Например, объявление функции `f !a = ...` аналогично ``f a = a `seq` ...``.
- ## Некоторые полезные модули
- * [Data.Complex](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Data-Complex.html) — комплексные числа.
- * [Data.Fixed](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Data-Fixed.html) — числа с фиксированным количеством знаков после запятой, а также обобщение `div` и `mod` на действительные числа.
- * [Data.Sequence](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/containers-0.5.0.0/Data-Sequence.html) — списки, поддерживающие быстрое добавление в оба конца, конкатенацию, доступ к произвольному элементу.
- * [Text.Printf](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Text-Printf.html) — копия `printf` из языка C.
- * [Text.ParserCombinators.ReadP](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/Text-ParserCombinators-ReadP.html) — удобное написание парсеров для сложных грамматик (но и для арифметических выражений подойдёт).
- * [GHC.Exts](http://www.haskell.org/ghc/docs/7.6.1/html/libraries/base-4.6.0.0/GHC-Exts.html) — определяет `groupWith` и `sortWith`. Отсортировать строки в порядке возрастания длины теперь можно так: `sortWith length strings`.
Advertisement
Add Comment
Please, Sign In to add comment