BeOSmAn's Blooog

Seguro que todos los que habéis tenido matemáticas en el instituto o universidad conocéis la sucesión de Fibonacci. Y seguro que todos los que habéis hecho algún curso, módulo o carrera de informática la habéis tenido que implementar alguna vez, ¿verdad?

Lo más fácil era seguir las instrucciones del profesor e implementar, sin salirse del guión, la definición matemática de esta sucesión:

f₀ = 0
f₁ = 1
f_n = f_n-1 + f_n-2 para todo n = 2, 3, 4…

Siguiendo esto estrictamente, en C++ os quedaría:

unsigned long long
fibonacci(int value) {
  if(value == 0) {
    return 0;
  } else if(value == 1) {
    return 1;
  } else {
    return fibonacci(value - 1) + fibonacci(value - 2);
  }
}

Este algoritmo, como podréis observar, es recursivo, es decir, se llama a sí mismo con parámetros diferentes a los que se pasa inicialmente para calcular la solución.

Pero este algoritmo tiene un problema bastante más grave que el de la recursividad (que, dependiendo del número de llamadas recursivas, corremos el riesgo de desbordar la pila) y es el de la duplicidad de llamadas a la función con el mismo valor del parámetro. Es decir, ¿te has parado a pensar cuántas veces se llama a la función fibonacci(int) con el mismo parámetro? Pues te lo digo yo: para un valor inicial de 8, esta función se llama 13 veces con el 0, 21 veces con el 1, 13 veces con el 2, 8 veces con el 3, 5 veces con el 4, 3 veces con el 5, 2 veces con el 6 y 1 vez con el 7. En total 66 veces. 66 veces cuando el valor a calcular es 8. Si tenemos que calcular con el 20, la función se llama un total de ¡21 890 veces!

Digamos que esta función, implementada directamente como se define matemáticamente, es totalmente ineficiente. Probad, si queréis, a calcular el tiempo de cálculo para 20, 40, 50… si tenéis tiempo, claro.

¿Y cómo solucionarlo? Pues mediante programación dinámica. Resumiendo, se trata de reducir el problema principal en problemas más pequeños, calcular la solución para cada problema pequeño y, finalmente, aplicar las soluciones de estos problemas pequeños para solucionar el problema grande.

Para la sucesión de Fibonacci específicamente, de lo que se trata es de no tener que calcular el mismo valor cada vez que se llama a la función, sino de tener una tabla donde están los valores previamente calculados. Si, cuando se llama a esta función el valor no está calculado, se calcula, pero si lo está, se recoge directamente de la tabla evitando toda esa recursividad y cálculos innecesarios.

Una posible implementación en C++ podría quedar así:

unsigned long long
fibonacci_alt(int value) {
	// Variables estáticas con la tabla de valores precalculados.
	static unsigned long long* prev_values = new unsigned long long[value];
	static bool init = true;
	if(init) {
		// Inicializamos sólo una vez.
		for(int i = 0; i < value; i++) {
			prev_values[i] = -1;
		}
		init = false;
	}
	
	// Implementación de Fibonacci comprobando si hay algún valor precalculado.
	if(value == 0) {
		return 0;
	} else if(value == 1) {
		return 1;
	} else if(prev_values[value - 1] != -1 || prev_values[value - 2] != -1) {
		prev_values[value] = prev_values[value - 1] + prev_values[value - 2];
		return prev_values[value];
	} else {
		if(prev_values[value-1] == -1) {
			prev_values[value-1] = fibonacci_alt(value-1);
		}
		if(prev_values[value-2] == -1) {
			prev_values[value-2] = fibonacci_alt(value-2);
		}
		prev_values[value] = prev_values[value-1] + prev_values[value-2];
		return prev_values[value];
	}
}

Usando esta función, ésta sólo se ejecuta el número de veces indicado en el valor. Cierto es que usa más memoria, pero la reducción de tiempo es tan impresionante que merece la pena. De hecho, con este algoritmo, podréis calcular sin problemas la sucesión de Fibonacci para valores mayores de 200. Probad con el algoritmo anterior…

Y, ya de estar, aquí tenéis un programa para probar estos dos algoritmos con alguna funcionalidad extra, como la de la presentación de estadísticas de llamadas a las funciones y demás. Y con un fallo: con el argumento “2” produce una violación de segmento. Pero en general funciona.

