相关疑难解决方法(0)

生成素数是一个玩具问题,我经常不时尝试,特别是在尝试新的编程语言,平台或风格时.

我正在考虑尝试使用Hadoop(Map Reduce)编写素数生成算法或素数测试算法.

我想我会发布这个问题,以获得提示,参考,算法,方法.

虽然我的主要兴趣是基于Map Reduce的算法,但我不介意查看新的Hadoop编程模型或者例如查看使用PiCloud

我在Prime数字生成中似乎有一些有趣的问题:这里,这里和这里,但没有任何与Parallel方法相关的问题引起了我的注意.

提前致谢.

我想在Haskell中使用Vectors 编写Floyd-Warshall所有对最短路径算法的有效实现,以期获得良好的性能.

实现非常简单,但不使用三维| V |×| V |×| V | 矩阵,使用二维向量,因为我们只读过前一个k值.

因此,该算法实际上只是传递2D矢量的一系列步骤,并且生成新的2D​​矢量.最终的2D矢量包含所有节点(i,j)之间的最短路径.

我的直觉告诉我,确保在每个步骤之前评估先前的2D向量是很重要的,所以我使用了函数BangPatterns的prev参数fw和严格foldl':

{-# Language BangPatterns #-}

import           Control.DeepSeq
import           Control.Monad       (forM_)
import           Data.List           (foldl')
import qualified Data.Map.Strict     as M
import           Data.Vector         (Vector, (!), (//))
import qualified Data.Vector         as V
import qualified Data.Vector.Mutable as V hiding (length, replicate, take)

type Graph = Vector (M.Map Int Double)
type TwoDVector = Vector (Vector Double)

infinity :: Double
infinity = 1/0

-- …

所以我一直在尝试通过解决 Codeforce 上的一些问题来学习 Haskell。
即使我认为我的时间复杂度是最佳的，我也得到了很多 TLE（超出时间限制）。

我的问题是：是我编写这个程序的方式使它变慢了吗？

例如，这里是问题。

基本上答案是找到给定的，其中 and =和之间的除数数之差。annan = 2*an-1 + D(n)D(n)nn-1

（更新：上限为n10 ⁶）。

下面是我的程序。

import qualified Data.Map.Strict as Map

main = do t <- read <$> getLine
          putStrLn . show $ solve t

solve :: Integer -> Integer
solve 0 = 1
solve 1 = 1
solve n = (2*(solve (n-1)) + (fact n) - (fact (n-1))) `mod` 998244353
    where fact …