You are currently browsing the category archive for the ‘Optimización de programas’ category.

“Programación líneal” es evitar bifurcaciones condicionales como los if o switch y reemplazarlas por casos únicos. Estos casos únicos suelen contener expresiones más sofísticadas; en cambio se gana en legibilidad y testabilidad del código.

Expresiones booleanas

Como un ejemplo de introducción hablamos de las expresiones booleanas, que suelen ser un caso frecuente de aplicar un estilo “lineal”.

Podemos asignar el valor de una variable booleana medianta una bifurcación if:

bool igual;
if (a == b)
{
    igual = true;
}
else
{
    igual = false;
}

Sin embargo, todo esto podemos escribir en una sólo línea:

bool igual = a == b;

La segunda forma he bautizado “líneal”, porque el programa no tiene saltos. La misma sentencia se ejecuta en todos los casos. Por eso mejora la testabilidad del código. No necesito contemplar dos casos distintos (a igual a b y a desigual a b) para ejecutar todas las líneas del código al menos una vez.

Este ejemplo demuestra también que la programación líneal mejora la legibilidad: Varias líneas de código se acortaron a una sola. Una mejora de legibilidad no se da siempre pero a menudo.

Arriba he mencionado también, que la sustitución de saltos conlleva expresiones más complejas. Esta características observamos también en este ejemplo. La primera forma parte de una expresión “si algo es cierto, entonces haz una cosa, sino haz otra”. Esto es más intuitivo que la segunda forma, que es una ecuación booleana. Un cálculo booleano no suele presentar demasiada dificultad para un programador veterano, pero en casos más complejos puede acabar en expresiones menos intuitivas.

Linealizar con el operador ?:

Las asignaciones condicionales se puede casi siempre escribir en una sentencia. Una expresión condicional es del tipo

if (algo)
{
    mi_variable = función_de_algo;
}
else
{
    mi_variable = función_de_no_algo;
}

Por ejemplo, si quiero acotar un rango, entonces el algo sería una expresión como a < max_a. Si estoy dentro del rango, la función_de_algo sería la variable a, si estoy fuera sería max_a.

if (a < max_a)
{
    mi_variable = a;
}
else
{
    mi_variable = max_a;
}

La forma más directa de reemplazar el if sería con el operador “?:”. No todos los lenguajes ofrecen este operador, pero muchos.

mi_variable = a < max_a ? a : max_a;

Esta expresión podemos hacer todavía un poco más legible. Acotar el valor máximo de un rango corresponde a tomar el valor mínimo del valor a acotar y el límite. Por lo tanto podemos escribir el ejemplo arriba como

mi_variable = min(a, max_a);

Por supuesto, el operador ?: no ha desaparecido. Se encuentra ahora en la función min. Sin embargo, hemos ganado en testabilidad. Podemos comprobar el funcionamiento de la función min por separado y hemos simplificado la expresión que asignamos a mi_variable.

Crítica al operador ?:

Un buen observador habrá notado que realmente no hemos reemplazado el if de todo. Ya no aparece la palabra clave if, pero el operador ?: es una especie de notación abreviada de un if. El hilo de la ejecución pasa por la expresión en todos los casos, pero no ejecuta toda la expresión. Hemos mejorado la legibilidad, pero no testabilidad.

Una primera manera de trater este problema ya hemos introducido: esconder el operador ?: en una función. Entonces todavía nos queda comprobar dos casos distintos en esta nueva función, pero suele ser bastante más simple comprobar una función como min que una expresión con el operador ?: en un contexto complejo donde, además, puede haber varias bifurcaciones.

Debemos tener en cuenta que cada if multiplica el número de posibles casos por dos. Dividir los if en funciones pequeñas simplifica las pruebas. Una función con tres bifuraciones tendría 23 = 8 casos distintos. Reemplazar estos if por funciones pequeñas nos dejaría dos casos por función – que serían 2 · 3 = 6 casos.

