Question

0

112

Vistas

El tamiz de Eratóstenes funciona más lento después de mejorar

Trato de mejorar el algoritmo básico de Tamiz de Eratóstenes evitando tachar múltiplos duplicados de números primos, pero resulta ser peor de lo que esperaba.

He implementado dos métodos que devuelven números primos en el rango [2..max)

Tamiz básico

 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) + 1; 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; }

Ejecute Sieve22Max_Basic(100) , vea que algunos múltiplos cruzan más de uno (por ejemplo 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

Tamiz mejorado

Luego, trato de mejorar usando una matriz que almacena smallest prime divisor ( spd ) de cada número.

 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

Cuando pase por múltiplos de primo p, no tacharé el número mul que tiene spd[mul] < p porque mul fue tachado por spd[mul] antes

 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) + 1; 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; }

Prueba

Pruebo en mi computadora portátil (core i7 - 2.6 Ghz), con n = 1 mil millones

Sieve22Max_Basic tarda solo 6 s, mientras que Sieve22Max_Enh tarda más de 10 s en completarse

 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}");

Puedes probar en https://onlinegdb.com/tWfMuDDK0

¿Qué hace más lento?

over 4 years ago · Santiago Trujillo

1 Respuestas

Responde la pregunta

0

Responde la pregunta

Encuentra empleos remotos

Accepted Answer · 2022-03-29T19:55:16.149Z

Compare sus dos bucles de las versiones original y mejorada.

Original:

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

Mejorado:

 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; } }

Algunas observaciones:

Ambos bucles ejecutan la misma cantidad de iteraciones.
Para cada iteración, el ciclo original ejecuta tres operaciones muy rápidas: 1) cambia un valor en BitArray , mul += inc y verifica mul < n .
Por cada iteración del bucle mejorado, ejecutamos más operaciones: check spd[mul] >= p , mul += inc , mul * p (en la condición de bucle for), check mul * p < n .
El incremento += y la verificación de la condición del bucle para < son iguales en ambos bucles; verificar spd[mul] >= p y cambiar un valor en BitArray son comparables en cuánto tiempo toman; pero la operación adicional mul * p en la condición del segundo ciclo es la multiplicación, ¡es costosa!
Pero también , para cada iteración del segundo ciclo, si spd[mul] >= p es true , entonces también ejecutamos: mul * p (¡otra vez!), convertir a int , cambiar un valor en BitArray , mul * p (tercera time!), asumo de nuevo una conversión a int en la indexación de spd , y asigno un valor en la matriz spd .

Para resumir, cada iteración de su segundo bucle mejorado es computacionalmente "más pesada". Esta es la razón por la que su versión mejorada es más lenta.

0

112