Pull to refresh
8
0
Алексей Матвеев @AlexMatveev

Пользователь

Send message
Отличное решение! Действительно, из моего поля зрения совсем ускользнуло наличие альтернативных реализаций для строк. Ваши решения проходят все тесты с большим запасом.
Единственное — во второй версии пришлось заменить <> на `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, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.

Information

Rating
Does not participate
Location
Новосибирск, Новосибирская обл., Россия
Date of birth
Registered
Activity