Debemos tener en cuenta también, que el operador ?: dificulta la depuración, por lo cual sólo debería emplearse para casos simples. Al contrario de una estructura if, no tenemos un bloque de if y de else, donde podemos colocar un punto de interupción. Además, el operador ?: sólo puede eligir entre expresiones. Si queremos ejecutar sentencias de forma condicional, no lo podemos usar. Debemos usar el if.

Expresiones incondicionales

Hay casos en que podemos prescindir del operador ?: por completo y podemos usar una expresión incondicional, que sería una expresión que básicamente usa operaciones aritméticas como más y menos.

Para ello presentamos un ejemplo más complejo. Imaginemos que tenemos una tabla de base de datos y queremos imprimir los datos válidos. Una columna VALIDO contiene un uno si el registro es válido y cero en el caso contrario. El tratamiento habitual sería hacer un bucle con un if anidado. Si la columna VALIDO es distinta de cero, añadimos el registro a la salida final.

for (Registro registro : todos_los_registros) 
{
    if (registro.valido == 1)
    {
        String salida = registro.toString();
        print(salida);
    }
}

Ahora reemplazamos el if por una expresión incondicional. En su lugar aparece una expresión más compleja con una multiplicación.

for (Registro registro : todos_los_registros) 
{
    String salida = registro.toString();
    print(salida.substring(0, salida.length() * registro.valido));
}

Si el registro es vállido, entonces registro.valido vale uno y la multiplicación no altera el valor de salida.length(). La expresión

salida.substring(0, salida.length() * 1))

es igual a salida. En el caso contrario de que registro.valido vale cero, el producto salida.length() * registro.valido vale cero y llegamos a la expresión salida.substring(0, 0) – que es un string vacío. En este caso se imprime un string vacío como print("") que realmente no imprime nada.

Tenemos el mismo comportamiento que en la versión con la condición if pero sin usar una bifuración. Al mismo tiempo hemos hallado un ejemplo de como la expresión resultante se puede complicar. No es muy intuitivo multiplicar la longitud de una cadena de texto con un valor en general y mucho menos con el fin de suprimir esta cadena.

Reemplazando los saltos llegamos a menudo a una situación donde debemos decidir si prevalece la testibilidad del código o la intuición del lector del programa. Como criterio podemos usar la legibilidad del código. Si podemos reemplazar muchas líneas por pocas bien comentadas solemos ganar en general. Sin embargo, siempre debemos comprobar si no ganamos aún mucho más si pasamos el cuerpo de un bucle a una función.

Trabajar con datos erróneos

Muchas veces hace falta comprobar la validez de datos antes de usarlo. En general conviene comprobar los datos donde se usan. Es decir, una función que sólo pasa un dato como parámetro a otra función, no debería comprobar el dato en general. No obstante, algunas bibliotecas como la biblioteca estándar de C no comprueban la validez de los datos y obligan al usuario de sus funciones de comprobar la validez de datos. Una función de usuario, en cambio, debería devolver un código de error o lanzar una excepción cuando no puede seguir por un dato erróneo.

La comprobación de errores conlleva a menudo un if: “Si esto es válido, entonces hazlo.” Sin embargo, hay ocasiones en que uno puede utilizar un dato malo. Esto devolverá un resultado malo, pero puede simplificar la comprobación de errores. Por ejemplo, no hace falta comprobar la validez de una ruta en el sistema de ficheros. Si la función fopen no la encuentra, entonces devuelve un controlador nulo. Una comprobación de este controlador sería suficiente para protegerme contra cualquier error de fichero – no sólo contra una ruta de fichero errónea.

En programas que hacen un uso exhaustivo de excepciones muchas veces no hace falta ningún if. Yo puedo calcular el índice en un array sin miedo, ya que se pueden hacer todas las operaciones aritméticas con números enteros aunque los números no representen algo físico. Si el índice calculado luego no existe en el array, ya se lanzará una excepción.