Para compilarlo podéis usar el comando:

$ g++ -o fibonacci fibonacci.cpp

Y para usarlo podéis hacerlo así (o usando el comando time para calcular cuánto tarda con cada método):

$ ./fibonacci
fibonacci <number> [-a|-v|-av]
Opciones:
  -a   Usa el algoritmo alternativo.
  -v   Muestra más información en pantalla.
  -av  Usa el algoritmo alternativo mostrando más información.
$ ./fibonacci 20
6765
$

Haciendo uso de la STL de C++ y viendo que no tiene ninguna función “sencilla” de comprobación de tipos de datos, he implementado estas funciones para uso y disfrute de todo aquel que las quiera y las necesite. Con sus comentarios y todo.

Por resumir, tenemos la función T StringTo<T>(string,T) (con sus diferentes variantes) para convertir una cadena al tipo determinado en la plantilla. Por ejemplo:

int i = StringTo<int>("42",0);  // i valdrá 42

bool error;
int a = StringTo<int>("42a",-1,error);  // a valdrá -1 y error será true

float f = StringTo<float>("123.45",-1);  // f valdrá 123.45

También está la función bool StringIs<T>(string) (también con sus variantes sobrecargadas) que comprueba si el valor pasado en la cadena como parámetro es del tipo indicado en la plantilla:

cout << boolalpha << StringIs<int>("42") << endl;  // la salida será true
cout << boolalpha << StringIs<int>("42a") << endl;  // la salida será false
cout << boolalpha << StringIs<float>("42") << endl;  // la salida será true
cout << boolalpha << StringIs<float>("123.45") << endl;  // la salida será true

Finalmente tenemos la función string StringFrom<T>(T) que devuelve una cadena con el valor pasado como parámetro convertido:

string value = StringFrom<int>(42);  // "value" contendrá la cadena "42"
string bvalue = StringFrom<bool>(true,boolapha);  // "bvalue" contendrá la cadena "true"

Y, ahora ya sí, la implementación:

#include <string>
#include <sstream>

using std::string;
using std::ios_base;
using std::stringstream;

/**
 * Convierte una cadena en el tipo dado en la plantilla.
 *
 * @param string value Valor a convertir.
 * @param T defaultValue Valor por defecto en caso de error.
 * @param bool& error Esta variable se fija a true si hay error, a false si
 * todo_ está correcto.
 * @param ios_base f Si son números, se puede especificar una base de
 * conversión.
 * @return T Valor devuelto según la cadena pasada.
 */
template <typename T>
T
StringTo(const string value, T defaultValue, bool& error, ios_base& (*f)(ios_base&) = NULL) {
	stringstream iss(value);
	T result;
	if(f == NULL) {
		iss >> result;
	} else {
		iss >> f >> result;
	}
	error = iss.fail() || iss.rdbuf()->in_avail() > 0;
	return (iss.fail() || iss.rdbuf()->in_avail() > 0 ? defaultValue : result);
}

/**
 * Función sobrecargada de la anterior donde se omite el parámetro "error".
 * @see template <typename T> T StringTo(const string, T, bool&, ios_base& (*)(ios_base&));
 */
template <typename T>
T
StringTo(const string value, T defaultValue, ios_base& (*f)(ios_base&) = NULL) {
	bool result;
	return StringTo<T>(value, defaultValue, result, f);
}

/**
 * Función sobrecargada de la anterior con un "const char*" en lugar de
 * un string.
 *
 * @param const char* value Valor a convertir.
 * @param T defaultValue Valor por defecto.
 * @param ios_base& f En caso de que sea un número y haya una base de
 * conversión.
 * @return T Tipo de dato a partir de la cadena.
 */
template <typename T>
T
StringTo(const char* value, T defaultValue, ios_base& (*f)(ios_base&) = NULL) {
	return StringTo<T>(string(value),defaultValue,f);
}

/**
 * Devuelve si una cadena contiene el tipo de dato indicado en la plantilla.
 *
 * @param string value Valor a controlar.
 * @param ios_base& f En caso de que sea un número, la base de conversión.
 * @return bool True si la cadena es del tipo indicado, false en otro caso.
 */
