100 valores es un número manejable, podemos guardar 100 números en la memoria de cualquier ordenador, pero 2³¹ no lo es.
Cuando se trata de averiguar cosas que faltan en un conjunto el algoritmo más simple es dimensionar un array de valores boolean con valores false (por ejemplo) con tantas posiciones como elementos tiene el conjunto completo. Conforme vayamos leyendo los elementos que sí tenemos vamos asignando el valor true al array anterior. Al final de la lectura de todos los elementos existentes hacemos una lectura de este array y los elementos que mantengan el valor false inicial son los que faltan.
Pero como dijimos antes no podemos dimensionar un array con 2³¹ elementos, así que nos olvidamos de este método. Al menos por el momento.
El método complicado
Lo que más me llama siempre la atención de tutoriales y cursos de programación es que siempre obtienen la solución correcta a la primera. Yo debo ser muy tonto porque rara vez me ocurre eso. Muy al contrario mi experiencia es que encuentro la solución, o mejor, una solución al problema a través de una serie de intentos, fallos y correcciones.
Como lo que me interesa transmitir no es sólo cómo se codifica en C++ sino, y para mí más importante, cómo se programa en cualquier lenguaje, quiero en estas entradas no solamente describir el código al que llegué en la resolución del problema sino el proceso que seguí para encontrarlo.
En este caso lo primero que pensé, por un instante sólo, fue en el método clásico que nombré anteriormente pero sabiendo de antemano que era demasiado simple para que fuera una solución del problema. No obstante hice los cálculos del principio de la entrada para saber que la premonición era cierta y el método inviable.
¿Cuál es el problema del algoritmo desechado? El espacio necesario para el almacenamiento. ¿Sobre qué deberíamos empezar a pensar? En cómo guardar la misma información (los números que vamos leyendo secuencialmente del archivo) de forma más eficiente.
Así que pensando en esto lo primero que se me ocurrió fue una solución que, a la postre, se demostró ser una elucubración mental. Sin embargo he dejado comentada la implementación al comienzo del fichero con la solución y no me resisto a comentarla.
La idea, que en principio me pareció genial, es que si los números me llegaban relativamente ordenados podría tener suficiente memoria para almacenar todos los números que iba leyendo si en vez de guardar los números individuales guardaba conjuntos de números consecutivos, de tal forma que sólo tenía que almacenar, en una estructura, el número inicial y el final del conjunto. Estos conjuntos los guardaría en una lista ordenada.
Todo esto se definiría así:
struct _extremos
{
long start,end;
};
typedef _extremos extremos;
typedef list<extremos> listaExtremos;
El código sería así:
int main() // Muy lento
{
long n;
listaExtremos lista;
extremos item;
vector<long> perdidos;
ifstream numbers("integers", ifstream::binary);
long c=0;
while (true)
{
if (++c % 1000==0) cout<<c<<" - "<<lista.size()<<endl;
numbers.read((char *)&n, sizeof(long));
if (numbers.eof()) break;
bool found=false;
for (listaExtremos::iterator it=lista.begin(); !found && (it!=lista.end()); ++it)
{
if (it->start==n+1)
{
it->start=n;
found=true;
}
else if (it->end==n-1)
{
it->end=n;
if ((++it!=lista.end()) && (it->start==n+1))
{
n=it->end;
(--it)->end=n;
lista.erase(++it);
}
found=true;
}
else if (it->start>n)
{
item.start=n; item.end=n;
lista.insert(it, item);
found=true;
}
}
if (!found)
{
item.start=n; item.end=n;
lista.push_back(item);
}
}
cout<<"Resultado:"<<endl;
n=0;
for (listaExtremos::iterator it=lista.begin(); it!=lista.end(); ++it)
{
while (n<it->start)
{
perdidos.push_back(n);
cout<< n << " , ";
n++;
}
n=it->end+1;
}
return 0;
}
El bucle externo (while) se encarga de procesar todos los números del fichero hasta que se alcanza el final de éste, momento en el que mediante una sentencia break se termina el bucle.
El bucle interno recorre la lista de conjuntos que hemos ido guardando (en principio estará vacía) y una variable booleana (found) controla el final del bucle antes de llegar al final de la lista.
Comparamos el número recién leído con el valor mínimo del conjunto que procesamos, si el número es el anterior al leído lo guardamos en este conjunto, cambiando su valor mínimo por el nuevo mínimo.
Análogamente comparamos con el valor máximo del conjunto. Si aumentamos el conjunto por su final hay que hacer una comparación adicional para ver si el conjunto aumentado es correlativo con el siguiente conjunto, esto es no hay ningún número entre ambos, en cuyo caso unimos los dos en el primer conjunto, igualando su valor máximo con el valor máximo del siguiente conjunto, y eliminamos el segundo conjunto, con lo que recuperamos memoria, que es de lo que trata este algoritmo.
En el momento en que el valor mínimo sea mayor que el número que estamos procesando no hay que continuar la búsqueda y lo que procede es crear un nuevo conjunto en el que el valor máximo y el mínimo sean iguales al número procesado e insertar el nuevo conjunto en la lista delante del conjunto comparado para que la lista se mantenga ordenada.
El final del código no implementa la solución pedida al problema sino que simplemente muestra los números perdidos obtenidos, al tiempo que los almacena en una nueva lista, en este caso es un vector de longs, recorriendo la lista con los conjuntos obtenidos y guardando los números que van desde el máximo de un conjunto hasta el mínimo del siguiente.
El método parece funcionar (no dejé terminar la ejecución) pero es tremendamente lento por la cantidad y complejidad de las comparaciones a realizar por cada número tratado además del tiempo extra en mantener la lista ordenada.
Conclusión: método inservible por ineficiente, aunque posiblemente no diera un desbordamiento de memoria que, al fin y al cabo, es la idea que tenía en mente cuando pensé esta solución. Pero en cualquier caso un precioso tiempo perdido.
Así que pensando en esto lo primero que se me ocurrió fue una solución que, a la postre, se demostró ser una elucubración mental. Sin embargo he dejado comentada la implementación al comienzo del fichero con la solución y no me resisto a comentarla.
La idea, que en principio me pareció genial, es que si los números me llegaban relativamente ordenados podría tener suficiente memoria para almacenar todos los números que iba leyendo si en vez de guardar los números individuales guardaba conjuntos de números consecutivos, de tal forma que sólo tenía que almacenar, en una estructura, el número inicial y el final del conjunto. Estos conjuntos los guardaría en una lista ordenada.
Todo esto se definiría así:
struct _extremos
{
long start,end;
};
typedef _extremos extremos;
typedef list<extremos> listaExtremos;
int main() // Muy lento
{
long n;
listaExtremos lista;
extremos item;
vector<long> perdidos;
ifstream numbers("integers", ifstream::binary);
long c=0;
while (true)
{
if (++c % 1000==0) cout<<c<<" - "<<lista.size()<<endl;
numbers.read((char *)&n, sizeof(long));
if (numbers.eof()) break;
bool found=false;
for (listaExtremos::iterator it=lista.begin(); !found && (it!=lista.end()); ++it)
{
if (it->start==n+1)
{
it->start=n;
found=true;
}
else if (it->end==n-1)
{
it->end=n;
if ((++it!=lista.end()) && (it->start==n+1))
{
n=it->end;
(--it)->end=n;
lista.erase(++it);
}
found=true;
}
else if (it->start>n)
{
item.start=n; item.end=n;
lista.insert(it, item);
found=true;
}
}
if (!found)
{
item.start=n; item.end=n;
lista.push_back(item);
}
}
cout<<"Resultado:"<<endl;
n=0;
for (listaExtremos::iterator it=lista.begin(); it!=lista.end(); ++it)
{
while (n<it->start)
{
perdidos.push_back(n);
cout<< n << " , ";
n++;
}
n=it->end+1;
}
return 0;
}
El bucle interno recorre la lista de conjuntos que hemos ido guardando (en principio estará vacía) y una variable booleana (found) controla el final del bucle antes de llegar al final de la lista.
Comparamos el número recién leído con el valor mínimo del conjunto que procesamos, si el número es el anterior al leído lo guardamos en este conjunto, cambiando su valor mínimo por el nuevo mínimo.
Análogamente comparamos con el valor máximo del conjunto. Si aumentamos el conjunto por su final hay que hacer una comparación adicional para ver si el conjunto aumentado es correlativo con el siguiente conjunto, esto es no hay ningún número entre ambos, en cuyo caso unimos los dos en el primer conjunto, igualando su valor máximo con el valor máximo del siguiente conjunto, y eliminamos el segundo conjunto, con lo que recuperamos memoria, que es de lo que trata este algoritmo.
En el momento en que el valor mínimo sea mayor que el número que estamos procesando no hay que continuar la búsqueda y lo que procede es crear un nuevo conjunto en el que el valor máximo y el mínimo sean iguales al número procesado e insertar el nuevo conjunto en la lista delante del conjunto comparado para que la lista se mantenga ordenada.
El final del código no implementa la solución pedida al problema sino que simplemente muestra los números perdidos obtenidos, al tiempo que los almacena en una nueva lista, en este caso es un vector de longs, recorriendo la lista con los conjuntos obtenidos y guardando los números que van desde el máximo de un conjunto hasta el mínimo del siguiente.
El método parece funcionar (no dejé terminar la ejecución) pero es tremendamente lento por la cantidad y complejidad de las comparaciones a realizar por cada número tratado además del tiempo extra en mantener la lista ordenada.
Conclusión: método inservible por ineficiente, aunque posiblemente no diera un desbordamiento de memoria que, al fin y al cabo, es la idea que tenía en mente cuando pensé esta solución. Pero en cualquier caso un precioso tiempo perdido.
El método que funciona: divide y vencerás
En la vida de un programador los errores no pueden conducir al desánimo porque es el pan nuestro de cada día. Si te das cuenta, sin lugar a la menor duda, que el camino que has emprendido es incorrecto muchas veces es mejor abandonarlo y comenzar de nuevo que tratar de corregir algo que está mal de base. Sobre todo si, como en este caso, el tiempo invertido es despreciable. Como mucho me costará una taza más de café.
Del desánimo surgió la nueva idea. Como son muy pocos los números que faltan parece un derroche marcar todos los que están sea de la forma que sea. ¿Qué hacer entonces?
La idea es agrupar los números en grupos de números, por ejemplo por miles (es sólo un ejemplo, no lo haremos así). Hacer una primera lectura del fichero de números, asignando el número al grupo que corresponde y contando los números que aparecen en cada grupo. El número 23.250 corresponderá al grupo 23 (comenzando por el grupo 0).
Al final casi todos los grupos tendrán todos los números (mil en el ejemplo), en los grupos que falten números aplicaremos el método clásico pero ahora sólo tendremos que reservar memoria para los números pertenecientes a los grupos incompletos.
Necesitaremos una segunda lectura del fichero de números. En esta segunda lectura si el número pertenece a un grupo completo no hacemos nada y si pertenece a un grupo incompleto lo marcamos. Como cada grupo tiene mil números reservaremos espacio para mil booleanos por cada grupo incompleto.
El número 23.250 corresponderá con la posición 250 de su grupo. Al final de la segunda lectura tendremos sin marcar los números que faltan.
Al final casi todos los grupos tendrán todos los números (mil en el ejemplo), en los grupos que falten números aplicaremos el método clásico pero ahora sólo tendremos que reservar memoria para los números pertenecientes a los grupos incompletos.
Necesitaremos una segunda lectura del fichero de números. En esta segunda lectura si el número pertenece a un grupo completo no hacemos nada y si pertenece a un grupo incompleto lo marcamos. Como cada grupo tiene mil números reservaremos espacio para mil booleanos por cada grupo incompleto.
El número 23.250 corresponderá con la posición 250 de su grupo. Al final de la segunda lectura tendremos sin marcar los números que faltan.
Cuanto más fácil sea asignar el número a su grupo más eficiente será el método. En el ejemplo del párrafo anterior elegir los grupos de 1.000 elementos hace que, para los humanos, sea muy fácil calcular el grupo y la posición dentro del grupo (el número de delante del separador de miles y el de detrás).
Pero como para los ordenadores los números no están en base 10 sino en base 2 la forma fácil para el ordenador es que los grupos sean de 2^n elementos. Yo elegí hacer grupos de 65536 (2¹⁶) números porque un long se almacena en memoria usando 4 bytes de memoria, si tomo los dos bytes que almacenan los bits más significativos del long como si fuera un entero obtendré el índice del grupo de 65536 números al que pertenece el número. Es como dividir el número por 2¹⁶ y usar el cociente pero infinitamente más rápido.
long n,c,indx;
long cn[32768];
bool *tabla[32768];
La tabla cn contendrá los contadores de números de cada grupo, ¿pero por qué dimensiono la tabla tabla para todos los grupos (32768) si he dicho que no voy a necesitar anotar los números existentes de los grupos completos? Muy sencillo, porque no estoy reservando todavía el sitio para los 65536 booleanos que necesitaré por cada grupo sino solamente la memoria que necesitaría para guardar punteros que me apunten al comienzo de cada tabla de 65536 booleanos. La mayor parte de esta tabla no contendrá ningún dato válido porque sólo reservaré la memoria y guardaré por tanto el puntero a esta memoria para los pocos grupos no completos, pero tener el array de punteros dimensionado para todos los grupos simplifica el programa y los punteros ocupan la suficiente poca memoria como para permitirnos este derroche.
unsigned short * low=(unsigned short *)&n;
short * high=(short *)low+1;
Los punteros short* low y high así definidos me van a permitir realizar la división de la que hablaba antes para asignar un número a su grupo sin realizar ninguna operación. Vamos a ver esto con un poco más de detalle:
La variable n, definida de forma normal como de tipo long, habrá reservado en alguna zona de la memoria los bytes suficientes para almacenar este tipo de dato que, aunque puede variar según el compilador que usemos, siempre serán más de los 4 bytes que nosotros necesitamos. En esta variable almacenaremos el número que leemos desde el fichero.
El operador & devuelve la dirección de memoria donde está alojada la variable n, es decir, un puntero a la variable n. El truco está en cambiar el tipo de puntero, de esta forma como una variable short ocupa 2 bytes cuando pidamos el valor de la variable a la que apunta el puntero low no va a devolver el valor de la variable n, sino sólo el número que forman los dos primeros bytes de la variable que, en el procesador de mi equipo, resultan ser los bits de menos valor de la variable y, por lo tanto, el resto de la división que nos dará la posición del número dentro del grupo. Necesitamos definir el puntero unsigned para que los valores vayan de 0 a 65.535 que es la representación que nos interesa y no de -32.768 a 32.767.
La variable high así definida apuntaría al segundo elemento de un array de shorts que empezara en la misma dirección que n que, evidentemente, resultan ser los bytes 3º y 4º de la variable n. Al acceder al valor apuntado por esta variable obtendremos el cociente de dividir n para 65.536 pero sin realizar la operación. Nos dará el índice del grupo al que pertenece el número.
Y todo ello sólo por almacenar el número en la variable n. ¡Maravilloso!
for (int i=0; i<32768; i++) cn[i]=0;
Pero como para los ordenadores los números no están en base 10 sino en base 2 la forma fácil para el ordenador es que los grupos sean de 2^n elementos. Yo elegí hacer grupos de 65536 (2¹⁶) números porque un long se almacena en memoria usando 4 bytes de memoria, si tomo los dos bytes que almacenan los bits más significativos del long como si fuera un entero obtendré el índice del grupo de 65536 números al que pertenece el número. Es como dividir el número por 2¹⁶ y usar el cociente pero infinitamente más rápido.
Los punteros y la asignación dinámica de memoria
Ya sé que prometí en la introducción que este no iba a ser un curso del lenguaje C++ sino de programación y que, por tanto, no iba a entrar en los detalles del lenguaje. Pero los punteros merecen un trato especial.
¿Por qué?
Porque es un elemento que no existe en todos los lenguajes, al menos como está implementado en C y C++, y por lo tanto quien no esté familiarizado con estos lenguajes puede perderse cuando realmente su funcionamiento es de lo más simple.
Y además porque son fantásticos y peligrosos.
En realidad no hay un tipo puntero sino infinitos. Uno por cada tipo de variable que se pueda definir (incluyendo struct y class). Pero todos ellos tienen la particularidad que lo que guardan no es un dato guardado en la memoria del ordenador sino la dirección de la memoria donde está guardado el dato.
Los que aprendimos a programar en los tiempos en los que los microprocesadores eran muy simples (como mi caso que aprendí con un Z80 de Zilog montado sobre un ordenador Sinclair ZX-81) tenemos la ventaja de tener una representación muy clara de cómo se organiza la memoria. Es como un conjunto de casillas numeradas correlativamente en las que en cada una se puede almacenar un número entero (que para mí es un byte, aunque ahora ya son cantidades de más bits).
Pues bien en una variable puntero se almacena la dirección de una de estas casillas. Luego el compilador, en función del tipo del puntero, sabe sacar el valor al que apunta el puntero cogiéndolo de esa casilla y las siguientes.
Vemos que este tipo de variables se puede usar de dos formas: refiriéndose a la dirección que guarda o al valor al que apunta. Cuando hacemos referencia a la dirección que guardan escribimos el nombre de la variable tal cual, cuando nos referimos al valor guardado en esa dirección de memoria precedemos al nombre de un asterisco (*). Los punteros que apuntan a estructuras se especifica de otra manera, pero el funcionamiento es el mismo y de momento no los voy a emplear.
Podemos saber la dirección de cualquier variable anteponiéndole el operador & que significa dirección de. Este operador devuelve un puntero del mismo tipo que la variable sobre la que se aplica. Para pensar: podemos aplicar este operador sobre una variable de tipo puntero a algo y nos devolverá un tipo puntero a puntero a algo, y así indefinidamente...
Un tipo puntero a algo se define posponiendo un asterisco al tipo al que apunte. Por ejemplo para definir una variable apuntador que apunte a un entero (el espacio después del asterisco es opcional):
int * apuntador;
Otra cosa interesante que podemos hacer con punteros es operar con ellos. Cuando sumamos a un puntero una cantidad hace que apunte a una posición de memoria que está más adelante en la memoria. Cada unidad que se incrementa un puntero hace que apunte a una posición de la memoria que está justo las posiciones que ocupa el tipo de dato al que apunta. Es decir cuando sumamos uno a un puntero apuntaría al siguiente número del mismo tipo almacenado a continuación. O dicho más simple, al siguiente elemento del array.
Y un último recurso que tiene que ver con la memoria y los punteros es el operador new y delete que permiten reservar una cantidad de memoria y liberarla después a través de la dirección del primer elemento.
Finalmente una advertencia: usar indebidamente los punteros puede provocar resultados catastróficos. Úselos con responsabilidad.
La implementación
Echemos un vistazo a la parte del programa que inicializa los datos:long n,c,indx;
long cn[32768];
bool *tabla[32768];
La tabla cn contendrá los contadores de números de cada grupo, ¿pero por qué dimensiono la tabla tabla para todos los grupos (32768) si he dicho que no voy a necesitar anotar los números existentes de los grupos completos? Muy sencillo, porque no estoy reservando todavía el sitio para los 65536 booleanos que necesitaré por cada grupo sino solamente la memoria que necesitaría para guardar punteros que me apunten al comienzo de cada tabla de 65536 booleanos. La mayor parte de esta tabla no contendrá ningún dato válido porque sólo reservaré la memoria y guardaré por tanto el puntero a esta memoria para los pocos grupos no completos, pero tener el array de punteros dimensionado para todos los grupos simplifica el programa y los punteros ocupan la suficiente poca memoria como para permitirnos este derroche.
unsigned short * low=(unsigned short *)&n;
short * high=(short *)low+1;
Los punteros short* low y high así definidos me van a permitir realizar la división de la que hablaba antes para asignar un número a su grupo sin realizar ninguna operación. Vamos a ver esto con un poco más de detalle:
La variable n, definida de forma normal como de tipo long, habrá reservado en alguna zona de la memoria los bytes suficientes para almacenar este tipo de dato que, aunque puede variar según el compilador que usemos, siempre serán más de los 4 bytes que nosotros necesitamos. En esta variable almacenaremos el número que leemos desde el fichero.
El operador & devuelve la dirección de memoria donde está alojada la variable n, es decir, un puntero a la variable n. El truco está en cambiar el tipo de puntero, de esta forma como una variable short ocupa 2 bytes cuando pidamos el valor de la variable a la que apunta el puntero low no va a devolver el valor de la variable n, sino sólo el número que forman los dos primeros bytes de la variable que, en el procesador de mi equipo, resultan ser los bits de menos valor de la variable y, por lo tanto, el resto de la división que nos dará la posición del número dentro del grupo. Necesitamos definir el puntero unsigned para que los valores vayan de 0 a 65.535 que es la representación que nos interesa y no de -32.768 a 32.767.
La variable high así definida apuntaría al segundo elemento de un array de shorts que empezara en la misma dirección que n que, evidentemente, resultan ser los bytes 3º y 4º de la variable n. Al acceder al valor apuntado por esta variable obtendremos el cociente de dividir n para 65.536 pero sin realizar la operación. Nos dará el índice del grupo al que pertenece el número.
Y todo ello sólo por almacenar el número en la variable n. ¡Maravilloso!
for (int i=0; i<32768; i++) cn[i]=0;
Inicializo el contenido de los contadores de los grupos a cero porque C++ no nos asegura que al definir una variable esta adopte ningún valor inicial sino uno aleatorio. No hace falta que inicialice la tabla de punteros porque lo haré cuando reserve memoria para los grupos que necesite directamente al valor del puntero bueno.
ifstream numbers("integers", ifstream::binary);
while (true) // 1st pass
{
numbers.read((char *)&n, sizeof(long));
if (numbers.eof()) break;
cn[*high]++;
}
El bucle que controla la primera lectura es muy parecido al bucle externo del método complicado pero en este caso el procesamiento por cada número se limita simplemente a la ejecución de la última sentencia. Como la instrucción read ha colocado el número en la variable n el puntero almacenado en la variable high apuntará al valor del índice del grupo al que pertenece el número; con lo que la última sentencia incrementa el contador del grupo al que pertenece el número que estamos procesando. ¡Impresionante que escribiendo tan poco obtengamos tantos resultados!
n=0; c=0;
for (int i=0; i<32768; i++)
{
if (cn[i]<65536)
{
tabla[i]=new bool[65536];
for (long j=0; j<65536; j++)
tabla[i][j]=false;
n++;
c+=65536-cn[i];
}
else
tabla[i]=NULL;
}
// cout << "Resultado: " << n << " bloques con " << c << " faltas" << endl;
Momento de la reserva de memoria para los grupos incompletos. Mediante un bucle recorro todos los contadores y para los grupos en los que no haya contado 65536 números reservo memoria para un array de 65536 booleanos cuya dirección guardo en el elemento del array tabla correspondiente al grupo e inicializo el array recién asignado al valor false para todos sus elementos. Si el grupo está completo guardo en el elemento del array tabla correspondiente el valor NULL que corresponde con un puntero especial a una posición de memoria no válida. Sirve para comparar si un puntero tiene una dirección buena o no.
Una pequeña observación, fijaros en la incialización de la tabla de booleanos cómo he empleado el puntero a booleanos como si fuera una tabla de booleanos.
Al final del proceso en la variable c obtendré la cantidad de números que faltan y en la variable n la cantidad de grupos en los que están repartidos. Este último dato no se necesita pero lo puse en la fase de diseño por curiosidad y ahí se quedó.
La salida de mensajes por pantalla comentadas corresponden con las informaciones que me parecen pertinentes visualizar en la fase de diseño. Cuando son pocos uso esta técnica de comentar las líneas de código implicadas, en programas más grandes esta técnica es inviable por lo que hay que usar un macro_identificador (cláusula #define del compilador) para luego, gracias a la cláusula #ifdef, compilar o no las líneas de código que sólo deben ejecutarse en la fase de pruebas de la aplicación. Por costumbre llamo a este macro_identificador DEBUG.
long *lost=new long[c];
numbers.close();
numbers.open("integers", ifstream::binary);
while (true) // 2nd pass
{
numbers.read((char *)&n, sizeof(long));
if (numbers.eof()) break;
if (tabla[*high]!=NULL)
tabla[*high][*low]=true;
}
Como ya sé cuántos números me faltan reservo la memoria para el array que los va a contener. Aunque lo emplearé después de la segunda lectura del fichero de números prefiero reservar la memoria ahora para que si no tengo suficiente memoria se detenga el programa antes ahorrándome tiempo (y nervios).
Cierro el archivo y lo vuelvo a abrir para procesarlo de nuevo. No es una manera muy elegante de posicionarnos al comienzo del archivo pero es simple y efectiva.
El bucle de la segunda lectura vuelve a ser similar al de la primera, pero esta vez el procesamiento es un pelín más largo: si el valor almacenado en el array tabla correspondiente al grupo al que pertenece el número vale NULL significa que el grupo estaba completo y no hago nada, si no marco el booleano correspondiente a la posición de este número en su grupo a true. Observad cómo empleo un array de punteros a booleanos como si fuera un array de booleanos con una dimensión más.
Ya tengo casi todo el trabajo hecho, ahora a recoger los resultados:
// cout << "Búsqueda de números..." << endl;
n=0; indx=0;
for (int i=0; i<32768; i++)
{
if (tabla[i]!=NULL)
{
for (long j=0; j<65536; j++)
{
if (!tabla[i][j])
lost[indx++]=n;
n++;
}
delete[] tabla[i];
}
else
n+=65536;
}
La variable n me va a recorrer todos los números, indx es el índice en el array lost donde tengo que almacenar el siguiente número que falte, por tanto ambos se inicializan a cero.
El procesamiento se corresponde nuevamente con un bucle que va a recorrer todos los grupos. Si el grupo está completo (puntero vale NULL) sólo tengo que sumar 65536 a la variable n porque todos esos números están presentes. Si el grupo está incompleto necesitaré un bucle anidado que recorra las 65536 posiciones del array tabla correspondiente al grupo y en las posiciones que encuentre un valor false, que indica que el número falta, guardar el número que corresponda, que tendré en la variable n, en la tabla lost incrementando el índice indx. En cada iteración de este bucle interno incrementaré en uno la variable n con lo que al final del bucle a la variable n le habremos sumado 65536 como en el caso de los grupos completos.
Al final del bucle interno, como ya no se va a emplear más el array de booleanos correspondiente a ese grupo, libero la memoria que ocupa con la sentencia delete[]. Al reservar memoria con la sentencia new es obligatorio el liberarla explícitamente porque si no se pueden quedar zonas de la memoria del ordenador inutilizadas. Normalmente los modernos sistemas operativos detectan estos olvidos al finalizar el programa pero es mejor no dar por supuesto este comportamiento y crear programas limpios que liberen todo lo que usan. Es otro inconveniente de usar punteros.
Este procesamiento no es el más eficiente. Como sabemos cuántos elementos faltan en cada grupo se podría detener el bucle interno en el momento que se hayan encontrado esos elementos. El número que falta (n) se podría calcular a partir del índice del grupo (i) y de la posición del elemento en el grupo (j) simplemente escribiendo estos valores a través de los punteros high y low, es decir lo contrario a lo que hemos hecho antes, con lo que no necesitaríamos ir incrementando la variable n. Se os queda como tarea pero me temo que el beneficio que se obtenga será inapreciable porque son pocos los grupos a los que les faltan números.
Y ahora a resolver el problema:
cin >> n;
for (int i=0; i<n; i++)
{
cin >> indx;
cout << lost[indx-1] << endl;
}
Leo el número de casos a estudio. Por cada caso leo el índice y saco el valor del array lost correspondiente a ese índice. Tengo que restar uno porque el primer elemento del array lost tiene por índice cero.
Y ya sólo queda liberar el último trozo de memoria reservada manualmente y terminar:
delete[] lost;
return 0;
Los corchetes detrás de la sentencia delete le indican al compilador que la memoria que vamos a liberar se corresponde con un array, es decir que cuando se reservó con la sentencia new se indicó una cierta cantidad de elementos contiguos para ser reservados.
Y aquí el programa completo
Y aquí el programa completo
No hay comentarios:
Publicar un comentario