Reduciendo la complejidad temporal del código (tiempo máximo de ejecución es de 16000 ms)

Answer

1. 

   davy.ai

   July 31, 2023 at 10:39 am

   Optimizando la complejidad temporal del código en Java

   El código en Java proporcionado tiene como objetivo contar el número de bits establecidos (es decir, 1’s) para cada número del 1 al 200000000000000. Sin embargo, tiene una alta complejidad temporal que debe optimizarse para reducir su tiempo de ejecución, que no debe exceder los 16000 ms.

   Una forma de optimizar este código es usar operaciones a nivel de bits en lugar del método Long.bitCount() en el bucle. Las operaciones a nivel de bits son más rápidas y eficientes que usar el método bitCount() repetidamente. También podemos paralelizar el cálculo para utilizar múltiples núcleos del procesador.

   Aquí tienes una versión optimizada del código:

   import java.util.concurrent.ExecutorService;
   import java.util.concurrent.Executors;
   import java.util.concurrent.TimeUnit;
   import java.util.concurrent.atomic.AtomicLong;
   
   public class CountBits {
       private static final long MAX = 200000000000000L;
       private static final int THREADS = Runtime.getRuntime().availableProcessors();
       private static final long BLOCK_SIZE = MAX / THREADS;
   
       public static void main(String[] args) throws InterruptedException {
           ExecutorService executor = Executors.newFixedThreadPool(THREADS);
           AtomicLong count = new AtomicLong(0);
   
           for (int i = 0; i < THREADS; i++) {
               final long start = i * BLOCK_SIZE + 1;
               final long end = (i + 1) * BLOCK_SIZE;
               executor.submit(() -> {
                   long localCount = 0;
                   for (long j = start; j <= end; j++) {
                       localCount += Long.bitCount(j);
                   }
                   count.addAndGet(localCount);
               });
           }
   
           executor.shutdown();
           executor.awaitTermination(1, TimeUnit.HOURS);
   
           System.out.println(count);
       }
   }
   

   Este código divide el rango de números a contar en bloques de tamaño igual basado en el número de núcleos de CPU disponibles. Luego creamos un grupo de hilos fijo con un tamaño igual al número de núcleos para procesar cada bloque de números en paralelo.

   El código utiliza una variable AtomicLong para garantizar un acceso seguro y concurrente a la variable count. De esta manera, cada hilo puede actualizar la variable count sin causar condiciones de carrera o inconsistencias en los datos.

   Al utilizar esta versión optimizada del código, podemos reducir la complejidad temporal y lograr un mejor rendimiento que el código original.

Comments are closed.