Este enfoque tiende a un tiempo de cálculo menor cuando los datos son buenos, ya que se hacen menos comprobaciones. En cambio incrementa el tiempo de cálculo con datos malos, ya que se realizan cálculos que luego no tienen un resultado útil. Si consideramos un dato malo un caso excepcional, entonces ahorramos más que perdemos con cada comprobación de que podemos prescindir.

Conclusión

Hemos visto como la “programación líneal” simplifica el código y mejora su testabilidad. En general mejora también la legibilidad aunque tiene tendencia a introducir expresiones más complejas que a veces no son intuitivas y requieren un buen comentario explicativo.

Se puede conseguir un resultado optimal utilizando varias técnicas: usando el operador ?:, empleando a funciones auxiliares y finalmente comprobando la validez de los datos donde se usan. En todo caso no hay un camino de oro para la “programación líneal”. Hay que averiguar si prevalece la belleza del código o su intuitividad: un empleo de muchos if puede ser la mejor representación de la descripción humana de un algoritmo.

Lectura adicional

Introducción

Con funcioncitas me refiero a funciones de una o dos líneas, muchas veces con un cálculo muy simple, pero con un valor semántico muy potente.

Escribir una función adicional fracasa a menudo en una cierta pereza, porque hay que buscar un hueco en el fichero fuente, escribirla, en C y C++ hay que añadirlo en la cabecera, eventualmente serás capaz de escribir algún comentario de qué esta función debe hacer y todo esto para una línea de código bastante trivial. Pero esto se puede ver también de otra forma: escribes el código una vez, lo modificas diez veces y lo lees cien veces. Si tardas 99 segundos (1 minuto y 39 segundos) para escribir una función que te ahorra un segundo en la lectura, todavía ahorras tiempo.

El valor de las funciones pequeñas está en su claridad semántica, que mejora mucho la legibilidad del código – sobre todo cuando se trata de una combinación de varias funciones pequeñas. Para ilustrar esto, presento algunos ejemplos.

Copiar con punteros

Si p y q son dos punteros, entonces ¿qué hace el código de C siguiente?

while (*p++ = *q++) {}

Lo que hace es copiar el valor a que q apunta a la memoria referenciada por p. A continuación pasa ambos punteros al próximo y elemento y sigue copiando hasta que haya copiado un cero. (El valor de una asignación es el valor asignado, el cero se interpreta como un false y el bucle while termina.)

Tenemos una expresión booleana basada en cualquier tipo arbitrario que el compilador sepa amablemente interpretar como false o true y que, además, modifica las variables dentro de la expresión. A parte de tener un buen ejemplo de un uso sofisticado pero poco intuitivo del lenguaje de programación C, ¿para qué se podría utilizar un bucle así?

Pues, para copiar un string. En la biblioteca estándar de C hay una definición de strcpy similar a esta (la versión estándar devuelve un char*):

void strcpy(char *p, const char *q)
{
    while (*p++ = *q++) {}
}

Ahora la pregunta: ¿qué te parece más comprensible? ¿Una línea strcpy(p, q) o un bucle while (*p++ = *q++) {}? Técnicamente no trae ninguna ventaja llamar a la función strcpy, pero semánticamente, es decir, el significado del código es mucho más claro para el programador.

Funciones pequeñas son a menudo parte del estándar. La clase String en C# tiene un método IsNullOrEmpty. La expresión

if (!String.IsNullOrEmpty(miString))

reemplaza a

if (miString != null && miString.Length > 0)

Es lo mismo, pero el método IsNullOrEmpty deja la intención más obvia.

Acotar rangos

Un ejemplo simple. Mira el reloj cuánto tardas en contestar a la pregunta. ¿Qué representa c?

c = a < b ? a : b;

Y ahora los mismo otra vez. ¿Qué representa c?

c = min(a, b);

Esto era fácil, pero ¿qué tal con algunos niveles de anidamiento?

c = c < a ? a : (c > b ? b : c);

