Archivo de la categoría: Ingeniería del software

Entradas del blog acerca de la ingeniería del software.

Un algoritmo de generación de números pseudoaleatorios

Posted on por
Responder

números aleatorios

En la nota a pie del artículo La privacidad no existe citaba un artículo de la Wikipedia acerca de cómo generar números aleatorios mediante software. En esta entrada voy a poner un ejemplo sencillo desarrollado en Python. Obviamente Python tiene sus propias funciones para ello, pero nada nos impide desarrollar nuestra propia función.

En primer lugar veamos la teoría que hay detrás. Estos algoritmos lo que realmente generan son números pseudoaleatorios porque usan procedimientos sistemáticos. El método más empleado es el de congruencia lineal. Se eligen cuatro números enteros: un módulo m, un multiplicador a, el incremento c y la semilla x0 Estos números deben ser números enteros positivos mayores de 0. El artículo de la Wikipedia también impone que  a, c y x0 deben ser menores que m pero no encuentro ninguna razón para ello. De hecho, al final el artículo entra en contradicción al afirmar que el estándar POSIX para C define a = 1103515245 y m = 32768 Con lo que a > m

Una semilla válida la podemos obtener del reloj interno de la CPU: el RTC. En el ejemplo usaré el método time() de la librería time. Éste nos da el tiempo que ha pasado desde el tiempo Unix: el 1 de Enero de 1970. Como se puede ver, devuelve un número en coma flotante:

>>> time.time()
1487416084.126488

Como necesitamos un entero lo convertimos, el número de segundos será suficiente para el ejemplo. Sigue leyendo →

La operación módulo en teoría de números y cómo la implementan diferentes lenguajes

Posted on por
4

En informática, la operación módulo, dados dos números, D el dividendo y d el divisor, nos da el resto r de la división entera de D por d, siendo d≠0 y |r|<|d|. Aunque no parece gran cosa, aun menos teniendo en cuenta que hace décadas que las CPUs incorporan coprocesadores matemáticos capaces de hacer a gran velocidad operaciones aparentemente más relevantes como raíces o logaritmos, la realidad es que es una operación fundamental en informática: Desde la generación de tablas de hash y números aleatorios hasta la criptografía, la generación de checksums y el álgebra computacional.

Veamos como Python resuelve esta operación. Abrimos la consola de Python y mediante el operador % le pedimos el módulo con D=27 y d=13:

>>> 27%13
 1

Así es: 27 = 13 * 2 + 1

Lo mismo nos devuelve PHP:

echo 27%13;
1

Nada nuevo bajo el sol, matemáticas básicas. Probemos esto ahora:

>>> -27%13
12

Así es: -27 = 13 * (-3) + 12

Cambiando los signos de D y d:

>>> 27%-13
-12

¡¿Comorll?!?

El resultado esperado es 1:

27 = -13 * (-2) + 1

¿Por qué da -12? ¿Y PHP qué opina de todo esto?

echo 27%-13;
1

Buen chico. ¿Será que un lenguaje tan usado y prestigioso como Python no sabe dividir? ¿Por qué entonces lo escogen en tantas facultades de todo el mundo para la enseñanza? La NASA también lo usa, ¿han escogido un lenguaje que no sabe ni calcular el resto de una división entera?

Siguiendo con PHP:

echo -27%13;
-1

Habíamos visto antes que el resultado era 12 ¿PHP anda también perdido? La definición de la Wikipedia tampoco ayuda a esclarecer que está pasando. En mi opinión, esa definición es inexacta pues dice que la operación módulo calcula el resto de la división euclídea y en la división euclídea se impone la condición r ≥ 0 Cuando no se impone esa condición, y no lo hice en la definición de la operación módulo que di al iniciar esta entrada, las divisiones tendrán dos cocientes y dos residuos posibles: por defecto y por exceso. Mientras que con r ≥ 0 sólo habrá un resultado posible. Si hay un cociente q habrá otro cociente q’ cuyo valor será q + 1 y cada cociente tendrá su respectivo residuo r y r’ Con D=-27 y d=13 tendremos q=-3 y r=12 por un lado y por otro q=-2 y r=-1

