劣線形時間で素数を合計するこのHaskellコードを最適化する方法は？

私はいくつかの小さな改善を行ったので3.4-3.5、私のマシンでは数秒で実行されます。使用IntMap.Strictすることは大いに役立ちました。それ以外は、ghc念のために手動でいくつかの最適化を実行しました。そして、HaskellコードをリンクからのPythonコードにもっと近づけます。次のステップとして、いくつかの可変を使用してみることができますHashMap。しかし、私にはわかりません...IntMap不変のコンテナであるため、いくつかの可変コンテナよりもはるかに高速になることはできません。私はまだそれの効率に驚いていますが。これをもっと早く実装できるといいのですが。

コードは次のとおりです。

import Data.List (foldl')
import Data.IntMap.Strict (IntMap, (!))
import qualified Data.IntMap.Strict as IntMap

p :: Int -> Int
p n = (sieve (IntMap.fromList [(i, i * (i + 1) `div` 2 - 1) | i <- vs]) 2 r vs) ! n
               where vs = [n `div` i | i <- [1..r]] ++ [n', n' - 1 .. 1]
                     r  = floor (sqrt (fromIntegral n) :: Double)
                     n' = n `div` r - 1

sieve :: IntMap Int -> Int -> Int -> [Int] -> IntMap Int
sieve m' p' r vs = go m' p'
  where
    go m p | p > r               = m
           | m ! p > m ! (p - 1) = go (update m vs p) (p + 1)
           | otherwise           = go m (p + 1)

update :: IntMap Int -> [Int] -> Int -> IntMap Int
update s vs p = foldl' decrease s (takeWhile (>= p2) vs)
  where
    sp = s ! (p - 1)
    p2 = p * p
    sumOfSieved v = p * (s ! (v `div` p) - sp)
    decrease m  v = IntMap.adjust (subtract $ sumOfSieved v) v m

main :: IO ()
main = print $ p $ 2*10^(9 :: Int) 

更新：

ミュータブルhashtablesを使用し~5.5secて、この実装でHaskellのパフォーマンスを実現することができました。

また、いくつかの場所でリストの代わりにボックス化されていないベクトルを使用しました。Linearハッシュが最速のようです。これはもっと速くできると思います。パッケージにsse42オプションがあることに気づきましたhasthables。正しく設定できたかどうかはわかりませんが、それがなくてもそれほど高速に実行されます。

更新2（19.06.2017）

3xジュディハッシュマップを完全に削除することで、@ Kromからの（私のコードと彼のマップを使用した）より高速で最良のソリューションを実現することができました。代わりに、単純な配列のみが使用されます。あなたがのためのキーことに気づく場合は、同じ考えを思い付くことができSハッシュマップからいずれかの配列されている1のn'かn div iのためにiから1にr。したがって、このようなHashMapを、検索キーに応じて配列内でルックアップを行う2つの配列として表すことができます。

私のコード+ Judy HashMap

$ time ./judy
95673602693282040

real    0m0.590s
user    0m0.588s
sys     0m0.000s

私のコード+私のまばらなマップ

$ time ./sparse
95673602693282040

real    0m0.203s
user    0m0.196s
sys     0m0.004s

これは、IOUArrayすでに生成されたベクトルとVectorライブラリの代わりに使用され、readArrayに置き換えられた場合、さらに高速に実行できますunsafeRead。しかし、これを可能な限り最適化することに本当に興味がないのであれば、これを行うべきではないと思います。

このソリューションとの比較は不正行為であり、公平ではありません。PythonとC ++で実装された同じアイデアがさらに高速になることを期待しています。しかし、クローズドハッシュマップを使用した@Kromソリューションは、標準のデータ構造ではなくカスタムデータ構造を使用しているため、すでに不正行為を行っています。少なくとも、Haskellの標準的で最も人気のあるハッシュマップはそれほど高速ではないことがわかります。このような問題には、より優れたアルゴリズムとより優れたアドホックデータ構造を使用する方がよい場合があります。

結果のコードは次のとおりです。