快速幂和算法
快速幂和算法
提问于 2015-02-22 09:12:33
这个代码在一个测试用例上达到了时间限制，解决了这个挑战。我使用的方法来自于图书算法函数式编程方法，这是一种回溯深度搜索方法。如何提高此代码的速度？还是有更好的方法来做呢？
searchDfs :: (Eq node) =>
(node -> [node]) -> -- generates successor nodes
(node -> Bool) -> -- is goal
node -> -- first node
[node]
searchDfs succ goal x = search' ([x])
where
search' s
| null s = []
| goal (head s) = head s : search' (tail s)
| otherwise = let x = head s
in search' (succ x ++ tail s)
type Degree = Int
type CurrentSum = Int
type CurrentNumber = Int
type Node = (CurrentSum,CurrentNumber,Degree,Goal)
type Goal = Int
succN :: Node -> [Node]
succN (sum,i,d, goal) = [( sum+i'^d, i', d, goal) | i' <- [(i+1)..goal], sum+i'^d <= goal ]
goal :: Node -> Bool
goal (sum,_,_,m) = sum == m
countSols :: Degree -> Goal -> Int
countSols d m = foldr (+) 0 $ map (\(sum,i) -> length (searchDfs succN goal (sum,i,d,m))) startingNumbers
where startingNumbers = [ (i^d,i) | i <- [1..m], i^d <= m]
main = do
m <- readLn
d <- readLn
let c = countSols d m
print c回答 2
Code Review用户
发布于 2015-02-22 11:24:20
search'可以写得更特别(但不一定更快)，比如搜索‘[] = [] search’(x: xs ) \x:目标x=x:搜索‘xs\x= ++’(succ x++ xs)Eq对searchDfs的约束似乎是未使用的。- 在
succN中，您要计算sum+i'^d两次(除非编译器将其优化，但最好不要依赖它)。此外，它还将计算i'的所有值，直到goal为止，尽管您可能希望尽早中止。也许使用takeWhile会更好: succN (sum，i，d，goal) = takeWhile ((s，_ ) -> S <= goal) [( sum+I^ d，i'，d，goal) _ i‘<- (i+1)..goal] - 看起来，您的
d和goal字段的Nodes总是相同的。那么，您不应该将它作为Node的一部分，而是显式地传递它。您可以在不修改searchDfs的情况下做到这一点！
Code Review用户
发布于 2015-02-23 03:54:33
正是因为i^d产生了Int无法容纳的太大的数字，所以它变得没有响应/冻结。这也是因为在不同的节点上计算相同的i^d会使它变得更慢。现在它只计算一次。然后使用地图查找。
import Control.Monad (guard)
import qualified Data.Map.Strict as Map
import Data.Map ((!),fromList,Map(..),member)
-- depth first search higher order function
depthFirstSearch :: (node -> [node]) -> -- successor node generator
(node -> Bool) -> -- is goal checker
[node] -> -- starting root nodes
[node] -- goal nodes
depthFirstSearch succ goal roots = search' roots
where search' [] = []
search' (x:xs) | goal x = x : search' xs
| otherwise = search' (succ x ++ xs)
type Degree = Int
type CurrentSum = Int
type CurrentNumber = Int
type Node = (CurrentNumber,CurrentSum)
type Goal = Int
-- generates valid successor nodes
succN :: Goal -> Map Int Int -> Node -> [Node]
succN goal _map (i,sum) = do
i' <- [(i+1)..goal]
guard (member i' _map)
let sum' = sum + _map!i'
guard (sum' <= goal)
return (i',sum')
-- checks if the node is the goal
goalN :: Goal -> Node -> Bool
goalN goal (_,sum) = goal == sum
-- counts solutions
solCount :: Degree -> Goal -> Int
solCount d goal =
let roots = rts d goal -- [(i,i^d) | i <- [1..goal], i^d <= goal]
_map = Map.fromList roots
nodes = depthFirstSearch (succN goal _map) (goalN goal) roots
c = length nodes
in c
rts :: Degree -> Goal -> [Node]
rts d' g' = do
let d = fromIntegral d'
g = fromIntegral g'
a <- [(1::Integer)..(fromIntegral g)]
let aNth = a^d
guard (aNth <= g)
let bNth = (fromInteger :: Integer -> Int) aNth
b = (fromInteger :: Integer -> Int) a
return (b,bNth)
main = do
g <- readLn
d <- readLn
print $ solCount d g页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/82259
复制相关文章
相似问题
腾讯云开发者