template <typename T>
bool
StringIs(const string value, ios_base& (*f)(ios_base&) = NULL) {
	stringstream iss(value);
	T result;
	if(f == NULL) {
		iss >> result;
	} else {
		iss >> f >> result;
	}
	return !iss.fail() && iss.rdbuf()->in_avail() <= 0;
}

/**
 * Convierte un valor del tipo indicado en la plantilla a cadena de caracters.
 *
 * @param T value Valor.
 * @param ios_base& f En caso de que sea numérico se puede especificar la base
 * de conversión.
 * @return string Cadena con el valor convertido.
 */
template <typename T>
string
StringFrom(const T value, ios_base& (*f)(ios_base&) = NULL) {
	stringstream result;
	if(f != NULL) {
		result << f;
	}
	result << (T)value;
	return result.str();
}

Actualización 2012-03-07: Releyendo un poco el código y habiendo leído algo de documentación adicional, creo que quedaría más elegante si llamamos a las funciones de otra manera (con la misma implementación), por eso de simplificar. Más o menos así:

namespace string {

template <typename T> T to(const string) {…}

template <typename T> T is(const string) {…}

template <typename T> const string from(T value) {…}

}

Con lo que los ejemplos quedarían:

int i = string::to<int>("42");  // 42
bool isint = string::is<int>("42");  // true
string value = string::from<float>(123.45);  // "123.45"

Por simple elegancia , ya que la funcionalidad es la misma. Pues quizás lo implemente…

Por necesidades del servicio voy a empezar a programar en C#, así que me he leído un par de manuales y he practicado un poco con ello. Y, la verdad, no me ha convencido demasiado. Así que, por petición popular (si por una persona se le puede llamar “popular”), estas son algunas de las conclusiones que he sacado, aunque si eres muy fan de C# quizás no deberías seguir leyendo :

Declaración de tipos

Extrañamemente se usan formas diferentes para declarar lo mismo. Porque declarar una variable o un nuevo tipo de dato debería ser consistente. Por ejemplo, para declarar una variable se usa <tipo de dato> <identificador>;. En cambio, para declarar un alias de un tipo de dato (no hay nuevos tipos) se usa using <identificador> = <tipo de dato>;. Y, ya para rematar, para declarar un delegate se usa delegate <valor devuelto> <identificador> (<parámetros>);.

¿No sería más sencillo y consistente tener una sintaxis común? Por ejemplo: <tipo de dato> <descripción> <identificador>;, con lo que la declaración quedaría:

// Variable:
int i;

// Tipo de dato:
typedef int MyInt;

// Usando 'using' (sin introducir ninguna palabra reservada adicional):
using int as MyInt;

// Delegate:
delegate void(int) MyDelegate;

Con esto la sintaxis siempre es consistente. Tenemos a la izquierda los tipos y a la derecha, siempre, el nombre tanto de la variable como del tipo nuevo como del delegate (que no deja de ser un tipo nuevo).

Nuevos tipos de datos

En C#, al igual que en C++, no se pueden declarar nuevos tipos de datos. Sí, en serio. Lo que estáis pensando ahora mismo es que con typedef sí se puede… pues no. En realidad es un alias del tipo básico. En C++, este código:

typedef int myint_t;
void overloaded_function(int value);
void overloaded_function(myint_t value);  // Error de compilación.

Daría error de compilación porque las dos funciones son iguales. myint_t no es un tipo de datos nuevo, sino un alias de int. En C# ocurre lo mismo, sólo que en lugar de declarar los nuevos tipos con typedef (que no tiene esa palabra reservada) se usa using:

using myint_t = int;

class Main {
  void overloaded_funcion(int value) {...}
  void overloaded_funcion(myint_t value) {...}  // Error de compilación.
}

También se puede hacer alguna triquiñuela, como hacer una clase MyInt que herede de System.Int32. Pero ya habría que implementar ciertas cosas para que funcionase.

Los métodos y su tipo de acceso

Es bastante enrevesado el uso de virtual, override y new para controlar el polimorfismo de las clases. Por ejemplo, en el código:

class A {
	public virtual void Who() { Console.WriteLine("A"); }
}

class B : A {
	public override void Who() { Console.WriteLine("B"); }
}

class C : B {
	public new virtual void Who() { Console.WriteLine("C"); }
}

