Reto Iron Hacker Mexico

digitalboy · October 15, 2011

Hola a todos!

Hace poco salio una convocatoria en internet...

En la cual uno se podia registrar gratuitamente y participar en una serie de retos. Yo, ya pase a la seguna etapa y en la proxima semana me enviaran el segundo reto.

Asi que quise compartir con ustedes estos retos, espero poder llegar a la final y asi poder compartirlos todos y mas por la oportunidades que esto representa.

Este fue el reto #1:

"Estimado contendiente Iron Hacker 2011: ¡Comenzamos! El primer reto: La suma de los primos menores a 10 es: 2 + 3 + 5 + 7 = 17. ¿Cuál es la suma de los primos menores a dos millones? La respuesta consiste en un número y el código fuente del programa con el que obtuviste dicha respuesta."

Bueno... he de ser sincero con todos ustedes la verdad no utilice vba/excel para este reto y eso es por que ahora trabajo de programador web y obviamente ahi excel ya no me es de mucha ayuda, aunque de vez en cuando lo ocupo para alguna que otra cosa especial. Utilice Python... Wow ese lenguaje es una maravilla sencillamente es muy facil de aprender y dominar, mas adelante dare una reseña del mismo.

Por el momento no subire el codigo, si no hasta tener el codigo en vba/excel de lo que hice en python.

Espero que sea de interes este reto y se animen a compartir sus macros para la solucion de este problema y asi podamos intercambiar conocimiento!

Antoni · October 15, 2011

Hola:

Aquí está mi versión del tema. Va un poco lento (100.000 números/minuto mas o menos).

Sub SumaPrimos2000000()

  Dim suma As Double, x As Long, y As Long, ce As Long

  Application.ScreenUpdating = False

  Cells.Clear

  [a1] = 2

  c = 1

  For x = 3 To 1999998 Step 2

     If x Mod 5000 = 1 Then Application.StatusBar = "Vamos por el número " & x - 1

     y = 1

     Do Until Cells(y, 1) = ""

        If x Mod Cells(y, 1) = 0 Then Exit Do

        If Cells(y, 1) > x ^ 0.5 Then

           y = c + 1

           Exit Do

        End If

        y = y + 1

     Loop

     If Cells(y, 1) = "" Then

        Cells(y, 1) = x

        c = c + 1

        suma = suma + x

     End If

  Next

  Cells.Clear

  MsgBox "Suma primos < 2.000.000 sin el 1 = " & Format(suma, "#,###")

End Sub

[/CODE]

Saludos

digitalboy · October 15, 2011

Hola Macro Antonio!

Gracias por tu interes en el tema!

Tu macro... como dices va algo lento, mas sin embargo fue mejor tu implementacion que la que yo tuve en un principio...

Esta fue mi version inicial:



Option Explicit


Sub primos01()

Dim num As String

Dim i, j As Long

Dim div As Integer

Dim ini, fin As Double


num = InputBox("Introduce un numero", "Numeros primos")

If Not IsNumeric(num) Then

   MsgBox "Solo se aceptan numeros!", vbCritical

   End

End If


ini = Timer


For i = 2 To num

   div = 0

   For j = 1 To i

      If (i Mod j) = 0 Then

         div = div + 1

      End If

   Next j


   If div = 2 Then

      Debug.Print i

   End If

Next i


fin = Timer

Debug.Print "Tiempo Requerido: " & (fin - ini) & " segundos"

End Sub

[/CODE]

Mi codigo no hace la suma de los numeros primos, solo los imprime. Solo habria que agregar un acumulador para llevar la suma.

Como veras mi primera implementacion era buena para numero pequeños, pero al meter un 10000, se hacia muy lenta a comparacion de la tuya! Estoy seguro que con mas tiempo tu hubiese podido implementar algo mejor.

Por cierto macro antonio, le hice cambios a tu macro la cual solo imprime los numeros primos y registra el tiempo consumido:

[CODE]
Sub SumaPrimos2000000()
Dim suma As Double, x As Long, y As Long, ce As Long
Application.ScreenUpdating = False
Cells.Clear
[a1] = 2
c = 1

num = InputBox("Introduce un numero", "Numeros primos")
If Not IsNumeric(num) Then
MsgBox "Solo se aceptan numeros!", vbCritical
End
End If

ini = Timer

For x = 3 To num Step 2
If x Mod 5000 = 1 Then Application.StatusBar = "Vamos por el número " & x - 1
y = 1
Do Until Cells(y, 1) = ""
If x Mod Cells(y, 1) = 0 Then Exit Do
If Cells(y, 1) > x ^ 0.5 Then
y = c + 1
Exit Do
End If
y = y + 1
Loop
If Cells(y, 1) = "" Then
Cells(y, 1) = x
c = c + 1
suma = suma + x
Debug.Print x
End If
Next
Cells.Clear

fin = Timer
Debug.Print "Tiempo Requerido: " & (fin - ini) & " segundos"
'MsgBox "Suma primos < 2.000.000 sin el 1 = " & Format(suma + 2, "#,###")
End Sub
[/CODE]

Ya veo que tu enfoque se baso en eliminar los numeros pares, muy inteligente de tu parte, asi solo manejas un millon de numeros y reduces el tiempo, aun que te falto tomar en cuenta el numero 2, el cual tambien es primo (ya lo arregle).

Mas adelante yo tambien tuve esa idea... pero aun hay otro metodo para acelerar aun mas el proceso.En el programa Python que hice, solo necesitaba alrededor de 3 a 3.5 minutos e hice uso de un diccionario para obtener la suma de los primos menores a 2,000,000

Estare subiendo todas las versiones que hice hasta llegar a la definitiva que es a la que yo llegue!

October 15, 2011

Hola! digitalboy (y Antonio).

Todos los códigos mostrados presentan buenas razones -entre otras- para ser "morosos":

a) El Application.StatusBar;

Los Debug.Print;

más allá de las características del proceso en sí mismo.

Por ejemplo el siguiente código no debería emplear más de 19/20 segundos:

Sub SumaDePrimos()
Dim Sum_of_prime As Double, i As Long, N As Long, M As Long
Dim lapse As Double

M = Application.InputBox("", "Suma de Nº primos menores a:", Type:=1)
If Not IsNumeric(M) Then Exit Sub

lapse = Timer
Sum_of_prime = 5
N = 5

Do
  i = 3
  Do While N / i >= i
    If N Mod i = 0 Then Exit Do
    i = i + 2
  Loop
  If N Mod i <> 0 Then
    Sum_of_prime = Sum_of_prime + N
  End If
  N = N + 2
Loop While N <= M

MsgBox "La suma de los Nº primos menores a " & _
  Format(M, "#,###") & " es:" & vbLf & Format(Sum_of_prime, "#,###") & _
    "." & vbLf & vbLf & "Y el tiempo empleado ha sido de:" & vbLf & _
  Timer - lapse & " seg."
End Sub[/PHP]

¿Le darían una "miradita"?...

Saludos, Cacho R.

digitalboy · October 16, 2011

Wow ese algoritmo utilizado por tu parte... se trata de un test de primalidad o algo asi o no?

Sin duda alguna si hubiese participado y enviado ese algoritmo hubieses sido uno de los poco que llegara a los 100 puntos. Yo solo llegue a 88.

Esto es lo mas que pude hacer en excel, pero no se compara a tu algoritmo:



Sub primos03()

Dim num As String

Dim i, j, suma As Long

Dim div As Integer

Dim ini, fin As Double


num = InputBox("Introduce un numero", "Numeros primos")

If Not IsNumeric(num) Then

   MsgBox "Solo se aceptan numeros!", vbCritical

   End

End If


ini = Timer

suma = 0


For i = 2 To num

   div = 0

   For j = 1 To CLng(i / 2)

      If (i Mod j) = 0 Then

         div = div + 1

      End If


      If div > 1 Then

         Exit For

      End If

   Next j


   If div = 1 Then

      suma = suma + i

   End If

