埃拉托色尼篩改進后運行速度變慢-有解無憂

我試圖通過避免洗掉重復的素數倍數來改進基本的埃拉托色尼篩演算法，但結果比我的預期差

我已經實作了兩種回傳范圍 [2..max) 中的素數的方法

基本篩

public static List<int> Sieve22Max_Basic(int n) {
    var primes = new List<int>();
    var sieve = new BitArray(n, true); // default all number are prime
    //int crossTotal = 0;

    int sqrt_n = (int)Math.Sqrt(n);
    for (int p = 2; p < sqrt_n;   p) {
        if (sieve[p]) {
            primes.Add(p);
            //var cross = new List<int>();
            int inc = p == 2 ? p : 2 * p;
            for (int mul = p * p; mul < n; mul  = inc) {
                // cross out multiple of prime p
                // cross.Add(mul);
                //  crossTotal;
                sieve[mul] = false;
            }

            //if (cross.Count > 0)
            //    Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
        }
    }
    //Console.WriteLine($"crossTotal: {crossTotal:n0}");

    for (int p = sqrt_n; p < n;   p)
        if (sieve[p])
            primes.Add(p);

    return primes;
}

運行Sieve22Max_Basic(100)，看到一些倍數超過一個（例如45, 75, 63：）

Prime 2, cross out: 4 6 8 ... 96 98
Prime 3, cross out: 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99
Prime 5, cross out: 25 35 45 55 65 75 85 95
Prime 7, cross out: 49 63 77 91

增強篩

smallest prime divisor然后，我嘗試通過使用存盤（spd）每個數字的陣列來改進。

45 = 3 x 5      // spd[45] = 3
75 = 3 x 5 x 5  // spd[75] = 3
63 = 3 x 3 x 7  // spd[63] = 3

當經過素數 p 的倍數時，我不會劃掉mul之前被劃掉的數字spd[mul] < pmulspd[mul]

public static List<int> Sieve22Max_Enh(int n) {
    var sieve = new BitArray(n, true);
    var spd = new int[n];
    for (int i = 0; i < n;   i) spd[i] = i;
    
    var primes = new List<int>();
    //int crossTotal = 0;

    int sqrt_n = (int)Math.Sqrt(n);
    for (int p = 2; p < sqrt_n;   p) {
        if (sieve[p]) {
            primes.Add(p);

            //var cross = new List<int>();
            int inc = p == 2 ? 1 : 2;
            for (long mul = p; mul * p < n; mul  = inc) {
                if (spd[mul] >= p) {
                    sieve[(int)(mul * p)] = false;
                    spd[mul * p] = p;
                    //  crossTotal;
                    //cross.Add((int)(mul * p));
                }
            }
            //if (cross.Count > 0)
            //    Console.WriteLine($"Prime {p}, cross out: {string.Join(' ', cross)}");
        }
    }
    //Console.WriteLine($"crossTotal: {crossTotal:n0}");

    for (int p = sqrt_n; p < n;   p)
        if (sieve[p])
            primes.Add(p);

    return primes;
}

測驗

我在我的筆記本電腦（核心 i7 - 2.6 Ghz）上測驗，n = 10 億

Sieve22Max_Basic只需要 6s 而Sieve22Max_Enh需要超過 10s 才能完成

var timer = new Stopwatch();
int n = 1_000_000_000;

timer.Restart();
Console.WriteLine("==== Sieve22Max_Basic ===");
var list = Sieve22Max_Basic(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");

Console.WriteLine();

timer.Restart();
Console.WriteLine("==== Sieve22Max_Enh ===");
list = Sieve22Max_Enh(n);
Console.WriteLine($"Count: {list.Count:n0}, Last: {list[list.Count - 1]:n0}, elapsed: {timer.Elapsed}");

您可以在https://onlinegdb.com/tWfMuDDK0嘗試

它使什么變慢？

uj5u.com熱心網友回復：

比較原始版本和改進版本的兩個回圈。

原版的：

int inc = p == 2 ? p : 2 * p;
for (int mul = p * p; mul < n; mul  = inc) {
  sieve[mul] = false;
}

改進：

int inc = p == 2 ? 1 : 2;
for (long mul = p; mul * p < n; mul  = inc) {
  if (spd[mul] >= p) {
    sieve[(int)(mul * p)] = false;
    spd[mul * p] = p;
  }
}

一些觀察：

兩個回圈運行相同數量的迭代。
對于每次迭代，原始回圈執行三個非常快速的操作：1) 更改中的值BitArray，mul = inc然后檢查mul < n。
對于改進回圈的每次迭代，我們執行更多操作：檢查spd[mul] >= p、、mul = inc（mul * p在 for 回圈條件下）、檢查mul * p < n。
兩個回圈中的增量 =和回圈條件檢查<相同；檢查spd[mul] >= p和更改值在BitArray花費多長時間方面具有可比性；但是第二個回圈條件中的附加操作mul * p是乘法——它很昂貴！
而且，對于第二個回圈的每次迭代，如果是，那么我們還執行：（再次！），強制轉換為，更改，（第三次！），我再次假設在索引中強制轉換為，并且在陣列中賦值。spd[mul] >= ptruemul * pintBitArraymul * pintspdspd

總而言之，您的第二個改進回圈的每次迭代在計算上都“更重”。這就是您的改進版本較慢的原因。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/427018.html

標籤：C＃算法素数 sieve-of-eratosthenes

上一篇：從陣列中選擇一個元素以在對陣列中的所有元素進行異或后最大化總和

下一篇：一列資料對最終分類結果的影響