class D : C {
	public override void Who() { Console.WriteLine("D"); }
}

C c = new D();
c.Who();	// Escribe "D"; lógico ¿no?

A a = new D();
a.Who();	// ¡Escribe "B"! ¿Dónde está la lógica de funciones virtuales aquí?

Es obligatorio que en todos los métodos que se podrán sobreescribir en clases derivadas se ponga virtual; que en todos los métodos que sobreescriben se ponga override; y que si un método oculta a otro se ponga new.

¿No sería más sencillo que todos los métodos fuesen virtuales por defecto (porque cuando haces clases, lo más probable es que las vayas a heredar)? ¿No sería más lógico que cuando declaras un método con el mismo nombre en la clase base, automáticamente se sobreescriba el de la base y, en caso de querer llamar al método de la base, uses super, base o similar?

Por cierto, decidme un caso real donde se use esta funcionalidad.

El problema de la clase base frágil

En este manual se menciona el problema de la clase base frágil, que habla de que en Java podría suceder esto, teniendo en principio estas clases:

class BaseClass {
	public void CleanUp() {
		System.out.println("BaseClass.CleanUp()");
	}
}

class DerivedClass extends BaseClass {
	public void Delete() {
		System.out.println("DerivedClass.Delete()");
	}
	public void CleanUp() {
		Delete();
	}
}

public class Test {
	public static void main(String[] args) {
		BaseClass k = new DerivedClass();
		k.CleanUp();
	}
}

La salida de este programa sería:

$ javac Test.java && java Test
DerivedClass.Delete();
$

Si luego implementamos el método Delete() en la clase base de esta forma:

class BaseClass {
	public void CleanUp() {
		System.out.println("BaseClass.CleanUp()");
	}
	public void Delete() {
		System.out.println("Delete all the world!");
	}
}

Según el manual, ¡podríamos borrar el mundo!

Esto sería un verdadero problema… si existiese. Pero es muy fácil comprobar que no se produce. La salida con la clase modificada es la misma que sin ella. Sólo usando super.Delete() se podría borrar el mundo.

Ámbito global o local

En C#, si una clase oculta un espacio de nombres, para acceder a dicho espacio introduce una nueva palabra que no está reservada, pero que hay que recordar: global. Por ejemplo:

class Main {

  public class System {}

  static void Main(string[] args) {
    System.Console.WriteLine("¡Hola mundo!");  // Error: la clase 'System' oculta
                                               // el espacio de nombres 'System'.
    global::System.Console.WriteLine("Esto sí funciona.");
  }
}

¿No sería más sencillo, en lugar de introducir otro identificador nuevo, usar sólo el operador ::, como hace C++ o, incluso, usar el operador .?

Comportamientos extraños de las variables

Resulta que si declaras una variable de tipo delegate, esta se comporta como una lista de delegates que se llaman todos seguidos:

class Test {
	void Notify1(string text) {
		System.Console.WriteLine("Hello " + text);
	}
	void Notfiy2(string text) {
		System.Console.WriteLine("Goodbye " + text);
	}
}

Test test = new Test();

delegate void Notifier(string text);

Notifier notifier;
notifier = new Notifier(test.Notify1);
notifier += new Notifier(test.Notify2);

notifier("Manolito");

// La salida será:
// Hello Manolito
// Goodbye Manolito

¿Nos aclaramos? ¿Notifier es una variable o es una lista de variables? Y si todos los delegates asignados devuelven algún valor, sólo se devuelve el último ejecutado. ¿Y el resto?

Recorriendo listas

C# añade el foreach, que no es más que lo que se conoce como syntactic sugar para el bucle for de toda la vida evitando que el programador use variables índice:

string[] stringArray = new string[] { /* Inicialización */ };

foreach(var s in stringArray) {
  System.Console.WriteLn(s);
}

Pero no estoy criticando ese syntactic sugar, todo lo contrario, eso me parece muy bien. Cuanto menos código se escriba y haga más cosas, mejor.

Lo que ya no me parece tan bien es que en ese bucle foreach sólo se tenga acceso a los valores de la lista a recorrer y no se tenga acceso al índice de dicha lista. Sí, simplemente a la famosa i que se omite para que el programador escriba menos código.