Next i


fin = Timer

Debug.Print "Suma: " & suma & "Tiempo Requerido: " & (fin - ini) & " segundos"

End Sub

[/CODE]

Me siento decepcionado... por que este fue el codigo que envie en Pyhton:

[CODE]
"""
Fecha: 09/10/2011
Programador: Luis Antonio Cervantes Sanchez
Mail: lacssoft@hotmail.com
Web: http://mexcel.wordpress.com/

Nota: Utilice un algoritmo similar al empleaso a la criba de eratostenes, utilizando
python 2.3
"""

#----------Funcion Suma Primos----------#
def llave_primos(num):
dicti = {} #diccionario vacio
suma = 0 #acumulador - suma primos

#se guardan en el diccionario los valores del 2-2,000,000
for i in range(3,x+1,2):
dicti[i] = i

#se itera en las llaves del diccionario...
for i in dicti.keys():
max = num//i+1 #se obtiene el numero de multiplos de i en num
for j in range(2,max):
llave = i*j
if dicti.has_key(llave): #si existe la llave
del(dicti[llave]) #se elimina del diccionario

#se itera en los elementos restantes del diccionario (numeros primos)...
for i in dicti.values():
suma += i #se suma el valor al acumulador

return suma+2 #suma de los primos < 2,000,000

#----------Funcion Principal----------#
print '\n Introduce un numero para generar la suma de los numeros primos comprendidos en este.'
x = input('rango: ')
print llave_primos(x)
[/CODE]

El algoritmo es similar a la criba de eratostenes peroquitando los pares desde un principio para no cargarlos en el diccionario, el caso es que al tratar de guardar los datos en una coleccion o diccionario de excel, el proceso de almacenado era tardado e ineficiente, esperaba mayor desempeño. Eso me demuestra que python esta relmente optimizado!

Ahora...compare tiempos entre tu algoritmo en vba y mio en python... y no se si sentirme feliz o frustrado, ya que ejecute el script python en mi netbook con procesador intel atom con un numero de entrada de 4,000,000 y me arrojo el resultado en 1 minuto (el tiempo lo tome manualmente, por que aun no me familiarizo con las funciones de tiempo en python), mientras que el que me proporcionas Cacho se tardo 2 minutos.

Feliz... por que mi algoritmo es mas rapido que el tuyo...

Frustrado... por que si no fuera por las estructuras dinamicas que proporciona python y su optimizacion, jamas hubiese podido siquiera igualar tu aporte...

Eso me confirma que python es mas eficiente que VBA. Aun asi VBA/Excel es una de mis mejores herramientas!

Les invito a descarguen el interprete python y prueben mi script! Gracias por su interes.

En una semana estare compartiendo el reto 2 que me llegara, parece tratarse de expresiones regulares!

Antoni · October 16, 2011

Hola:

Ya estoy aquí de nuevo. He conseguido rebajar el tiempo de Cacho en un 20%.

Tiempo Cacho: 21 segundos

Tiempo Macro: 16 segundos

digitalboy dice:

con procesador intel atom con un numero de entrada de 4,000,000 y me arrojo el resultado en 1 minuto

Tiempo Macro con Pentium III a 1,68 MZ, para números primos hasta 4.000.000: 42 segundos

Quizás digitalboy deberías cuestionarte la afirmación:

Eso me confirma que python es mas eficiente que VBA

Simplemente he sustituido las celdas por un array.

Sub SumaPrimos2000000()


  Dim suma As Double, x As Long, y As Long, c As Long

  Dim p() As Long

  Application.ScreenUpdating = False


  lapse = Timer

  ReDim p(1)

  p(1) = 2

  suma = 2

  For x = 3 To 1999998 Step 2

     For y = 2 To UBound(p)

        If x Mod p(y) = 0 Then Exit For

        If p(y) > x ^ 0.5 Then

           y = UBound(p) + 1

           Exit For

        End If

     Next y


     If y = UBound(p) + 1 Then

        ReDim Preserve p(UBound(p) + 1)

        p(UBound(p)) = x

        suma = suma + x

     End If


  Next x