Esto limita c al rango [a, b]. Si no estás tan firme en el uso del operador ? : podrías escribir la línea anterior con if.

if (c < a)
{
    c = a;
}
else
{
    if (c > b)
    {
	    c = b;
	}
}

Un poco más amigable sería usar las funciones pequeñas min y max:

c = max(a, min(b, c));

Mi opción preferida sería una función

c = limitToRange(a, c, b);

donde el parámetro en medio será acotado al intervalo [a, b].

Puedes optar por hacer una pequeña función que ocupa una línea o la construción con el if anidado arriba que ocupa once líneas por cada variable que quieres acotar. Y puede haber muchas: si c es un índice de un array, entonces podrías tener la necesidad de acotarlo cada vez que accedes al array.

Algo parecido vale si quieres generar un error al recibir un índice fuera de rango. La manera directa sería escribir algo así

if (index < start || index >= end)
{
    std:ostringstream mensaje;
	mensaje << "Error de índice index = "
	        << index
			<< ". Fuera del rango ("
			<< start
			<< ", "
			<< end
			<< ").";
    throw std::exception(mensaje.str());
}

Pero igual vale la pena hasta escribir una clase de excepción propia.

if (indexOutOfRange(start, index, end))
{
    throw IndexException(start, index, end);
}

Conclusión

Funciones pequeñas aumentan considerablemente la legibilidad del código. Ayudan a reducir el número de líneas dedicadas a comprobar la calidad de los datos y dejan a consecuencia más espacio a la parte principal de una función. Para no perder velocidad en la ejecución, C++ ofrece definir estas pequeñas funciones inline.

Muchas veces las funciones pequeñas son tan generales que se pueden usar en todos los proyectos de programación. Una buena gestión debería procurar que se mantiene una biblioteca que todo el mundo en la empresa pueda usar. Como son funciones muy básicas, conviene también pensarse bien sus nombres y el espacio de nombres en que se encuentran.

Si no eres gerente sino un simple programador, entonces te recomiendo que guardes estas funciones en un fichero personal. Así puedes copiar y pegarlas en cualquier proyecto en que participas. De hecho, mantener una biblioteca personal puede facilitar tu trabajo.

Referencias

Muchas veces necesitamos reservar memoria dinámica durante la ejecución de un programa. Sin embargo, esto es un proceso relativamente lento, porque el sistema operativo debe buscar un hueco suficientemente grande en el heap, donde se almacenan los objetos dinámicos. Esto se nota, por ejemplo, cuando uno quiere reservar muchos elementos de una lista. En este artículo quiero presentar algunas propuestas, como lenguajes compilados ofrecen alternativas más veloces. Los ejemplos de código serán en C++.

Contenedores pueden instanciar varios elementos de golpe

El tamaño no importa (mucho) a la hora de reservar memoria. Es el número de veces que afecta más. Una primera posibilidad que se ofrece, por lo tanto, es reservar memoria para varios elementos de golpe. Por supuesto, esto es menos optimal respecto al uso de la memoria, pero una técnica ampliamente usado por los contenedores de la biblioteca estándar de C++ (STL).

Un contenedor puede usar el operador new[] estándar para reservar un array de, digamos, 10 elementos y luego gestionar, cuales elementos ya están en uso y cuales no. Esto puede ser relativamente complicado. Sin embargo, se puede hacer a medida para una clase contenedor y también cuando le haga falta. Por lo tanto, es una buena opción.

Sobrecargar el operador new.

Otra opción para una clase, que está ideada para instanciarse a menudo de forma dinámica, es sobrescribir el operador new (y delete) de esta clase. La implementación de este operador sobrecargado suele tener dos elementos. Primero usa el operador new global para pedir memoria al sistema operativo. Segundo, las instancias reservadas se gestionarán por unas variables estáticas de la clase. De esta forma, el depósito de elementos reservados no depende de una instancia en concreto – que es justamente lo que queremos.

