[Python-es] Pythoniano y c niano

[Ricardo Cárdenes]

2012/12/26 Daπid <davidmenhur en gmail.com>

Calculando todos los primos desde 2 hasta n tenemos (spoiler):
>
> http://pastebin.com/fMRH5xKK
>
>
Lo que hace este programa tiene un nombre: "la criba de Eratóstenes". Es
muy simple en cuanto a su concepción y debe de ser uno de los métodos
conceptuales más viejos para optimizar el cálculo de primos (al menos los
documentados).


> Este programa tarda 0.3 s en calcular los primos hasta 15 000, y 13 s
> en encontrar los 13 843 primos menores que 150 000. Tu versión tarda
> unos 3 segundos para el primer caso.
>
> El proceso se puede encapsular más. Podemos echar mano de la
> programación funcional y hacer que isprime devuelva por defecto True,
> salvo cuando vea que el número es compuesto, en cuyo caso devolverá
> False.
>
> http://pastebin.com/gnFrcpYC
>
> Con esto, hemos reducido el tiempo de cálculo a la mitad.
>

Em... No sé de dónde sacas esa idea. El segundo listado es equivalente al
primero, abstrayendo el test de primalidad en una función aparte. Como
Python no soporta funciones "inline", esto introduce una llamada a función,
con lo que, intuitivamente, debería ser ligeramente más lento. Y lo es: el
mejor tiempo de ejecución (para primos hasta 15000) en mi máquina es de
125ms para tu primera propuesta y de unos 143ms para el segundo.

Ten en cuenta que lo único que estás ahorrando son unas pocas operaciones
rápidas que se ejecutan en tiempo despreciable. Lo que más influye en el
tiempo de ejecución son el bucle en sí y el append, que se ejecuta sólo
para algo más del 11% de los números (de esos 15000).

De hecho, este otro listado, que es más compacto, se ejecuta en básicamente
el mismo tiempo que el primer intento, aún descomponiéndose en menos
instrucciones básicas:

http://pastebin.com/vQ0eLPAZ
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://mail.python.org/pipermail/python-es/attachments/20121226/4fb64e07/attachment.html>