Comments 7
Спасибо за статью. Было интересно взглянуть на функциональный подход в таких задачах. Честно говоря, удивлён что скорости ввода/вывода было достаточно. Например в задаче С обычные операции ввода/вывода на С++ (используя cin/count) заняли 321 ms на 193 тесте.
В задаче F всего 20 тестов и тут уже интересно. Одно и то же решение (речь идёт о честном, не используя подсчёт на [0,100]), но последовательно заменяя cin/count -> cin/count + cin.tie + sync_with_stdio(false) -> посимвольное чтение и сборка числа "руками" ускорила 0.611s -> 345ms -> 213ms. Отсюда видно что ввод/вывод данных в моём решении занял не менее 0.4s а это почти половина лимита…
Сами задачи мне не очень понравились. На таких языках как Java или C# было на порядок сложнее сделать быстрое чтение/запись чем решить саму задачу.
Мне кажется что решение на хаскеле надо ускорять не в сторону красивой свёртки а именно со стороны чтения.
P.S. прилагаю самый быстрый вариант чтения (может натолкнёт на идею, к сожалению я сам недостаточно хорошо знаю хаскель что бы это реализовать)
inline int read(){
int tmp;
do
{
tmp = cin.get();
} while (tmp < '0' || tmp > '9');
int res = tmp - '0';
for (tmp = cin.get();tmp >= '0' && tmp <= '9';tmp = cin.get())
{
res = res * 10 + tmp - '0';
}
return res;
}
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и 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, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.
fillIOArray :: IOUArray Int Int -> IO ()
fillIOArray arr = readLine >>= addList
where
readLine = parseLine <$> getLine
parseLine = tail . map read . words
addList = mapM_ (addToIOArray arr)
(это кстати ИМХО в любом случае надо делать, для читаемости/сопровождаемости, нечего тут буквы экономить ;) ).
Профилирование указывает на проблему в парсинге:
и не удивительно — там же стандартный String, который известен своей неэффективностью (это связный список из юникодных код-поинтов). Давайте повозимся с байтиками:
gist.github.com/portnov/584fa2e74486af561f4c4b3f19bf2e17
на моём рандомно сгенерированном input.txt размером 20Мб (2746 строк, до 5000 чисел в строке) время упало с 17 секунд до 2.5. Причём теперь основная часть времени уходит уже на вывод результата:
:)gist.github.com/portnov/0d76663e9b1759294d94147b9f48680a
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Решаем задачи Яндекс.Интервью в функциональном стиле