El operador new global debe ser precidido por el operador :: para distinguirle del operador sobrecargado. Es decir new MiClase() llamaría al operador sobrecargado, mientras ::new MiClase() al sistema operativo. Si el operador no está sobrecargado, ambas notaciones tienen el mismo efecto. Lo mismo vale para el operador delete.

Separar reserva de memoria y construcción de instancia

La desventaja en pedir muchos elementos de golpe es que se llama el constructor por defecto para todos estos elementos aunque no se usan a priori. Pero a esto hay remedio, porque en C++ se puede separar la reserva de la memoria dinámica de la construcción de una instancia. Si, en lugar del tipo de la clase, reservo un array de char, entonces la reserva no llama a ningún constructor. Cuando quiero instanciar un nuevo elemento llamo al constructor mediante

void* operator new (std::size_t size, void* ptr) throw();

Esta versión del operador new no reserva memoria. Simplemente devuelve el puntero ptr. La manera de construir una instancia de la clase TElement en la memoria ya reservada apuntada por memory_ptr sería

*memory_ptr = * new ((TElement*) memory_ptr) TElement(*source_ptr);

Source_ptr podría ser otra instancia de la misma clase de donde copiar – es decir, la construcción arriba llamaría al constructor de copia. Los parámetros de new son tan variables como los parámetros de los constructores de la clase.

Para destruir un elemento sin liberar memoria llamo explícitamente a su destructor.


(MiClase* ptr)->~MiClase();

Reservar memoria en el stack

La forma más rápida es reservar memoria en el stack en lugar del heap. Esta reserva sucede cada vez que declaro una variable dentro de una función. Si sé que mi cadena de texto no tendrá más que mil bytes, entonces


char a[1001];

consiste en incrementar el puntero del stack, mientras


char* b = new char[1001];

en la búsqueda de un hueco lo suficientemente grande en el heap. La primera manera es muchísimo más rápida que la segunda. Teniendo en cuenta que la reserva dinámica puede, además, introducir errores de programación por olvidarse de liberar la memoria, es casi siempre preferible a ser generoso con la memoria RAM. Los ordenadores de hoy en día tienen de sobra.

Esta reserva en el stack se puede combinar con una gestión individualizada de la memoria. Dentro de mi clase puedo tener un miembro (posiblemente estático)


private: char _memory[1000];

Puedo convertirlo a un objeto de tipo TElement en la forma

TElement* element_ptr(void)
{
    return reinterpret_cast<TElement>(static_cast<char*>(_memory));
}

El static_cast no es obligatorio. Por la complejidad de la construcción conviene encapsularla en un método privado que convierte el almacén de memoria al tipo de clase requerido.

Hay implementaciones de la STL que usan esta técnica. Por ejemplo, la clase std::string contiene un búfer pequeño como miembro de la clase. Esto hace el almacenamiento de cadenas de textos cortos rápido. Si la longitud del string excede el tamaño del búfer, entonces se pide memoria dinámica.

Allocators

Los contenedores de la STL suministran otro mecanismo de cambiar la gestión de memoria mediante una clase allocator. Este allocator aparece como un parámetro en las plantillas de los contenedores. Aunque es una forma sofisticada de separar la gestión de memoria del funcionamiento del contenedor, aporta un problema nuevo: un contenedor con un allocator diferente no tiene el mismo tipo que un contendor con el allocator por defecto. Por lo tanto, dos instancias del mismo contenedor se comportan como dos contenedores distintos.

std::list<int, MiAllocator> miLista;
std::list<int> listaNormal;
listaNormal = miLista // Error: listaNormal y miLista no son de la misma clase

Sin embargo, los contenedores pueden interactuar al nivel de iteradores.

// Esto está permitido.
listaNormal.insert(listaNormal.begin(), miLista.begin(), miLista.end());

Si estás pensando en utilizar allocators personalizados, entonces considerar obligar el uso del contenedor modificado por toda la aplicación, por ejemplo utilizando un typedef que define un tipo de lista propia derivada de la STL.

