IDs únicas
Volvemos con los problemas de la semana. Este es uno de mis favoritos, muy útil para usar en una entrevista de trabajo si queréis poner a prueba al candidato 😉 (debería hacer una colección con este tipo de problemas, porque son simples, pero demuestran mucho de quien los resuelve; me gustan mucho!).
Pregunta: En cualquier lenguaje de programación, escribe una función UID que devuelva un ID (número) único cada vez que se ejecute.
Consideraciones: La función no puede hacer uso de datos o variables globales de ninguna forma ni aceptar parámetros. Toda su funcionalidad debe quedar encapsulada. Tampoco puede ser el método de un objeto.
Ejemplo de ejecución:
x=UID(); //x vale 1 x=UID(); //x vale 2 x=UID(); //x vale 3 /* Nota: Los números pueden o no ser secuenciales, el único requisito es que nunca se repitan. */
Expansión (para los que quieran sumar puntos extra): Escribe en cualquier lenguaje de programación, una función GUID que devuelva una función (o puntero a función en lenguajes como C++) según las especificaciones del problema anterior pero que funcionen de forma independiente.
Ejemplo de ejecución:
UID1=GUID(); UID2=GUID(); UID3=GUID(); x=UID1(); //x vale 1 x=UID1(); //x vale 2 x=UID2(); //x vale 1 x=UID1(); //x vale 3 x=UID2(); //x vale 2 x=UID1(); //x vale 4 x=UID3(); //x vale 1
*** SOLUCIÓN ***
El enunciado era sencillo pero la solución puede complicarse si no tomamos una primera decisión correcta. Erful consiguió resolverlo en Javascript (aunque no tenía Internet y no pudo responder con su código) y StormByte iba muy bien encaminado con la solución.
La primera decisión correcta e importante es la elección lenguaje de programación; en algunos lenguajes la solución es trivial… por eso es importante, cuando leemos “en cualquier lenguaje de programación”, no interpretarlo como “nuestro favorito” o “el que más dominamos”; si no “el más adecuado” para el problema.
Necesitamos un lenguaje que soporte clausuras o cálculo lambda.
Con esto, vamos con las soluciones:
Solución Simple en Javascript:
var UID = (function() { var id=0; return function() { return ++id; } })(); //=========================== var x; x=UID(); //x vale 1 x=UID(); //x vale 2 x=UID(); //x vale 3
Lo que tenemos es la creación de una función anónima que se ejecuta conforme es definida. Esta función forma la clausura que contiene a una variable id inicializada a 0. Además la función devuelve otra función que retorna e incrementa el valor de id, esta función es la que se asigna a UID, y que cada vez que se ejecuta, tiene acceso a la variable id de ámbito superior que pertenece a la clausura de la función anónima.
Con esta idea, hacer un generador de funciones UID es trivial:
Solución Expandida en Javascript:
function GUID() { var id=0; return function() { return ++id; } }; //=========================== var UID1=GUID(); var UID2=GUID(); x=UID1(); //x vale 1 x=UID1(); //x vale 2 x=UID2(); //x vale 1 x=UID1(); //x vale 3 x=UID2(); //x vale 2
La diferencia es que la función anónima de clausura original, ya no es anónima, si no que se llama GUID y se ejecuta creando una nueva clausura cada vez, devolviendo la función que incrementa y devuelve el valor de id.
En otros lenguajes de programación el planteamiento es el mismo:
Solución Expandida PHP
function GUID() { $id=0; return function() use (&$id) { return ++$id; }; } //=========================== $UID1=GUID(); $UID2=GUID(); echo $UID1(); //1 echo $UID1(); //2 echo $UID2(); //1 echo $UID1(); //3 echo $UID2(); //2
Fijaos en la sintaxis, para ejecutar UID1 y UID2 no se utiliza la sintaxis de llamada a función normal; si no que es necesario indicar que son variables: así a() != $a(). Requiere PHP >= 5.3 para funcionar.
Solución Expandida C++
#include <iostream> #include <functional> //=========================== std::function<int()> GUID() { return []()->std::function<int()> { int id=0; return [=]() mutable -> int { return ++id; }; }(); } //=========================== int main(int argc, char * argv[]) { auto UID1= GUID(); auto UID2= GUID(); std::cout << UID1() << std::endl; //1 std::cout << UID1() << std::endl; //2 std::cout << UID2() << std::endl; //1 std::cout << UID1() << std::endl; //3 std::cout << UID2() << std::endl; //2 return 0; }
Para simplificar y evitar el uso de punteros a funciones usamos el tipo function de c++11 (la última versión del estándar C++, requiere G++>=4.7). Usamos el cálculo lambda para crear la clausura necesaria y devolver la función. Si queréis aprender sobre la sintaxis del cálculo lambda en C++ está bien explicada en la documentación de referencia de MSDN.
¿Os animáis a hacer la prueba en otros lenguajes? 😉 ¿Quién nos enseña una solución en LISP o SCHEME?
5 Comentarios
Esta solución (en python) me parece interesante por lo elegante y legible que resulta en comparación con otros ejemplos como el de C++, aunque quizá se salga un poco de los límites del problema.
En lugar de devolver funciones, devolvemos callable objects, objetos “llamables” (¿flamable? estoy confundiendo a Homer), que se comportan como una función, a los efectos necesarios. GUID en este caso es el nombre de la clase y actúa de constructor, no una función, pero se podría crear una que retornase lo construido si queremos dejar eso claro, por lo que no he querido ensuciarlo más.
Una buena alternativa! Sería interesante compararla con la solución sin clases de python.
La ventaja de no usar datos externos es mantener la encapsulación y evitar que otras partes de código tengan acceso a variables que deberían ser internas. La ventaja de no usar clases y objetos es la enorme sobrecarga que supone la instanciación y las llamadas a métodos (en saltos de memoria).
Las clausuras y el cálculo lambda tienen las ventajas de lo anterior y ninguna de las desventajas. Los callable objects parecen ser algo muy parecido! Pero conceptualmente más aproximados a la programación no funcional.
Bahg, formato. A esto le falta un previsualizar xD Si te gusta como alternativa añádelo en limpio arriba.
Las etiquetas con colorines y numerado automático son [code lang=”python”] … [/code]
Btw: L85! L85 siempre ha tenido previsualizar… :rolleyes: