Ver Mensaje Individual
  #3 (permalink)  
Antiguo 03/11/2014, 14:46
Avatar de Profesor_Falken
Profesor_Falken
 
Fecha de Ingreso: agosto-2014
Ubicación: Mountain View
Mensajes: 1.323
Antigüedad: 10 años, 4 meses
Puntos: 182
Respuesta: Primos Circulares

Buenas,

Hace poco se posteó aquí una duda similar respecto al número de threads.
http://www.forosdelweb.com/f45/canti...iempo-1111410/

Te copio aquí la respuesta:

"

Buenas,

Cada vez que creas un thread, esto tiene un importante coste a nivel de recursos, ya que cada thread tiene su propio heap y stack de ejecucion. Por eso se te queda sin memoria.

Por otro lado lo que intentas es muy ineficiente, ya que el numero de cores de tu maquina es limitado. Ten en cuenta que cuando ejecutas muchos threads sobre un mismo core, este tiene que estar cambiando de contexto constantemente (http://es.wikipedia.org/wiki/Cambio_de_contexto)

El uso de muchos threads esta bien cuando se quieren ejecutar muchas tareas concurrentes sin dejar bloqueado al usuario. Por ejemplo un servidor, si no utilizase hilos, solo podria procesar una peticion al mismo tiempo.

Sin embargo tu caso es distinto, ya que no quieres ejecutar muchas tareas sino dividir una sola muy pesada. Esta es la diferencia entre concurrencia y paralelismo.

Lo que deberias hacer para conseguir el mayor rendimiento posible es basarte en el numero de cores de tu maquina:
Código Java:
Ver original
  1. int cores = Runtime.getRuntime().availableProcessors();

Ese es el numero de thread optimo para tu calculo.

Por otro lado, debes dividir bien las tareas. No puedes asignar a cada thread de forma secuencial.
Por ejemplo si tienes 4 cores y haces esto:
Thread 1: de 1 a 250000
Thread 2: de 250001 a 500000
[...]
Es muy mala idea ya que el algoritmo de calculo de primos es de complejidad lineal (O(n)) y por tanto, a mayor valor de n mas va a tardar. Lo mejor es que vayas asignando a cada core pequenos packs a procesar y segun vayan terminando le asignas nuevos hasta terminar.

"

En el otro caso puse un ejemplo para resolverlo con lambdas.

Otra forma correcta de hacerlo sería con Executors:
http://docs.oracle.com/javase/7/docs.../Executor.html

Sin embargo, como te piden threads, te he hecho una solucion siguiendo lo que decia más arriba.
Como no has puesto todo el código y hay cosas que no compilan lo he escrito sobre la marcha, por lo que puede haber algun error, incluso de compilación, pero supongo que no te costará corregirlo.

Puedes jugar con la variable BLOQUE para conseguir el rendimiento máximo. Dependerá del número evaluado: a mayor número, mayor debería ser el tamaño del bloque.

Código Java:
Ver original
  1. public class MyThread extends Thread {
  2.  
  3.     private static final int NUMERO_EVALUADO = 1000000;
  4.  
  5.     static List<Integer> lista_salida = new ArrayList<Integer>(NUMERO_EVALUADO);
  6.  
  7.     private static final int MAX_THREADS = Runtime.getRuntime().availableProcessors();
  8.  
  9.     private static final int BLOQUE = 200;
  10.  
  11.     private final List<Integer> startNums = new ArrayList<>();
  12.  
  13.     /* Constructor de la clase */
  14.     public MyThread(String name) {
  15.         super(name);
  16.     }
  17.  
  18.     public void addStartNum(int startNum) {
  19.         this.startNums.add(startNum);
  20.     }
  21.  
  22.     /* Muestra por pantalla los elementos de una lista */
  23.     private static void mostrar_lista_elementos(List elementos) {
  24.         int i = 0;
  25.         while (i < elementos.size()) {
  26.             System.out.println(elementos.get(i));
  27.             i++;
  28.         }
  29.     }
  30.  
  31.     /* Codigo a ser ejecutado por Threads */
  32.     public void run() {
  33.         for (final Integer startNum : startNums) {
  34.             for (int i = startNum; i <= startNum + BLOQUE; i++) {
  35.                 Primo pr = new Primo(Integer.parseInt(getName()));
  36.                 int valor = pr.numero;
  37.                 if (pr.es_primo_circular()) {
  38.                     lista_salida.add(valor);
  39.                 }
  40.             }
  41.         }
  42.     }
  43.  
  44.     /* Metodo principal */
  45.     public static void main(String[] args) throws InterruptedException {
  46.  
  47.         System.out.println("Evaluando " + NUMERO_EVALUADO + " con " + MAX_THREADS + " threads");
  48.  
  49.         //Inicializa el pool de threads
  50.         MyThread[] threadPool = new MyThread[MAX_THREADS];
  51.         for (int i = 0; i < threadPool.length; i++) {
  52.             threadPool[i] = new MyThread("Thread-" + i);
  53.         }
  54.  
  55.         //Asigna porciones de valores a cada thread
  56.         int j = 0;
  57.         for (int i = 0; i < NUMERO_EVALUADO; i += BLOQUE) {
  58.             threadPool[j++].addStartNum(i);
  59.             if (j >= MAX_THREADS) {
  60.                 j = 0;
  61.             }
  62.         }
  63.  
  64.         //Lanza todos los theads
  65.         for (int i = 0; i < threadPool.length; i++) {
  66.             threadPool[i].start();
  67.         }
  68.  
  69.         //Espera que terminen todos los threads antes de terminar el principal
  70.         for (int i = 0; i < threadPool.length; i++) {
  71.             threadPool[i].join();
  72.         }
  73.  
  74.         System.out.println("Cantidad de Primos Circulares Menores a " + NUMERO_EVALUADO + ": " + lista_salida.size());
  75.     }
  76. }

Los inconvenientes son que la lista probablemente esté desordenada y también, como bien comenta Xerelo, puede que haya problemas al insertar en el ArrayList, ya que no está sincronizarlo. Si lo tienes, basta con que hagas:
Código Java:
Ver original
  1. synchronized(lista_salida){
  2.    lista_salida.add(valor);
  3. }
Si no tienes problemas, mejor no sincronices, ya que tiene un alto coste en rendimiento.

Un saludo
__________________
If to err is human, then programmers are the most human of us

Última edición por Profesor_Falken; 03/11/2014 a las 14:52