Conclusión

Hemos visto varias formas de como hacer más rápida la creación de memoria dinámica. El incremento en velocidad se suele pagar por un uso menos óptimo de la memoria. Sin embargo, en la mayoría de los casos, no falta memoria. La gestión individual de la memoria es una tarea compleja y requiere cuidado. Un mal algoritmo para guardar, qué elementos reservados están en uso y cuales no, puede fácilmente acabar con la ventaja, que la administración propia de la memoria podría traer.

En C++ se puede separar la reserva de memoria de la construcción de instancias. La biblioteca STL permite utilizar gestores de memorias propias. Es una herramienta potente pero que puede traer complicaciones a la hora de mezclarla con contenedores con el gestor estándar.

Referencias

Hay una experiencia en la programación que dice

Primero hazlo funcionar, entonces hazlo rápido.

Lo que quiere decir es que no te preocupes (demasiado) sobre la velocidad con que tu programa se ejecutará a la hora de crear.

Esto viene de la experiencia que los problemas de velocidad muchas veces surgen de donde no se pueden predecir. Poco sirve optimizar un código para que corra un 30% más rápido cuando la mayor parte del tiempo no hace nada más que esperar a una conexión de red lenta. Comprar un ordenador más potente es muchas veces más barato que pagar un programador para optimizar el código. (De hecho un ordenador nuevo cuesta menos que un salario mensual.) Tampoco afecta mucho al programa entero cambiar esa sentencia SQL lenta por una más optima. Salvo en entornos concretos como el tratamiento de datos en tiempo real, la velocidad del código no es tan importante como la velocidad del programador para terminar el programa.

No obstante hay unas prácticas de programación que suben la velocidad de ejecución sin perder mucho tiempo a la hora de usarlas. Aquí presentamos algunas de ellas.

Evita llamar a las mismas funciones con los mismos parámetros. Una llamada a la misma función con los mismos parámetros suele devolver el mismo resultado. Es más rápido guardar este resultado en una variable (o constante) y usar su valor, porque en general no podemos saber si la función ejecuta un cálculo costoso en cada llamada. En el caso más rápido la función no hace otra cosa que devolver un simple valor, pero nunca va a ser más rápida que la variable. Esta regla es especialmente importante cuando su valor de retorno es usado en una condición de fin de bucle.

Es decir, en lugar de una construcción así

for (int i = 0; i < tamaño_de_mi_vector(); ++i)
{
    // Haz algo
}

usar esta práctica

const int tamaño = tamaño_de_mi_vector();
for (int i = 0; i < tamaño; ++i)
{
    // Haz algo
}

Evitar funciones con muchos parámetros. Cada parámetro incluye una copia de algo. Separa el código de una forma que minimiza el número de parámetros. Es cierto que lo óptimo por este punto de vista sería no separar el código en absoluto, pero tampoco queremos perder de la vista la velocidad del programador de entender el programa.

No devolver arrays y objetos grandes. Lo que es un objeto grande depende del lenguaje. C++ devuelve una copia de un objeto (costoso), Java y PHP devuelven nada más una referencia (rápida). Sin embargo, PHP copia los arrays. Es decir devolver un objeto que contiene un array es más rápido en PHP que devolver directamente el array. C++ permite devolver referencias a objetos también, pero el programador debe asegurar que el objeto existe después de la llamada a la función. Una manera de conseguirlo es que el valor de “retorno” es una referencia a un objeto que suministra el usuario de la función como parámetro.

// Esta devolución llama a un constructor de copia.
UnaClase una_funcion()
{
    UnaClase un_objeto;
    return un_objeto;
}

// Esta función pide como parámetro el objeto donde escribir el resultado.
// Nota el ampersand & que indica la referencia en lugar de copia.
// La función no necesita devolver ningún valor.
void otra_funcion(UnaClase& referencia_a_resultado)
{
    referencia_a_resultado = // lo que tú quieras
}

