Desafío de Algoritmos Power8

1.1 Planteamiento del problema

Problema:
Calcular la diferencia entre dos conjuntos de números.

Descripción detallada:
Dados dos archivos de texto que contienen conjuntos grandes de números (A y B), se debe determinar qué elementos están presentes en A pero no en B. El resultado debe almacenarse en un conjunto C, ordenado ascendentemente.

Especificaciones de entrada/salida:
La entrada son dos archivos (A.txt y B.txt) con un valor numérico por línea, sin orden predefinido. El archivo de salida C.txt debe contener la diferencia, un número por línea, en orden ascendente.

Consideraciones clave:
(1) Manejo eficiente de conjuntos de gran tamaño;
(2) Optimización del ordenamiento de datos voluminosos.

Ejemplo ilustrativo:
Si A = {5, 20, 10, 15, 25, 30} y B = {15, 5, 35, 25}, la diferencia A - B resulta en {10, 20, 30}.

1.2 Requisitos funcionales del programa

(1) El ejecutable debe recibir tres argumentos de línea de comandos (se recomienda que los archivos estén en el mismo directorio):
1) Ruta al archivo A.txt de entrada;
2) Ruta al archivo B.txt de entrada;
3) Ruta al archivo C.txt de salida.

(2) El archivo de salida C.txt debe cumplir:
1) Contener un valor por línea;
2) Los elementos deben estar ordenados de manera ascendente.

(3) En pantalla deben imprimirse tres líneas con el siguiente formato:
num: CANTIDAD
max: VALOR_MAXIMO
min: VALOR_MINIMO
Donde CANTIDAD es el número de elementos en la diferencia, VALOR_MAXIMO es el mayor elemento y VALOR_MINIMO el menor. Ejemplo de salida para el caso anterior:
num: 3
max: 30
min: 10

1.3 Requisitos de empaquetado

El paquete de entrega debe contener:
(1) Código fuente completo;
(2) Ejecutable precompilado, nombrado como "csdn";
(3) Script de compilación make.sh que genere el ejecutable csdn en el directorio actual;
(4) Script de ejecución run.sh que ejecute csdn tres veces consecutivas, midiendo el tiempo con el comando time;
(5) Archivo readme.txt con:
1) Instrucciones de compilación;
2) Instrucciones de ejecución;
3) Tiempo promedio de las tres ejecuciones;
4) Detalle del diseño y enfoque del algoritmo;
(6) Captura de pantalla de la ejecución de run.sh, mostrando tiempos consistentes con el readme.

1.4 Proceso de verificación

La evaluación seguirá estos pasos:
(1) Confirmar que el programa cumple los requisitos funcionales (sección 1.2);
(2) Verificar que el paquete cumple los requisitos de empaquetado (sección 1.3);
(3) Los tiempos reportados por el autor se consideran referenciales; el tiempo oficial se determinará en la verificación;
(4) Pasos de verificación:
1) Revisar la captura de pantalla para verificar la correcta salida por pantalla;
2) Ejecutar run.sh con el ejecutable csdn proporcionado y medir tiempos;
3) Eliminar csdn, ejecutar make.sh para recompilar, luego ejecutar run.sh nuevamente y medir tiempos;
4) Comparar el archivo C.txt generado con la solución de refernecia;
5) Si la salida es correcta, el tiempo promedio del paso (3) se considera el tiempo oficial.

Solución implementada

Enfoque algorítmico

Para calcular la diferencia A - B, se opta por una estrategia que minimiza el uso de memoria. En lugar de utilizar una tabla hash (como unordered_set) para almacenar B, se emplea un vector ordenado y búsqueda binaria. Esto reduce significativamente la huella de memoria, ya que un vector de enteros consume menos espacio que una tabla hash con su factor de carga y estructuras de resolución de colisiones.

El algoritmo procede:
1. Lee todos los elementos de B en un vector y los ordena.
2. Lee los elementos de A uno por uno y, para cada uno, verifica su existencia en B mediante búsqueda binaria.
3. Si un elemento de A no está en B, se agrega a un vector de resultados.
4. Finalmente, se ordena el vector de resultados.

Código fuente principal

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int NumeroEntero;

vector<NumeroEntero> calcularDiferenciaConjuntos(ifstream &archivoA, ifstream &archivoB) {
    vector<NumeroEntero> valoresB;
    NumeroEntero dato;

    while (archivoB >> dato) {
        valoresB.push_back(dato);
    }
    sort(valoresB.begin(), valoresB.end());

    vector<NumeroEntero> resultado;
    while (archivoA >> dato) {
        if (!binary_search(valoresB.begin(), valoresB.end(), dato)) {
            resultado.push_back(dato);
        }
    }
    sort(resultado.begin(), resultado.end());
    return resultado;
}

int main(int argc, char *argv[]) {
    if (argc != 4) {
        cerr << "Uso: ./ejecutable A.txt B.txt C.txt" << endl;
        return 1;
    }

    ifstream archivoA(argv[1]);
    ifstream archivoB(argv[2]);
    if (!archivoA.is_open() || !archivoB.is_open()) {
        cerr << "Error al abrir archivos de entrada." << endl;
        return 1;
    }

    ofstream archivoSalida(argv[3]);
    if (!archivoSalida.is_open()) {
        cerr << "Error al crear archivo de salida." << endl;
        return 1;
    }

    vector<NumeroEntero> diferencia = calcularDiferenciaConjuntos(archivoA, archivoB);

    cout << "num: " << diferencia.size() << endl;
    if (!diferencia.empty()) {
        cout << "max: " << *max_element(diferencia.begin(), diferencia.end()) << endl;
        cout << "min: " << *min_element(diferencia.begin(), diferencia.end()) << endl;
    }

    for (const auto &num : diferencia) {
        archivoSalida << num << "\n";
    }

    archivoA.close();
    archivoB.close();
    archivoSalida.close();
    return 0;
}

Script de compilación (make.sh)

#!/bin/bash
make clean
make all

Archivo Makefile

OBJ=csdn
CXXFLAGS=-std=c++11 -Wall -O2

all:
    g++ -o $(OBJ) main.cpp $(CXXFLAGS)

clean:
    rm -f $(OBJ) C.txt

Script de ejecución (run.sh)

#!/bin/bash
for i in 1 2 3; do
    time ./csdn A.txt B.txt C.txt
done