MsgBox "La suma de los Nº primos menores a 2.000.000 es:" & _

        vbLf & Format(suma, "#,###") & _

        "." & vbLf & vbLf & "Y el tiempo empleado ha sido de:" & vbLf & _

        Timer - lapse & " seg."



End Sub

[/CODE]

Pienso que mi algoritmo utiliza menos iteraciones, ya que solo comprueba si el número es divisible por sus anteriores primos hasta su raíz cuadrada.

Saludos.

digitalboy · October 16, 2011

Hola!

Aqui viendo la controversia generada...

Tiempo Macro con Pentium III a 1,68 MZ, para números primos hasta 4.000.000: 42 segundos

En efecto! yo tengo entendido que incluso un procesador celeron es mas rapido que un atom y no se se diga de un pentium III. El atom solo tiene la bondad de consumir menos energia y es el que utilizan casi todas las netbooks.

Ejecute tu macro mejorada y en efecto es mas rapida... la de cacho se tardo 42 segundos con una entrada de 2,000,000 y la tuya con la misma entrada se tardo 35 segundos.

Entonces dije.... bueno, hagamoslo mas interesante... dando una entrada de 8,000,000 ...

El resultado:

Python = 140 segundos!

VBA = 200 segundos!

Quizás digitalboy deberías cuestionarte la afirmación:

Eso me confirma que python es mas eficiente que VBA

En este aspecto creo que no delimite bien mi comentario. Creo que Python es mas eficiente en algunas cosas con respecto a VBA, por ejemplo en el procesamiento de archivos de texto. Y no me dejaran mentir que la escritura y lectura de archivos desde VBA es muy lenta. Y creo que ente ejemplo de los numeros primos Python demuestra el rapido acceso a sus estructuras de datos aunque si te soy sincero creo que mi algoritmo no se comporta tan natural como el propuesto por cacho, como dije: "simplemente explote las estructuras que proporciona python!"

Mi algoritmo consume memoria para crear una tabla, de la cual se iran eliminando numeros no primos y en el de cacho no, por lo tanto una posible limitante en mi programa es la memoria, ya que siento que hago un uso indescriminado de ella!

Les repito no tengo mucho que conoci python... pero en estos 2 meses de trabajo con el... hay algunas cosas que me parecen mejor que vba y otras no tanto. De echo python no tiene la instruccion With que trae VBA y la cual echo de menos, pero es facil de aprender, multiplataforma.

October 17, 2011

... Pienso que mi algoritmo utiliza menos iteraciones, ya que solo comprueba si el número es divisible por sus anteriores primos hasta su raíz cuadrada...

Tuve un poquito más de tiempo para mirar la "criatura"...

Por un lado incorporé la observación de Antonio: contrastar con los primos previos ("se me escapó la tortuga", diría nuestro prócer deportivo vernáculo: Diego Armando).

Con ello "empaté" los tiempos que Antonio mencionara.

Por otro lado, en lugar de redimensionar el vector de números primos tras cada nueva aparición de éstos, lo hago cada 500 nuevos números primos.

Otra diferencia importante es no tomar una raiz cuadrada (operación lenta) sino potenciar al cuadrado: Primos(i) * Primos(i) es mucho más veloz que Primos(i) ^ 2.

Y finalmente, estuve "jugando" con la comparación de bucles Do-Loop versus For-Next: el bucle externo me resultó más veloz con Do-Loop, mientras que el bucle interno fue más rápido con For-Next.

El resultado de todo lo anterior ha sido reducir a la mitad los tiempos de Antonio mediante el siguiente código:

Sub SumaDePrimos_02()
Dim Sum_of_prime As Double, i As Long, N As Long, M As Double
Dim lapse As Double, Primos() As Long, Q As Long