// Estas funciones se llamarían así.
// Nota que la técnica de pasar una referencia no permite declarar
// la variable constante.
const UnaClase un_valor = una_funcion();
UnaClase otro_valor;
otra_funcion(otro_valor);

Usar el incremento/decremento pre-fix en lugar de post-fix para operadores sobrecargados (en C++). Esto suele “ahorrar” dos llamadas al constructor de copia. Este tema está tratado en un artículo específico.

El lenguaje C++, como muchos otros lenguajes, tiene un operador de incremento pre-fix y post-fix. El operador pre-fix ++p tiene el mismo efecto sobre una variable entera int p como un incremento post-fix p++: el valor se incrementa en uno. La diferencia está que la expresión ++p evalúa al valor de p después del incremento (pre-fix como pre como primero), mientras la expresión p++ tiene el valor de p antes del incremento (post como después). Sin embargo, en muchas ocasiones no se hace uso de esta diferencia y simplemente se quiere añadir uno a la variable p.

No importa mucho qué operador se usa para tipos básicos, porque el compilador añade el cálculo de “más uno” en el código ejecutable donde hace falta. Sin embargo hay una diferencia importante cuando se usan operadores sobrecargados en clases. Lo mismo que vamos a demostrar aquí para un operador de incremento ++ vale también para un operador de decremento --.

Una típica implementación de un incremento sobrecargado sería algo así:

class MiClase
{
private:
    int mi_valor;
public:
    // El operador pre-fix (argumento void)
    MiClase& operator++(void)
    {
        // Increméntame internamente (también puedo usar ++mi_valor)
        mi_valor += 1;

        // Devuelve una referencia a mí mismo
        return *this;
    }

    // El operador post-fix (argumento int sin nombre)
    MiClase operator++(int)
    {
        // Guarda una copia en una instancia temporal
        MiClase temp(*this);

        // Increméntame internamente (también puedo usar ++mi_valor)
        mi_valor += 1;

        // Devuelve la copia temporal con el estado anterior
        return temp;
    }
};

A primera vista vemos que el pre-incremento es mucho más simple. Incrementa el estado de la clase y devuelve una referencia a la instancia.

El post-incremento es más complicado. Tengo que crear una copia para no perder el estado anterior que finalmente devuelvo también como copia y no como referencia. Es decir, tengo que llamar dos veces al constructor de copia cuando no necesito hacerlo para el operador pre-fix.

Por este motivo es preferible usar el operador pre-fix para incrementar y decrementar objetos. Aunque esta regla no sea necesario para variables de tipos básicos es preferible hacerlo para tener un estilo único.

La STL (Standard Template Library) de C++ ofrece dos contenedores muy similares: el famoso std::vector y la poco usada std::deque (Double Ended Queue = cola doblemente terminada). Ambos contenedores ofrecen acceso aleatorio a un bloque de memoria continuo. Es decir, son arrays.

¿Qué es la diferencia? El concepto de un vector es un array con un inicio fijo y un fin variable. Una deque es un array con tanto el inicio como el fin variable. Por eso, el contenedor deque es útil cuando quiero tener un acceso aleatorio como en un vector, pero poder insertar delante el índice cero o eliminar elementos al inicio.

Tanto el vector como la deque son contenedores de acceso aleatorio. Sin embargo, internamente tienen una diferencia importante: un vector garantiza que los elementos están guardados en una memoria continua. Es decir, puedo usar un puntero como iterador. De hecho muchas implementaciones usan punteros como iteradores sobre vectores. La deque a contrario no garantiza guardar los elementos en una memoria contigua. Se puede implementar como un vector con un puntero variable al primer elemento del array. Pero el estándar no lo impone. Se puede implementar también, por ejemplo, como dos vectores – uno creciendo hacia indices más altos, el otro creciendo hacia “abajo” para insertar elementos al inicio del contenedor.