-27 = 13 * (-3) + 12

-27 = 13 * (-2) + (-1)

Por lo tanto ambos lenguajes están calculando correctamente. En teoría de números siempre se escoge r ≥ 0 y algunos lenguajes, como Pascal, Scheme o Stata así lo hacen también, para estos lenguajes sí aplica la definición de la Wikipedia, pero la mayoría y los más usados van a escoger la división por exceso o por defecto. Algunos, como PHP, C o C++ escogerán siempre para el resto el signo del dividendo D mientras que otros como Python o Mathematica el del divisor d. Aparentemente para conseguir esta igualdad de signo, usarán la división por exceso o por defecto según sea necesario, aunque lo que realmente hacen es una operación más rápida. Los que usan el mismo signo que el dividendo van realmente rápido, truncan la división:

r = D – d * truncar(D / d)

La función truncar simplemente extermina todos los decimales, o dicho más fino: se redondea al número entero inmediato más cercano a 0. Esto es lo que hace PHP o C:

-1 = -27 – [13*truncar(-27 / 13)] = -27 – [13*truncar(-2.07…)] = -27 – [13*(-2)] = -27 – (-26)

Por otro lado, los que usan el signo del divisor d, usan la función floor (suelo). Esta función proporciona el número entero más pequeño inmediato o igual al número que se le pasa. De manera que por ejemplo Π quedaría en 3 y -Π en -4. Está función se expresa mediante ⌊⌋: floor(x) = ⌊x⌋

r = D – d * ⌊D / d⌋

Esto es lo que Python hace:

12 = -27 – 13[⌊-27 / 13⌋] = -27 – 13[⌊-2.07…⌋] = -27 -13[-3] = -27 + 39

Con la primera extrañeza que nos encontramos, cuando pusimos un divisor negativo, ahora sabemos qué hace Python:

-12 = 27 – (-13)*[⌊27 / -13⌋] = 27 – (-13)⌊-2.07…⌋ = 27 – (-13)*(-3) = 27 – 39

Lenguajes respetuosos con la teoría, como Pascal, hacen esto:

Si d > 0 => q = ⌊D / d⌋

Si d < 0 => q = ⌈D / d⌉

Es decir, si el divisor es negativo usan la función ceiling (techo) Dicha función da el número entero más grande inmediato o igual al número que se le pasa. De manera que Π quedaría en 4 y -Π en -3. Está función se expresa mediante ⌈⌉: ceiling(x) =⌈x⌉

Hay que tener en cuenta que no es esto lo que hacen los lenguajes que cogen el signo del divisor, es decir, no es lo mismo ⌊x⌋ que truncar(), no en el caso de números negativos. Volviendo al ejemplo D = 27 y d = -13 que en Python dio r = -12 mientras que PHP r = 1:

-12 ≠ 27 – (-13*⌈27 / -13⌉) = 27 – (-13*(-2)) = 27 – 26 = 1

Es lo que nos devolvió PHP, porque para números negativos truncar(x) equivale a ⌈x⌉ Para los positivos, en cambio, truncar(x) equivale a ⌊x⌋, por eso para D y d positivos todo lenguaje da el mismo r. Las diferencias surgen con los negativos. Veamos el caso en que ambos son negativos, D = -27 y d = -13. PHP usa truncar(), que en este caso sí equivale a ⌈⌉ :