M = Application.InputBox("", "Suma de Nº primos menores o iguales a:", Type:=1)
If Not IsNumeric(M) Then Exit Sub

lapse = Timer
Sum_of_prime = 5
N = 5

ReDim Primos(500)
Primos(1) = 3: Q = 1
On Error GoTo masPrimos

Do
  For i = 1 To Q
    If N Mod Primos(i) = 0 Then Exit For
    If Primos(i) * Primos(i) > N Then
      Q = Q + 1
      Primos(Q) = N
      Sum_of_prime = Sum_of_prime + N
      Exit For
    End If
  Next i

  N = N + 2
Loop Until N > M

MsgBox "La suma de los Nº primos menores o iguales a " & Format(M, "#,##0") & _
  " es:" & vbLf & Format(Sum_of_prime, "#,##0") & "." & vbLf & vbLf & _
  "Y el tiempo empleado ha sido de:" & vbLf & Timer - lapse & " seg."
Exit Sub

masPrimos:
ReDim Preserve Primos(Q + 499)
Resume

End Sub[/PHP]

¿Le darían otra "miradita"?...

Saludos, Cacho R.

digitalboy · October 17, 2011

Wow! mis respetos cacho! Cuando sea grande, quiero ser como tu!

En efecto! he comparado tiempo... para empezar tu macro con una entrada de 2,000,000 se tarda 15! Ese codigo si que vuela!

Asi que me fui a los extremos decidi probar tu macro y mi script python con una entrada de 16,000,000. Estos fueron los resultados:

VBA = 259 segundos

Python = 295 segundos

Sin lugar a dudas me has pensar que no importa tanto el lenguaje, si no mas bien la implementacion de un buen algoritmo como los que han desarrollado Macro Antonio y tu! Pero... no me quiero quedar con la espinita... se que el codigo python que tengo... tiene un punto debil que puedo modificar en post de reduccion de tiempo y pienso hacerlo para comparar resultados y ademas me propongo tratar de pasar tu algoritmo a python.

Solo denme tiempo... por que ya entre a trabajar. Quizas el fin de semana publique las moficicaciones y tiempos de ejecucion, si me es posible, lo hare antes!

digitalboy · October 17, 2011

Bien me di una escapada...

Le comente de todo este asunto al programador que nos esta instruyendo en python, el gran Jose Luis Limas, el cual me dio el siguiente codigo:


import time

a=[1]*16000000
suma = 0
t=time.time()

for i in xrange(2,16000000) :
    if a[i]:
        j=2
        while i*j < 16000000 :
            a[i*j]=0
            j+=1

for x in [j for j in xrange(2,16000000) if a[j]] :
    suma += x

print suma
print "%f segundos" % (time.time()-t)
[/PHP]

Wow solo tardo 120 segundos (dos minutos señores)! debo confesar que el es un programador avanzado en Python y uso una lista de compresion.... yo no se que sea eso, espero dominarlo algun dia!

Tambien me comento... que en IronPython el tiempo se reduce un poco mas ya que el el probo con una entrada de 2,000,000 y solo tardo 5 segundos para el resultado! Increible!

Antoni · October 17, 2011

Hola ambos dos:

¡Efectivamente!, no es la mitad, pero casi casi, el procedimiento de Cacho ha tardado 9,7 segundos contra los 16,5 del mío.

Es curioso que no damos importancia al uso de las instrucciones, pero escoger las adecuadas en cada momento, puede suponer hasta un ahorro de 42% del total del tiempo.

digtalboy, no dudes en ir publicando los retos de Iron Hacker que me estoy divirtiendo mucho.

Saludos

October 18, 2011

... digtalboy, no dudes en ir publicando los retos de Iron Hacker que me estoy divirtiendo mucho...

¡¡¡ No podría estar más de acuerdo con esta observación de Antonio!!! pues, este tipo de planteo, "rompe" la monotonía de las consultas -cuyo fondo conceptual- se reitera sin solución de continuidad en los Foros.

Saludos para ambos.

Cacho R.