Отличное решение! Действительно, из моего поля зрения совсем ускользнуло наличие альтернативных реализаций для строк. Ваши решения проходят все тесты с большим запасом.
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и boxed-массивов на 19 тесте получаем 8.61Mb вместо 10.25Mb, а для unboxed 984.00Kb.
Заголовок спойлера
import Data.Char (isSpace, isDigit, digitToInt)
import Data.List (foldl')
import Control.Monad
import System.IO
import Data.Array.Unboxed
getInt :: IO Int
getInt = hGetIntegral stdin
hGetIntegral :: Handle -> IO Int
hGetIntegral h = do
digits <- hGetDigits h
return $ read digits
hGetDigits :: Handle -> IO [Char]
hGetDigits h = g =<< hIsEOF h
where
g eof
| eof == True = return []
| otherwise = do
char <- hGetChar h
if isDigit char
then fmap (char:) (hGetDigits h)
else return []
foldM' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM' _ z [] = return z
foldM' f z (x:xs) = do
z' <- f z x
z' `seq` foldM' f z' xs
addToArray :: UArray Int Int -> Int -> UArray Int Int
addToArray arr number = accum (+) arr [(number, 1)]
fillArray :: UArray Int Int -> IO (UArray Int Int)
fillArray a = do
numb <- getInt
foldM' (\arr num -> addToArray arr <$> num) a (replicate numb getInt)
printPair (a, b) = replicateM_ b $ print a
main :: IO ()
main = do
t <- read <$> getLine :: IO Int
let a = array (0,100) [(i, 0) | i <- [0..100]]
res <- foldl' (>=>) return (replicate t fillArray) a
mapM_ printPair $ assocs res
Конечно можно предположить, что мы таким образом хоть и выиграли на чтении, но получили просадку в производительности на существенном большем количестве вызовов функции accum, но считаю это маловероятным. Тоже самое я пробовал с IOArray, который такой функции не имеет, и при его использовании приходится в обоих случаях оперировать с отдельными элементами — результат получился аналогичным.
Остаётся ещё оптимизация вывода результата, но я пока ничего не придумал в этом направлении.
По-хорошему, мне необходимо разобраться с профилированием программ на Haskell, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и boxed-массивов на 19 тесте получаем 8.61Mb вместо 10.25Mb, а для unboxed 984.00Kb.
Конечно можно предположить, что мы таким образом хоть и выиграли на чтении, но получили просадку в производительности на существенном большем количестве вызовов функции accum, но считаю это маловероятным. Тоже самое я пробовал с IOArray, который такой функции не имеет, и при его использовании приходится в обоих случаях оперировать с отдельными элементами — результат получился аналогичным.
Остаётся ещё оптимизация вывода результата, но я пока ничего не придумал в этом направлении.
По-хорошему, мне необходимо разобраться с профилированием программ на Haskell, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.