-27 – (-13* truncar(-27 / -13) = -27 – (-13*truncar(2.07)) = -27 – (-13*2) = -27 + 26 = -1

>>> -27%-13
-1
echo -27%-13;
-1

Mientras que ⌊⌋, que ningún lenguaje la usa, daría:

-27 – (-13*⌊-27 / -13⌋) = -27 – (-13*(⌊2.07⌋) = -27 – (-13)*3 = -27 + 39 = 12

Como q = (D – r) / d Acaba resultando una ecuación sin solución entera:

(-27 – 12) / -13

Por lo tanto r ≠ 12

En la definición de división entera que di al principio introduje una «trampa» para que los resultados de PHP, Python o C fueran correctos: añadí la condición |r|<|d| En teoría de números, la división entera se define sólo para el conjunto de los naturales y la única condición es d ≠ 0 En cambio, para el conjunto de los números enteros (que incluye los naturales más los negativos), se usa la división euclídea, la cual añade la condición r ≥ 0 con el objetivo de obtener unos q y r únicos.

En mi opinión, la razón principal por la que algunos lenguajes usan la división entera también para números negativos es obtener un conjunto de r más amplio. Sin la condición r ≥ 0 se obtienen también r negativos. Con ello, por ejemplo, se consigue reducir el número de colisiones en una tabla de hash. Secundariamente, porque es más rápido el cálculo: truncar es más rápido que redondear. Sacrifican purismo matemático por fines prácticos. Además, el programador puede seguir obteniendo el resto de la división euclídea por otras vías. Puede programar su propia función con ceil() y floor(), o con floor() y truncate() si viene de microsegundos. También es más que probable que el lenguaje tenga una función para obtener dicho resto. Por ejemplo C tiene la función fmod en la librería math.h

Más Modelo y menos Controlador en el patrón MVC

Posted on por
Responder

He tenido ocasión de acceder al código de algunas aplicaciones para su desarrollo y veo un patrón que se repite con frecuencia y que demuestra que el desarrollador no está entendiendo el patrón de diseño de software Modelo Vista Controlador (MVC). Veo modelos pequeños que, a parte de la validación de los datos, poca más lógica contienen. Por otro lado y como no podía ser de otro modo, unos controladores gigantes para compensar los raquíticos modelos.

En el fondo una página web es tan solo un interfaz a la base de datos. Siendo aun más generalista: es tan solo un interfaz a un origen de datos (datasource). Ese origen de datos podría un servicio web SOAP, la API Rest de Twitter o cualquier otro, póngale imaginación. Si creamos ese interfaz, esa web, es por razones como que el usuario medio no tiene porque saber SQL ni mucho menos conocer la estructura de la base de datos, porque un XML de medio megabyte no nos resulta muy agradable a los humanos, etc. Siendo aun más generalistas podríamos decir que la inmensa mayoría de las aplicaciones, web o no, son «tan solo» eso. Por lo tanto, es la base de datos lo más importante y siendo los modelos los encargados de interactuar con ella, tienen un peso fundamental en una aplicación que pretende seguir el patrón MVC. Tema para otro artículo es como frecuentemente las bases de datos están mal diseñadas, saltándose a la torera las Formas Normales y no por optimizaciones en sitios con mucho tránsito. Esta alegría para diseñar el modelo de la base de datos la he llegado a ver incluso en personas que han recibido formación en la ingeniería de software.

Para poder dar un ejemplo de infrautilización de los modelos imaginemos una aplicación donde los usuarios, al crear o actualizar su perfil, opcionalmente pueden incluir una imagen a modo de avatar. Es obvio que es en el modelo donde deberemos validar si el fichero no excede un tamaño máximo y si es del tipo esperado: una imagen. Lo que no es tan obvio es que en el modelo también debe ir toda la lógica para tratar posibles errores manejando el fichero en el servidor. Tendremos que mover el fichero desde su ubicación temporal a la definitiva y talvez tengamos que realizar operaciones como cambiarle el nombre o crear un directorio donde alojarlo y lo que no es tan obvio es que esas operaciones también deben hacerse en el modelo evitando la tentación de sobrecargar el controlador. Si el campo «avatar», donde guardamos el nombre del fichero, no es obligatorio en la tabla, posiblemente primero guardaremos el nuevo usuario, luego realizaremos las operaciones con el fichero y si es felizmente renombrado y está en su ubicación actualizaremos la tabla con el nuevo nombre del avatar, de lo contrario informaremos al usuario de que si bien se pudo guardar su registro se produjo un error interno y no se pudo guardar la imagen que envió (por ejemplo haciendo saltar una regla de validación que no impida la inserción o actualización del usuario) En el controlador sólo haría esto o poco más:

if ($this->request->is('post')) {
    $this->User->create();
    if ($this->User->save($this->request->data)) {
        $this->Session->setFlash(__('The user has been saved'));
        $this->redirect(array('action' => 'index'));
    } else {
        $this->Session->setFlash(__('The user could not be saved. Please, try again.'));
    }
}

Este ejemplo se puede generalizar a cualquier acceso a la base de datos para crear o actualizar un registro que dependa de otro factor ajeno a la operación. Otro caso típico es al realizar complejas búsquedas en la base de datos, toda la lógica debe estar en el modelo y desde el controlador llamar a la función del modelo, si por complejidad es necesario dicha función puede estar apoyada por otras funciones «protected» o «privated» del modelo.

Toda acción CRUD (Create, Read, Update and Delete) así como otras operaciones dependientes deben estar en el modelo. Si es nuev@ en el patrón MVC, antes de poner algo en el controlador piense bien si es el lugar más adecuado. Seguir la normal general de mantener los controladores pequeños y los modelos preponderantes le ayudará a desarrollar unas aplicaciones más fáciles de mantener y modificar.

– Editado el 10/03/2012 –

Lo que aquí he expuesto no sólo aplica al MVC, no sólo al desarrollo web sino a todo el desarrollo de software, es uno de los principios básicos de la ingeniería de software. Los datos y su estructura dominan, si no están bien toda lógica que opere sobre esos datos va a ser innecesariamente más compleja. Incluso aparece listado en las reglas de la «filosofía Unix«, según Eric S. Raymond. Aunque estas normas van más allá de Unix y aplican para el desarrollo en cualquier plataforma.

No es recursivo todo lo que parece.

Posted on por
2

En la entrada anterior hablé sobre la recursividad mediante Scheme y la función de Ackermann. Hay algo curioso, o al menos a mi me sorprende, sobre Scheme y es como interpreta como iterativos algoritmos aparentemente recursivos. Como ejemplo 2 algoritmos para calcular los números de Fibonacci, uno recursivo y el otro iterativo aunque parezca recursivo. Primero recordar que estos números de definen así:

0 Si n = 0

1 Si n = 1

Fib(n – 1) + Fib(n – 2) Si n ≠ 0 y n ≠ 1

Esta definición lleva directamente a este algoritmo recursivo en Scheme:

(define (fib n)
    (cond ((= n 0) 0)
    ((= n 1) 1)
    (else (+ (fib (- n 1))
        (fib (- n 2))))))

Funciona pero es poco eficiente, la complejidad aumenta exponencialmente a medida que el número que buscamos, n, es mayor, pues se trata de recursividad en árbol. Este otro algoritmo es mucho más eficiente:

(define (fib n)
    (fib-iter 1 0 n))

(define (fib-iter a b count)
    (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

Si queremos saber el Fibonacci para 4 lo invocamos así:

(fib 4)

Y hará:

(fib 4)

(fib-iter 1 0 4)

(fib-iter 1 1 3)

(fib-iter 2 1 2)

(fib-iter 3 2 1)

(fib-iter 5 3 0)

3

Scheme lo ejecuta como iterativo, no como recursivo. ¿Pero que sucede si implementamos ese mismo algoritmo en un lenguaje tipo procedimental como C o Pascal? Veamos como podría ser en PHP, el rey de la web:

function fib ($a, $b, $aCalc) {

    if ($aCalc == 0) {
        return $b;
    }else{
        $aCalc--;
        fib($a + $b, $a, $aCalc);
    }
}

$result = fib (1, 0, 4);
echo $result;

Y no funcionará. ¿Por qué? Pues porque PHP lo interpretará como recursivo, no como iterativo, y hará:

(fib 1 0 4)

(fib 1 0 4)(fib 1 1 3)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 1)(fib 5 3 0)

Pero en vez de quedarse aquí empezará a hacer los «returns», los «pops» de la pila:

(fib 1 0 4)(fib 1 1 3)(fib 2 1 2)(fib 3 2 0)

(fib 1 0 4)(fib 1 1 3)(fib 2 1 1)

(fib 1 0 4)(fib 1 1 2)

(fib 1 0 3)

:-/

Entonces, ¿como hacer «entender» al compilador o intérprete en este tipo de lenguajes que deseamos una implementación iterativa? La única opción es hacer servir las instrucciones que disponen para bucles: while, for, repeat, etc. Este podría ser un ejemplo en PHP:

function fibonacci($n) {
    $f[0] = 0;
    $f[1] = 1;

    for ($i = 2; $i <= $n; $i++) {
        $f[$i] = $f[$i-1] + $f[$i-2];
    }

    echo $f[$n];
}
fibonacci(8);

Ésta curiosidad se puede expresar también a la inversa: Scheme interpreta como iterativos algoritmos que a quienes estamos acostumbrados a los lenguajes por preocedimientos (procedural languages) nos parecen iterativos. Probablemente ésta es mejor forma de expresarlo.

La función de Ackermann

Posted on por
1

Llevo un par de meses bastante entretenido con el libro del MIT «Structure and Interpretation of Computer Programs». Si bien el MIT nos permite el acceso gratuitamente a todo su contenido aquí, es un libro genial que realmente vale la pena comprárselo.

En uno de sus primeros capítulos, donde se contrastan los procesos iterativos con los recursivos y como aquel que no quiere la cosa, en un ejercicio aparentemente inocente aparece un procedimiento que computa una variante de la función matemática de Ackermann:

(define (A x y)
    (cond ((= y 0) 0)
    ((= x 0) (* 2 y))
    ((= y 1) 2)
    (else (A (- x 1)
        (A x (- y 1))))))

Dicha función es famosa en teoría de la computación. Lo que sorprende de dicha función, a diferencia de las que habitualmente se usan como función «modelo» para enseñar qué es la recursividad, es que no es recursiva primitiva. El ejemplo típico de la función recursiva es la que nos da el factorial de un número n:

(define (factorial n)
    (if (= n 1)
    1
    (* n (factorial (- n 1)))))

El proceso que seguiría para calcular por ejemplo el factorial de 6 sería:

factorial(6)

6 * factorial(5)

6 * (5 * factorial(4))

6 * (5 * (4 * factorial(3)))

6 * (5 * (4 * (3 * factorial(2))))

6 * (5 * (4 * (3 * (2 * factorial(1)))))

Este es el punto en que más se carga la pila, a partir de aquí serían «pops»:

6 * (5 * (4 * (3 * (2 * 1))))

6 * (5 * (4 * (3 * 2)))

6 * (5 * (4 * 6))

6 * (5 * (24))

6 * (120)

720

Las funciones recursivas «típicas» siguen éste patrón, se van sumergiendo hasta llegar a un punto de inflexión a partir del cual van emergiendo hasta aflorar el resultado final. La función de Ackermann podría parecer que transcurre igual, por ejemplo (A 1 6) sería:

(A 1 6)

(A 0 (A 1 5))

(A 0 (A 0 (A 1 4)))

(A 0 (A 0 (A 0 (A 1 3))))

(A 0 (A 0 (A 0 (A 0 (A 1 2)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))

(A 0 (A 0 (A 0 (A 0 (A 0 2)))))

(A 0 (A 0 (A 0 (A 0 4))))

(A 0 (A 0 (A 0 8)))

(A 0 (A 0 16))

(A 0  32)

64

Es decir, 26 De hecho, para todo (A 1 n) el resultado siempre será 2n Pero veamos por ejemplo como transcurre al calcular (A 2 4):

(A 2 4)

(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

…

Como se puede observar, se va profundizando para después emerger y a continuación volver a sumergirse. Después de un largo proceso recursivo, el resultado final que acaba dando es 65536, es decir, 216.