Дистанционная подготовка: Возможно слишком агрессивные ограничения для haskell?
Возможно слишком агрессивные ограничения для haskell?
от Дмитрий Гершвин - Суббота 28 Февраль 2015, 02:31
111508. Кружки в Маховниках
 

Разумно оптимизированная топологическая сортировка не проходит половину тестов по времени. Сложность вычислений — O(N). Конечная сложность алгоритма будет O(N log N), так как добавится куча, но топологическая сортировка за линейное время уже не проходит по времени. Может стоит увеличить лимиты для Haskell для этой задачи?

Основной код:

zeroElementsAfterDecrement :: (MArray a e m, Num e, Eq e) => a Int e -> [Int] -> m[Int]
zeroElementsAfterDecrement arr is = do rs <- bulkRead arr is
                                       let decrementedValues = (zip is . map (subtract 1)) rs
                                       bulkWrite arr decrementedValues
                                       return [ i | (i, e) <- decrementedValues, e == 0 ]

testBulkUpdate = runST $ do arr <- newArray (1, 10) 1 :: ST s (STArray s Int Int)
                            zeroElementsAfterDecrement arr [2, 4]

getNextVertexesForSources :: (MArray a e m, Num e, Eq e) => Graph -> a Int e -> [Int] -> m [Int]
getNextVertexesForSources graph arr sources = foldM (\acc source -> zeroElementsAfterDecrement arr (graph!source) >>= return . flip (++) acc) [] sources

topSort_ :: (MArray a e m, Num e, Eq e) => Graph -> a Int e -> [Int] -> [Int] -> m [Int]
topSort_ graph arr [] partialResult = return partialResult 
topSort_ graph arr sources partialResult = getNextVertexesForSources graph arr sources >>= \newSources -> topSort_ graph arr newSources (sources ++ partialResult)

topSort :: Graph -> [Int]
topSort graph = runST $ do let upperBound = snd $ bounds graph
                           arr <- newArray (1, upperBound) 0 :: ST s (STUArray s Int Int)
                           ((incrementByIndices arr) . concat . elems) graph
                           arrayAsList <- bulkRead arr [1..upperBound]
                           let sources = [ i | (i, e) <- zip [1..] arrayAsList, e == 0]
                           topSort_ graph arr sources []
Re: Возможно слишком агрессивные ограничения для haskell?
от Дмитрий Гершвин - Пятница 13 Март 2015, 09:36
  В итоге надо zeroElementsAfterDecrement оптимизировать и IO. Проходит тютелька в тютельку.
Re: Возможно слишком агрессивные ограничения для haskell?
от Владимир М. Гуровиц - Пятница 22 Май 2015, 01:32
  Никто не обещал, что каждая задача проходит на всех языках. У нас нет отдельных ограничений для разных языков.