Y por culpa de esto, en caso de necesitarla, pues tienes que declararla fuera e incrementarla manualmente. Vamos, con en un bucle for.

Anidamiento

No se permiten métodos anidados, es decir, declaración e implementación de métodos dentro de otros métodos. Sí, venga, vale, se puede “solucionar” mediante el uso de delegates, pero eso no es permitir métodos anidados, eso es una chapuza.

Y además, ya para rematar, tampoco se permite declarar estructuras ni clases dentro de métodos. Como está orientado a objetos, pues toda declaración adicional tiene que ir dentro de la clase.

Actualización 2011-12-05: C y C++ tampoco permiten métodos anidados como me indican en un comentario. Esto lo puse porque yo los he usado para resolver algún problema, sólo que no recuerdo ni el lenguaje ni el proyecto en el que lo hice. ¿Pascal quizás?

Atributos

Los atributos del lenguaje también son otra cosa que está muy bien dentro de un lenguaje. Permiten extender la funcionalidad del compilador, por ejemplo, para hacer compilación condicional, controlar entre diferentes versiones o arquitecturas, marcar elementos como obsoletos… pero, me pregunto, ¿por qué la sintaxis no es coherente con el resto del lenguaje y hay que añadir triquiñuelas del estilo [Conditional("Debug")] al código?

Conclusión

Después de despotricar un poco toca una pequeña conclusión:

Si Microsoft tuvo la oportunidad de crear un nuevo lenguaje de programación desde cero, para ellos solos, sin que nadie se pueda meter, sin que nadie le diera lecciones, con la posibilidad de innovar, de mejorar lo que había hasta el momento ¿por qué lo ha hecho tan retorcido e incoherente? Porque sí, en serio, es retorcido. Hasta C++ —que mira que a Bjarne Stroustrup se le fue la olla cuando lo diseñó— es más consistente y coherente que C#. C# parece un batiburrilo de Java, C++ y alguna funcionalidad adicional como los delegates que más que ser un lenguaje nuevo es lo mismo de siempre con otro nombre. Y propietario, claro.

Y, bueno, de la compilación a código intermedio en lugar de a código máquina directamente ya no hablamos. Eso es una decisión que han tomado pero que tampoco es que importe demasiado. Recordemos que esta generación de código es una de las fases de compilación que se puede cambiar sin afectar a la sintaxis.

Concluyendo, a mi, personalmente, no me convence en absoluto. Pero claro, si quieres hacer un proyecto decente para sistemas Windows, no queda otra que hacerlo en C# o pelearte con los punteros en C++.

O usar Pascal .

P.D.: Yo, en realidad, soy más del lenguaje de programación D.

Puede que alguna vez en tu vida como desarrollador de software te veas en la necesidad de representar números en su forma binaria. Hay infinidad de algoritmos para ello, por eso no me voy a enrollar mucho. Aquí te muestro tres en C++:

La forma sencilla e intuitiva

template <typename T>
char*
ValueToBits(T value) {
	int length = sizeof(T)*8;
	char* result = new char[length];
	result[length] = '\0';
	for(int i = 0; i < length; i++) {
		result[length-1-i] = (value & (1 << i) ? '1' : '0');
	}
	return result;
}

Este algoritmo es fácilmente adaptable a C estándar. Basta con quitar la plantilla, sobrecargar esta función con más versiones, una por cada tipo de dato que se quiera convertir, y usar malloc() en lugar de new. Y, por supuesto, no hay que olvidarse de liberar la memoria del valor devuelto, o bien con delete[] si usas new, o bien con free() si usas malloc().

Usando std::strings

Este algoritmo es similar al anterior pero usando std::strings, con lo que evitamos el uso de char* y la reserva manual de memoria.

#include <string>

using std::string;

template <typename T>
const string
ValueToBits(T value) {
	string result;
	for(int i = 0; i < sizeof(T)*8; i++) {
		result = (value & (1 << i) ? "1" : "0") + result;
	}
	return result;
}

La forma elegante

Y ya que estamos en C++, ¿por qué no usar toda la potencia que nos proporciona la STL?

#include <bitset>

using std::bitset;

template <typename T>
const string
ValueToBits(T value) {
	return bitset<sizeof(T)*8>(value).to_string();
}

No me digáis que esta forma no es muy elegante .