La presente actividad tiene por finalidad, comparar algoritmos de benchmark en dos computadores distintos, uno de cuatro núcleos y de un núcleo para realizar la comparación del tiempo de ejecución en ambas máquinas mediante el comando time, en los siguientes algoritmos:
ü Sieve de criba
ü Ackermann
ü Fibonacci
ü Bubblesort
PROCEDIMIENTO Y ANÁLISIS EN MÁQUINA DE 4 NÚCLEOS
ü Lo primero que se realizó fue ejecutar el algoritmo Sieve de criba, en lenguaje python mediante: python sievedecriba.py
Una vez ejecutado se hizo con el comando time: time python sievedecriba.py
fig. 1
ü Que arrojó lo siguiente:
ü real 0m0.032s
ü user 0m0.010s
ü sys 0m0.020s
ü Código fuente del algoritmo sieve de criba utilizado:
ü #!/usr/bin/python
ü # -*- coding: <encoding name> -*-
def sieveOfEratosthenes(n, stop=0):
l = [2] # Creamos una lista que ya contenga el numero 2, que es el unico numero par primo.
d = [] # Lista de numeros no primos
top = int(math.floor(math.sqrt(n)))+1 # Definimos hasta que numero multiplicaremos
for i in range(3,n,2): # Iniciamos un bucle desde el 3 hasta 'n', dando un salto de 2 numeros para
# recorrer solamente los numeros impares.
if i>top: # Si ya hemos multiplicado todo lo necesario...
if i not in d: # ...comprobamos que el numero actual no este en la lista de excluidos...
if stop==i: return 1 # ...si debemos detenernos nos detenemos y devolvemos 1
l.append(i) # ...y lo marcamos como primo...
else:
d = d[d.index(i)+1:] # Para aligerar memoria, redefinimos la lista de excluidos
# desde el indice siguiente al numero actual en adelante.
elif i not in d: # Si el numero actual no esta en la lista de excluidos...
if stop==i: return 1 # ...si debemos detenernos nos detenemos y devolvemos 1
l.append(i) # ...lo marcamos como primo...
for j in range(i,n,i): # y excluimos todos sus multiplos menores o iguales a 'n'
d.append(j)
else:
d = d[d.index(i)+1:] # Para aligerar memoria, redefinimos la lista de excluidos
# desde el indice siguiente al numero actual en adelante.
return l # Devuelve la lista de numeros primos <=n
def lcm(x, y):
if x==y: return x # si los dos numeros son iguales devolvemos el numero,
# puesto que mcm(5,5) es 5
# Definimos 'a' como el numero mayor y 'b' como el numero menor, solamente
# por comodidad.
a = x if x>y else y
b = x if x<y else y
# Redefinimos 'x' como el numero mayor para utilizarlo en el bucle final.
x = a
# Si 'a' es multiplo de 'b' devolvemos 'a', puesto que mcm(10,5) es 10.
if a%b==0: return a
# Definimos 'm' como el maximo numero hasta el cual se comprobara si alguno
# de los argumentos es un numero primo.
m = 1000
# Comprobamos que alguno de los dos argumentos sea menor que 'm', y llamamos
# a la funcion anterior diciendole que nos detengamos en dicho numero.
#
# La razon de esto es que la funcion de la criba de Eratostenes nos devuelve
# siempre una lista, pero si le decimos que se detenga en un numero, y ese
# numero es primo, nos devuelve un entero.
#
# Y como el minimo comun multiplo de un numero compuesto y un primo, o dos
# primos es la multiplicacion de dichos numeros, devolvemos el resultado de
# dicha multiplicacion.
if b<=m:
if type(sieveOfEratosthenes(b+1,b))==type(1): return a*b
elif a<=m:
if type(sieveOfEratosthenes(a+1,a))==type(1): return a*b
# Si no se ha hallado aun el minimo comun multiplo, iniciamos un bucle donde
# al numero mayor se le sumara su mismo numero hasta que sea multiplo del
# numero menor, que sera entonces cuando finalicemos la funcion devolviendo
# el minimo comun multiplo de 'x' e 'y'.
while a%b!=0:
a+=x
return a
ü Luego se ejecutó el algoritmo de fibonacci, en lenguaje python mediante: python fibonacci.py
Una vez ejecutado se hizo con el comando time: time python fibonacci.py
fig. 2
ü Que arrojó lo siguiente:
ü real 0m3.315s
ü user 0m0.010s
ü sys 0m0.010s
ü Código fuente del algoritmo fibonacci utilizado:
ü #! /usr/bin/env python
ü # -*- coding: utf-8 -*-
n = int(raw_input("¿Valor tope da serie? "))
print " Serie de Fibonacci "
a, b = 0, 1
while b <= n:
print b
a, b = b, a + b
ü Luego se ejecutó el algoritmo de Ackermann, en lenguaje python mediante: python ackermann.py
ü Una vez ejecutado se hizo con el comando time: time python ackermann.py
fig. 3
ü Que arrojó lo siguiente:
ü real 0m0.024s
ü user 0m0.010s
ü sys 0m0.010s
ü Código fuente del algoritmo ackermann de criba utilizado:
#!/usr/local/bin/python
def a(n,m):
if n==0:
return m+1
if m==0:
return a(n-1,1)
return a(n-1,a(n,m-1))
ü Luego se ejecutó el algoritmo de ordenamiento Bubblesort, en lenguaje python mediante: bubblesort ackermann.py
ü Una vez ejecutado se hizo con el comando time: time python bubblesort.py
fig. 4
ü Que arrojó lo siguiente:
ü real 0m0.025s
ü user 0m0.010s
ü sys 0m0.010s
ü Código fuente del algoritmo de ordenamiento bubblesort utilizado:
#!/usr/local/bin/python
# Bubble Sort
# KYA
# 7-20-08
def bubbleSort(theList, max):
for n in range(0,max): #upper limit varies based on size of the list
temp = 0
for i in range(1, max): #keep this for bounds purposes
temp = theList[i]
if theList[i] < theList[i-1]:
theList[i] = theList[i-1]
theList[i-1] = temp
No hay comentarios:
Publicar un comentario