Quiero imprimir todos los números primos hasta un número primo dado máx. Tengo dos métodos: el tamiz de Eratóstenes y el método trivial. ¿Cómo comparo sus tiempos de ejecución? ¿Qué método es más rápido?

Answer 1

El método simple para el cerebro que utilizo para comparar la velocidad de dos algoritmos es hacer dos binarios y ejecutarlos con el comando “time” UNIX con la misma entrada. Es muy conveniente porque no requiere ninguna maquinaria adicional en el código mismo. Todo lo que necesita hacer es pegar la palabra “tiempo” antes del mismo comando que usaría para ejecutarlo normalmente, y tal vez algunas opciones adicionales para mostrar el consumo de otros recursos.

Si quiero un poco más de detalle, utilizo una suite de evaluación comparativa que vuelve a ejecutar el código tantas veces como sea necesario para determinar el tiempo de ejecución promedio y su desviación estándar dentro de un margen de error estrecho, que generalmente requiere envoltorios bastante sencillos alrededor de su código.

Y si eso no da suficientes detalles, utilizo un generador de perfiles para ver dónde exactamente cada algoritmo pasa la mayor parte de su tiempo.

Answer 2

Para grandes conjuntos de datos, minimizar el tamaño y el acceso a los datos se vuelve más importante para la velocidad del algoritmo que las operaciones aritméticas mismas.

El tamiz accede y modifica constantemente todas las partes de una matriz de celdas máximas , lo que desbordará el caché e incurrirá en errores de caché, o incluso excederá la memoria principal que requiere paginación. Si max = 2³², entonces el tamiz necesita 2³² de almacenamiento.

La división de prueba almacena solo los primos confirmados, y en última instancia solo requiere el almacenamiento [math] O \ left (\ frac {max} {log (max)} \ right) [/ math]. Para max = 2³², requiere 10.4% de almacenamiento como el tamiz. La escritura es solo hasta el final del conjunto de números primos, no dispersa sobre ella.

La división de prueba por solo primos max ) vuelve a acceder solo [matemáticas] O \ left (\ frac {sqrt (max)} {log (sqrt (max))} \ right) = O \ left (\ frac {2sqrt (max)} {log (max)} \ right) [/ math] primos como divisores; los primos posteriores no se necesitan nuevamente hasta la salida, y se pueden paginar hasta entonces. Para max = 2³², solo unos 13600 primos deben mantenerse a la mano como divisores de prueba, lo que se ajustará fácilmente no solo en la memoria principal, sino incluso en la memoria caché.

Answer 3

Puede usar dos variables temporales y compararlas para cada método. Me gusta esto :

[código] largo startTime = System.currentTimeMilliseconds ();

// ejecuta algo 1 aquí

long endTime = System.currentTimeMilliseconds ();

long elapsedTimeAlgo1 = endTime – startTime

[/código]
Haga lo mismo para su segundo algo y compare los dos valores de elapsedTime.

PD. ¡Esto supone que estás ejecutando los dos algo en condiciones muy similares!

Answer 4

Aunque el método de tamizado es un mejor algoritmo, puede ser más lento que el método ingenuo en su caso …

Aquí es por qué:

• El método ingenuo usa un bucle y solo lee un elemento de la matriz de primos en el bucle. El cuerpo del lazo no toca la memoria.
• El método de tamizado lee isCompose [i] en el bucle y ocasionalmente escribe en él.

No me sorprendería si los efectos de caché hicieran la versión de cribado más lenta incluso para todo el rango del tipo de datos int, especialmente porque la matriz isCompose será muy grande en comparación con la matriz primes