¿Cómo puedo unir dos listas en menos de O(N*M)?

Answer

1. 

   davy.ai

   July 28, 2023 at 5:35 pm

   Algoritmo para unir dos tablas usando Hashing

   Para mejorar el rendimiento de la unión de dos tablas con una relación de clave primaria y clave externa, podemos usar hashing. Aquí tienes un algoritmo simple para lograrlo:

   1. Crea una tabla hash vacía con la clave externa como clave y la fila correspondiente en la segunda tabla como valor.

   2. Itera a través de la columna de clave primaria en la primera tabla.

   3. Para cada valor, verifica si existe en la tabla hash.

   4. Si existe, recupera la fila correspondiente de la segunda tabla y añádela al resultado de la unión.

   5. Si no existe, continúa con el siguiente valor.

   6. Una vez que se hayan verificado todos los valores, el resultado de la unión contendrá todas las filas de ambas tablas que tengan claves primarias y claves externas coincidentes.

   El uso de una tabla hash reduce la complejidad temporal a O(N + M) ya que solo necesitamos iterar una vez por cada tabla para construir la tabla hash y realizar la operación de unión. Esto es significativamente más rápido que el enfoque O(N*M) sugerido en la pregunta.

   Aquí tienes una implementación del algoritmo para las tablas de ejemplo proporcionadas:

   HashMap<integer, string[]=""> tablaHash = new HashMap<integer, string[]="">();
   String[] fila;
   for(int i = 0; i < tabla2.length; i++){ //iterar a través de las filas en la tabla 2
       fila = tabla2[i];
       tablaHash.put(Integer.parseInt(fila[1]), fila); //agregar fila a la tabla hash con la clave externa como clave
   }
   List<string[]> resultadoUnion = new ArrayList<string[]>();
   for(int i = 0; i < tabla1.length; i++){ //iterar a través de las filas en la tabla 1
       fila = tabla1[i];
       int claveExterna = Integer.parseInt(fila[0]);
       if(tablaHash.containsKey(claveExterna)){ //si la clave externa existe en la tabla hash
           String[] filaUnion = new String[5];
           String[] filaTabla2 = tablaHash.get(claveExterna);
           //agregar columnas de ambas tablas a la fila de unión
           filaUnion[0] = filaTabla2[0];
           filaUnion[1] = filaTabla2[1];
           filaUnion[2] = filaTabla2[2];
           filaUnion[3] = fila[1];
           filaUnion[4] = fila[2];
           resultadoUnion.add(filaUnion);
       }
   }
   

   Esta implementación asume que las tablas están representadas como arreglos de cadenas, donde cada cadena representa una fila y los valores en cada fila están separados por un delimitador (por ejemplo, una coma). El resultado de la unión se almacena en una lista de arreglos de cadenas, donde cada arreglo de cadenas representa una fila en la tabla unida.</string[]></string[]></integer,></integer,>

Comments are closed.