これはあなたのHaskellは階乗のみであり、

あなたの好きな言語に関して言えば、私は通常、他のことは同じであると言います。私は、数値クラッシャーにはC ++を、他のすべてにはHaskellを好みます。 そのような部門が正当化されているかどうかを定期的に確認することは有用であり、ごく最近、アイドルで非常に単純な質問が発生しました：数のすべての約数の合計は、たとえば、最初の10億の数について、この数の増加にどのように影響しますか？ このタスクを脅かすのは簡単です（結果として得られる番号グラインダーと呼ぶのは残念です）。そのため、このようなチェックに最適なオプションのように見えます。

さらに、Haskellコードのパフォーマンスを正確に予測する能力はまだないので、パフォーマンスがどのように低下​​するかを知るために、故意に悪いアプローチを試してみると便利です。

さらに、さらに、各数の除数の正面検索よりも効率的なアルゴリズムを簡単に披露できます $$$1$ 前に $$$n$ 。

アルゴリズム

それでは、アルゴリズムから始めましょう。

数のすべての約数の合計を見つける方法 $$$n$ ？ あなたはすべてを通過することができます $$$k_1 \ in \ {1 \ dots \ lfloor \ sqrt n \ rfloor \}$ そして、そのようなすべての $$$k_1$ 除算の残りを確認する $$$n$ に $$$k_1$ 。 残りが $$$0$ 、バッテリーに追加します $$$k_1 + k_2$ どこで $$$k_2 = \ frac {n} {k_1}$ もし $$$k_1 \ neq k_2$ 、そしてちょうど $$$k_1$ そうでなければ。

このアルゴリズムを適用できますか $$$n$ 回、各番号に対して $$$1$ 前に $$$n$ ？ もちろんできます。 難しさは何ですか？ その順序がわかりやすい $$$O（n ^ \ frac {3} {2}）$ 除算-数字ごとに正確に除算のルートを作成し、数字があります $$$n$ 。 もっと良くできますか？ はい、そうです。

この方法の問題の1つは、無駄な労力を費やしていることです。 分割数が多すぎると、成功に至らず、ゼロ以外の剰余が生じます。 もう少し怠けて、反対側からタスクにアプローチするのは自然です：除数のすべての種類の候補を生成し、それらが満たす数値を見てみましょうか？

だから、今から私たちはからの各番号ごとに一挙に必要です $$$1$ 前に $$$n$ すべての除数の合計を計算します。 これを行うには、すべてを通過します $$$k_1 \ in \ {1 \ dots \ lfloor \ sqrt n \ rfloor \}$ 、およびそれぞれの $$$k_1$ 全部見てみましょう $$$k_2 \ in \ {k_1 \ dots \ lfloor \ frac {n} {k} \ rfloor \}$ 。 各ペアについて $$$（k_1、k_2）$ インデックスでセルに追加します $$$k_1 \ cdot k_2$ 価値 $$$k_1 + k_2$ もし $$$k_1 \ neq k_2$ 、そして $$$k_1$ そうでなければ。

このアルゴリズムは正確に $$$n ^ \ frac {1} {2}$ 除算、および各乗算（除算よりも安価）が成功につながります。各反復で何かを増やします。 これは、正面アプローチよりもはるかに効果的です。

さらに、この同じ正面アプローチを使用して、両方の実装を比較し、かなり小さい数に対して同じ結果が得られることを確認できます。

最初の実装

ちなみに、これは直接Haskellの初期実装のほぼ擬似コードです。

module Divisors.Multi(divisorSums) where

import Data.IntMap.Strict as IM

divisorSums :: Int -> Int
divisorSums n = IM.fromListWith (+) premap IM.! n
  where premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1)
                 | k1 <- [ 1 .. floor $ sqrt $ fromIntegral n ]
                 , k2 <- [ k1 .. n `quot` k1 ]
                 ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Main



- , .

, $$$n$ . , — , ( ), , - .

? i7 3930k 100'000 0.4 . 0.15 0.25 — GC. 8 , , — 8 , 800 .

( ). , , ́? 1'000'000 7.5 , 4.5 GC, 80 ( 10 , ). Senior Java Software Developer' GC, . . , , : 64 , 80, .

,

C++

, , .

, , :

#include <vector>
#include <string>
#include <cmath>
#include <iostream>

int main(int argc, char **argv)
{
    if (argc != 2)
    {
        std::cerr << "Usage: " << argv[0] << " maxN" << std::endl;
        return 1;
    }
    int64_t n = std::stoi(argv[1]);

    std::vector<int64_t> arr;
    arr.resize(n + 1);

    for (int64_t k1 = 1; k1 <= static_cast<int64_t>(std::sqrt(n)); ++k1)
    {
        for (int64_t k2 = k1; k2 <= n / k1; ++k2)
        {
            auto val = k1 != k2 ? k1 + k2 : k1;
            arr[k1 * k2] += val;
        }
    }

    std::cout << arr.back() << std::endl;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

-O3 -march=native



, clang 8, 0.024 , 8 . — 155 , 8 , . . . . ! ?

, IntMap



, , , — , (, , ). , C++?

:

module Divisors.Multi(divisorSums) where

import qualified Data.Array.IArray as A
import qualified Data.Array.Unboxed as A

divisorSums :: Int -> Int
divisorSums n = arr A.! n
  where arr = A.accumArray (+) 0 (1, n) premap :: A.UArray Int Int
        premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1)
                 | k1 <- [ 1 .. floor bound ]
                 , k2 <- [ k1 .. n `quot` k1 ]
                 ]
        bound = sqrt $ fromIntegral n :: Double
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

unboxed- , Int



, . Boxed- arr



, . , bound



, , LICM, , defaulting' floor



.

0.045 ( !). 8 , GC (!). — , C++, . ! ?

, . accumArray



, — . accumArray



unsafeAccumArray



:

module Divisors.Multi(divisorSums) where

import qualified Data.Array.Base as A
import qualified Data.Array.IArray as A
import qualified Data.Array.Unboxed as A

divisorSums :: Int -> Int
divisorSums n = arr A.! (n - 1)
  where arr = A.unsafeAccumArray (+) 0 (0, n - 1) premap :: A.UArray Int Int
        premap = [ (k1 * k2 - 1, if k1 /= k2 then k1 + k2 else k1)
                 | k1 <- [ 1 .. floor bound ]
                 , k2 <- [ k1 .. n `quot` k1 ]
                 ]
        bound = sqrt $ fromIntegral n :: Double
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

, , (, , API , ). ?

— 0.021 (, , , !). , 8 , 0 GC.

— 152 (, !). 8 . 0 GC. - . , , .

-, , accumArray



unsafe



- . 10-20 ( , operator[]



at()



), !

-, , , .

-, , , . , , . , , ( ) . LLVM JIT . , , .

-, : . unsafe



, , k_1 * k_2 <= n



k_1, k_2



, . , . , , , , ( ), array



.

-: , , . , . , - Go, Rust, Julia, D, Java, Malbolge , , C++- — , , .

P.S.: . .