このアルゴリズムをリファクタリングして高速化しようとしています。ここでの速度向上のための最初のリファクタリングは何でしょうか?
public int GetHowManyFactors(int numberToCheck)
{
// we know 1 is a factor and the numberToCheck
int factorCount = 2;
// start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor
for (int i = 2; i < numberToCheck; i++)
{
if (numberToCheck % i == 0)
factorCount++;
}
return factorCount;
}
実行できる最初の最適化は、数の平方根までチェックするだけでよいということです。これは、一方が平方根よりも小さく、もう一方が大きいペアになっているためです。
これに対する 1 つの例外nは、 が正確な 2 乗の場合、その平方根は因数ですnが、ペアの一部ではありません。
たとえば、数字が 30 の場合、要素は次のペアになります。
したがって、5 より大きい数値をチェックする必要はありません。なぜなら、ペアで対応する小さい因数が見つかったら、他のすべての因数がすでに存在すると推測できるからです。
C# でそれを行う 1 つの方法を次に示します。
public int GetFactorCount(int numberToCheck)
{
int factorCount = 0;
int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck));
// Start from 1 as we want our method to also work when numberToCheck is 0 or 1.
for (int i = 1; i < sqrt; i++)
{
if (numberToCheck % i == 0)
{
factorCount += 2; // We found a pair of factors.
}
}
// Check if our number is an exact square.
if (sqrt * sqrt == numberToCheck)
{
factorCount++;
}
return factorCount;
}
より高速に使用できるアプローチは他にもありますが、特に 32 ビット整数を操作するためだけに必要な場合は、これで十分に高速であることに気付くかもしれません。
故意に数の平方根で止まることができるので、どれだけ高くしなければならないかの限界を減らします。ループを実行する必要があります。
ループ カウンターを 2 (数字が偶数の場合) または 3 (奇数の場合) から開始します。これにより、ループ回数がさらに 50% 減少する他のすべての数値を確認できるはずです。
public int GetHowManyFactors(int numberToCheck)
{
// we know 1 is a factor and the numberToCheck
int factorCount = 2;
int i = 2 + ( numberToCheck % 2 ); //start at 2 (or 3 if numberToCheck is odd)
for( ; i < numberToCheck / 2; i+=2)
{
if (numberToCheck % i == 0)
factorCount++;
}
return factorCount;
}
ここで、この正確なトピックについて長い議論があるようです: Algorithm to calculate the number of divisor of a given number
お役に立てれば
最初に気付くことは、すべての素因数を見つけるだけで十分だということです。これらを取得すると、総約数を簡単に見つけることができます。素数ごとに、出現する回数に 1 を加え、それらを掛け合わせます。したがって、12 = 2 * 2 * 3 の場合、(2 + 1) * (1 + 1) = 3 * 2 = 6 個の因数があります。
次のことは最初から続きます。因数が見つかったら、結果の数値が小さくなるように割ります。これを、現在の数値の平方根を確認するだけでよいという事実と組み合わせると、これは大きな改善です。たとえば、N = 10714293844487412 を考えてみましょう。単純に、N ステップかかります。その平方根までチェックするには、sqrt(N) または約 1 億ステップかかります。しかし、係数 2、2、3、および 953 は早い段階で発見されるため、実際には 100 万までチェックするだけで済みます。これは 100 倍の改善です!
もう 1 つの改善点: すべての数値をチェックして、数値が割り切れるかどうかを確認する必要はありません。素数だけです。より便利な場合は、2 と奇数、または 2、3、および 6n-1 と 6n+1 (基本的なホイールふるい) を使用できます。
ここにもう 1 つの優れた改善点があります。素数かどうかをすばやく判断できれば、割り算の必要性をさらに減らすことができます。小さな因数を取り除いた後、120528291333090808192969 があるとします。その平方根までチェックするだけでも、3000 億ステップという長い時間がかかります。ただし、Miller-Rabin テスト (非常に高速です。おそらく 10 ～ 20ナノ秒)) は、この数が合成であることを示します。これはどのように役立ちますか? これは、立方根を調べて因数が見つからない場合、素数が 2 つ残っていることを意味します。数が平方の場合、その約数は素数です。数が正方形でない場合、その数は別個の素数です。これは、「現在の合計」をそれぞれ 3 または 4 で乗算して、最終的な答えを得ることができることを意味します - 因数を知らなくても! これは想像以上に大きな違いを生む可能性があります。必要なステップ数は 3,000 億からわずか 5,000 万に減少し、6,000 倍の改善です!
上記の唯一の問題は、Miller-Rabin が数が合成であることしか証明できないことです。素数が与えられた場合、その数が素数であることを証明できません。その場合、数の平方根に因数分解する手間を省くために素数証明関数を書きたいと思うかもしれません。(または、答えが正しいという証明ではなく、正しいという高い信頼に満足する場合は、Miller-Rabin 検定をさらに数回実行することもできます。数値が 15 回の検定に合格した場合、その数値は 1 未満の確率で合成されます。 10億で。）
この関数を頻繁に使用する場合は、Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenesの修正アルゴリズムを使用して、1 から Max までの間隔の回答を配列に保存できます。IntializeArray() を 1 回実行した後、0(1) で回答を返します。
const int Max =1000000;
int arr [] = new int [Max+1];
public void InitializeArray()
{
for(int i=1;i<=Max;++i)
arr[i]=1;//1 is factor for everyone
for(int i=2;i<=Max;++i)
for(int j=i;i<=Max;i+=j)
++arr[j];
}
public int GetHowManyFactors(int numberToCheck)
{
return arr[numberToCheck];
}
しかし、この関数をあまり使用しない場合、最善の解決策は unitll 平方根をチェックすることだと思います。
注：コードを修正しました！
試行分割よりもはるかに先に進む実装が簡単なアルゴリズムは、Pollard Rhoです。
これは、C# に簡単に適応できるはずの Java 実装です: http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html