1

Tengo el siguiente código en Python en el cual quiero que ingresando un número muy grande, identifique si es primo o no, pero me di cuenta que no es del todo eficiente ya que no me da exactamente el resultado esperado, o al menos no sé como hacer que cada hilo haga algo diferente en cuanto al número. Además el código también mide el tiempo de ejecución.

from threading import Thread
import time

inicio = time.time()
def primo_concurrente(n):
    for i in range(2,int(n)):
        if (n%i) == 0:
            print("no primo")
    print("primo")

hilo_uno = Thread(target=primo_concurrente(21474836/4))
hilo_dos = Thread(target=primo_concurrente((21474836/4)*2))
hilo_tres = Thread(target=primo_concurrente((21474836/4)*3))
hilo_cuatro = Thread(target=primo_concurrente((21474836/4)*4))
hilo_uno.start()
hilo_dos.start()
hilo_tres.start()
hilo_cuatro.start()

fin = time.time()
print("concurrente: "+str(fin-inicio))
6
  • 1
    Parece que intentas segmentar en cuatro partes el número de modo que cada Thread revise un rango. No puedes usar una simple división para eso, pues si el número es primo, no será divisible.
    – Candid Moe
    el 9 oct. 2022 a las 22:01
  • exactamente, pero no se como mas hacer para que cada hilo haga algo diferente sobre el número
    – Wiska
    el 9 oct. 2022 a las 22:25
  • La mayoría de las implementaciones de Python sólo ejecutan un thread a la vez, incluso en máquinas multi-core. Dividir el cálculo en múltiples thread no lo hará más corto que un single thread.
    – Candid Moe
    el 9 oct. 2022 a las 22:36
  • Siempre escucho hacerlo multi thread en Python, no lo hará más rápido o más corto. Cierto, toda la razón. Pero no se trata de hacerlo más rápido o más corto, se trata de entender el concepto de hilos y su uso. Si el lenguaje lo permite, se implementa. Si es una falacia hacer uso de hilos en Python, porque será igual que usarlo sin hilos, entonces no debieron implementar esa característica, cierto? el 10 oct. 2022 a las 7:17
  • Para lograr el objetivo, debes calcular la raíz cuadrada del valor objetivo, no la raíz exacta sino la aproximación superior entera. Luego, divides la tarea de división desde 2 hasta el valor de raíz calculado, en tantas subtareas como hilos necesites. Toma en cuenta siempre que hay una limitación sobre el máximo número representable en el lenguaje. Saludos el 10 oct. 2022 a las 7:32

1 respuesta 1

1

Tal como planteo en mi comentario, una forma de lograr lo que te propones es dividir el proceso de división del valor que estás probando entre diferentes etapas, asignando a cada hilo una parte del proceso de división en la búsqueda de un factor primo para el número dado.

Algoritmo

Un algoritmo para determinar si un valor dado es un número primo o no viene dado por la división del mismo entre todos los valores primos menores a la raíz cuadrada número dado. Esto requiere conocer de antemano los valores primos anteriores. Por lo cual, lo que usualmente se hace, sin tener estos datos previos, es dividir el valor por todos los números naturales entre 2 y la raíz cuadrada del número dado.

Se hace hasta la raiz cuadrada porque no queremos encontrar todos los divisores, queremos hallar al menos uno. Si no encontramos ningún divisor desde 2 hasta la raíz cuadrada del número, no encontraremos ninguno por encima del valor de la raíz cuadrada.

Hilos

Ahora, la tarea de división es la que vamos a repartir entre diferentes hilos, dándole de ser posible, la misma cantidad de divisiones a procesar a cada hilo. Para ello podemos dividir la cantidad de números que hay entre 2 y la raiz cuadrada del número dado entre la cantidad de hilos. Esto nos dará la cantidad de números por los cuales ha de dividir cada hilo.

Por ejemplo, si queremos determinar si el valor 101 es primo o no, primero hallamos su raiz cuadrada, la cual es aproximadamente 10. Esto es, el entero más cercano por defecto a la raíz cuadrada real.

Entonces desde 3 hasta 10 hacemos la división entre 4 hilos, quedando las tareas asignadas de la siguiente forma:

  • Primer Hilo: divide 101 entre cada número en el rango [3, 5)
  • Segundo Hilo: divide 101 entre cada número en el rango [5, 7)
  • Tercer Hilo: divide 101 entre cada número en el rango [7, 9)
  • Cuarto Hilo: divide 101 entre cada número en el rango [9, 10] (nótese que el último hilo realiza una división en la que se incluye el último valor del rango)

Entonces, nuestra función que determina si un valor es Primo o no, debe recibir el valor dado, el inicio y fin del rango para realizar las divisiones. Por ejemplo, la siguiente función realiza un división del valor recibido entre todos los números del rango [start, end] (end incluído) y devuelve un valor booleano indicando si se ha encontrado un divisor del número en dicho rango:

def is_prime(n, start, end):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  return prime

Resultado

Ahora, dado que cada hilo llevará a cabo su tarea de forma independiente, necesitamos una forma de saber si alguno de ellos ha encontrado un divisor del número o no. Existen muchas formas de obtener el resultado, yo usaré una muy sencilla que se basa en añadir a una lista el resultado de cada Hilo. Luego una simple inspección de dicha lista nos dirá si el número analizado es Primo o no.

Por ejemplo, la siguiente función recibe 5 parámetros: n, start, end, result e index. Las primeras 3 ya las conocemos, pero las 2 adicionales simplemente son una referencia a la lista para almacenar el resultado y el índice en el que pondremos dicho resultado.

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

Es practimanete igual a la primera función vista, pero en vez de devolver el resultado, lo almacenamos en una lista.

Por último, armamos todo para que nuestros hilos se encarguen de calcular si un valor es Primo, donde cada Hilo recibe una parte de las divisiones que debe hacer.

El siguiente código debería funcionar en python 3.x:

from threading import Thread
import time
import math

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

test_number = int(input("Ingrese un valor numérico para testear si es primo o no: "))

inicio = time.time()
msg_primo = "primo"
msg_no_primo = "no primo"

# si el valor introducido es 2, es primo
if test_number == 2
  print(msg_primo)
  exit(0)

# si el valor introducido es par o menor que 2, entonces no es primo.
if test_number < 2 or test_number % 2 == 0:
  print(msg_no_primo)
  exit(0)

# podemos pedir la cantidad de hilos por consola
# number_of_threads = max(int(input("Ingrese el número de hilos: ")), 1)
number_of_threads = 4

# valor hasta el cual realizaremos divisiones
upper_limit = math.floor(math.sqrt(test_number))
print(f"upper_limit: {upper_limit}")

# dividimos las tareas
task_size = math.floor((upper_limit - 3) / number_of_threads)

# inicializamos las listas para almacenar las tareas y resultados
tasks = [None] * number_of_threads
result = [None] * number_of_threads

# asignamos las tareas a cada hilo y lo iniciamos
for i in range(0, number_of_threads):
  start = 3 + (i * task_size)
  end = start + task_size - 1 if i < number_of_threads - 1 else upper_limit
  tasks[i] = Thread(target=is_prime, args=(test_number, start, end, result, i))
  tasks[i].start()

# esperamos que cada hilo termine su trabajo antes de proseguir con el resultado
for i in range(len(tasks)):
  tasks[i].join()

# mostramos el mensaje adecuado
print(msg_no_primo if False in result else msg_primo)

fin = time.time()
print(f"concurrente: {fin-inicio}")

Con esto habrás realizado la tarea usando Hilos, pero como muy bien te ha comentado @CandidMoe, esto no hará que tu tarea se ejecute más rápido, inlcuso puede pasar lo contrario.

Por ejemplo, si queremos averiguar si el siguiente número es Primo: 87178291197, usando los 4 hilos, tendremos el siguiente resultado (dependerá de la potencia del equipo en el que se ejecute):

Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 3 hasta 73816
87178291197 es divisible entre 3
dividiendo desde 73817 hasta 147630
dividiendo desde 147631 hasta 221444
dividiendo desde 221445 hasta 295259
87178291197 es divisible entre 151269
no primo
concurrente: 0.034451961517333984

Se observa que los 4 hilos han realizado su trabajo y en 2 de ellos se ha obtenido un divisor, por lo tanto el número no es primo.

Pero si ejecutamos el mismo programa con sólo 1 Hilo, el resultado se puede ver parecido al siguiente:

Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 3 hasta 295259
87178291197 es divisible entre 3
no primo
concurrente: 0.0004985332489013672

Claramente, usando 1 sólo Hilo hemos obtenido el resultado en menos tiempo. Esto es porque la función que realiza las operaciones de división ha sido optimizada para detener el bucle al momento de conseguir un divisor, y en este caso, el divisor es 3, es decir, hemos realizado sólo 1 iteración para encontrar un divisor.

En cambio al usar más de un Hilo, cada uno realiza el trabajo asignado, y aunque el primero ya ha obtenido el resultado en la primera iteración, los demás continuarán su trabajo, incrementándose el tiempo de ejecución.

Existen formas de evitar esto, pero eso estaría fuera del alcance de tu pregunta.

Espero que esto te ayude a resolver el problema.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.