Otra diferencia está en los elementos que se reservan de más. Ambos contenedores tienen el método size() que devuelve el número de elementos válidos en el contenedor, pero sólo vector tiene el método capacity(), que devuelve el número de elementos reservados en la memoria.

Por ejemplo, si el método size() de un vector devuelve cinco, entonces mi array aparenta tener el tamaño cinco. Si el método capacity() de la misma instancia de vector devuelve ocho, entonces habrá memoria reservada para ocho elementos. Si añado un sexto elemento al final del vector, la operación es muy rápida, ya que no hace falta reservar más memoria para el un nuevo objeto: el elemento ya existe físicamente y sólo hace falta construirlo con los datos para el nuevo elemento.

Esta reserva de memoria ayuda a mejorar la velocidad cuando añado elementos a un contenedor. Si no fuera así, el contenedor debería reservar memoria para n+1 elementos, copiar los n que ya tiene y escribir el último al final cada vez cuando añado un elemento nuevo. Por eso los contenedores de la STL pueden reservar memoria para más elementos que corresponde a su tamaño.

Se puede forzar la capacidad mínima de un vector con el método reserve(). El contenedor deque no tiene esta característica. (La deque debería tener un método reserve_front() y reserve_back()para esto, pero esto la STL no lo ofrece.)

Por lo tanto, si quiero añadir a un array ya existente un número de elementos conocidos a priori con el método push_back(), es ventajoso usar un vector. No obstante, si ya conozco el número de elementos a la hora de creación del contenedor no tengo esta limitación. Tanto el vector como la deque tienen un constructor que especifica el número de elementos iniciales. Y lógicamente puedo llamar al método resize() en cada momento para especificar el número de elementos en ambos contenedores.

Compara

std::vector vec;
vec.reserve(numero_de_elementos);
for (int i = 0; i < numero_de_elementos; ++i)
{
    vec.push_back(nuevo_elemento);
}

con

std::vector vec2;
vec2.resize(numero_de_elementos);
for (int i = 0; i < numero_de_elementos; ++i)
{
    vec2[i] = nuevo_elemento;
}

La primera versión con reserve() es más flexible cuando quiero sustituir el vector por una lista. Aún así la mayoría de los programadores usaría la segunda forma con resize() que funciona tanto para la deque como el vector.

La limitación de un vector se manifiesta cuando quiero eliminar i elementos del principio. Como su inicio es fijo y el elemento con el índice i será el nuevo con el índice 0, debo copiar todos los elementos de i a n para que ocupen el rango de índices 0 a n-i. El contenedor deque, en cambio, no necesita borrar los elementos. Simplemente sube un puntero al primer elemento en i posiciones y invalida así los elementos a borrar. Estos elementos se quedan en la memoria para ser reciclados si se añadieran nuevas elementos al principio.

La deque requiere un poco más de gestión por tener el inicio variable, pero teniendo en cuenta que la mayor parte del trabajo de un contenedor es trabajar con los elementos y no con el contenedor mismo, la diferencia es mínima. Por lo tanto, conviene optar por una deque siempre y cuando no esté asegurado que no se quieren eliminar elementos del inicio del array.

Un vector es la elección si quiero reservar un número de elementos conocido después de la creación del contenedor, ya que puedo aprovecharme del método reserve() que la deque no tiene. Sin embargo, la reserva previa de elementos se puede sustituir muchas veces por una construcción con resize().

Pero tampoco hay muchas ocasiones en que necesito añadir elementos al principio de un array. Por lo tanto no extraña que la deque es menos conocida que el vector: simplemente se necesita poco. Pero conviene saber de su existencia.

Escribe tu dirección de correo electrónico para suscribirte a este blog, y recibir notificaciones de nuevos mensajes por correo.

Únete a otros 56 seguidores

Archivos

octubre 2019
L M X J V S D
« Nov    
 123456
78910111213
14151617181920
21222324252627
28293031