Complejidad Computacional
Definición
La función de complejidad de un algoritmo es una función \$f : NN -> NN\$ tal que \$f(n)\$ es la cantidad de operaciones que realiza el algoritmo en el peor caso cuando toma una entrada de tamaño \$n\$.
Medimos la cantidad de operaciones en lugar del tiempo total porque el tiempo de ejecución depende de factores externos, como:
-
La velocidad del procesador.
-
La cantidad de memoria disponible.
-
El sistema operativo.
-
El lenguaje de programación y el compilador utilizado.
En cambio, la cantidad de operaciones refleja el trabajo intrínseco que realiza el algoritmo y permite compararlo de manera independiente de la máquina donde se ejecute.
Nos interesa el peor caso porque nos da una garantía sobre el rendimiento del algoritmo. Sabemos que nunca tardará más que lo indicado por su complejidad. Nos permite analizar el comportamiento del algoritmo cuando la entrada es desfavorable, y estudiarlo de manera más sencillo que analizando todos los casos posibles.
La complejidad se mide en una entrada de tamaño \$n\$ y no de una entrada particular porque distintas entradas del mismo tamaño pueden producir tiempos de ejecución diferentes.
Si analizáramos cada entrada individual, tendríamos infinitas funciones distintas, por lo que el análisis se vuelve poco útil. Al usar únicamente el tamaño de \$n\$, podemos:
-
Estudiar el crecimiento del costo cuando aumenta la entrada.
-
Comparar algoritmos de forma general.
-
Obtener una medida independiente de casos particulares.
Notación "O Grande"
Si \$f\$ y \$g\$ son dos funciones, decimos que \$f in O(g)\$ si existen \$alpha in RR\$ y \$n_0 in NN\$ tales que:
Intuitivamente, \$f in O(g)\$ si \$g(n)\$ "le gana" a \$f(n)\$ para valores grandes de \$n\$.
Ejemplos:
-
\$n in O(n^2)\$
-
\$n^2 notin O(n)\$
-
\$100n in O(n^2)\$
-
\$4n^2 in O(2n^2)\$ (y a la inversa)
Utilizamos la notación "O Grande" para especificar la función de complejidad \$f\$ de los algoritmos. Esta notación nos permite describir el crecimiento de la complejidad de un algoritmo de manera simple y general, ignorando detalles poco relevantes como constantes multiplicativas.
Por ejemplo, las siguientes complejidades
-
\$3n^2 + 5n + 10\$
-
\$100n^2\$
-
\$n^2 + 7\$
pertenecen a \$O(n^2)\$ ya que para valores grandes de \$n\$ el término dominante es \$n^2\$ y los demás términos tienen una influencia despreciable.
-
Si \$f in O(n)\$, decimos que el algoritmo es lineal.
-
Si \$f in O(n^2)\$, decimos que el algoritmo es cuadrático.
-
Si \$f in O(n^3)\$, decimos que el algoritmo es cúbico.
-
En general, si \$f in O(n^k)\$, decimos que el algoritmo es polinomial.
-
Si \$f in O(2^n)\$ o similar, decimos que el algoritmo es exponencial.
Ejemplos:
-
Búsqueda lineal: \$O(n)\$
-
Búsqueda binaria: \$O(log(n))\$
-
Ordenar un arreglo (bubblesort): \$O(n^2)\$
-
Ordenar un arreglo (quicksort): \$O(n^2)\$ en el peor caso, \$O(n log(n))\$ en promedio.
-
Ordenar un arreglo (heapsort, mergesort): \$O(n log(n))\$
Problemas bien resueltos
Decimos que un problema está bien resuelto si existe un algoritmo de complejidad polinomial para el problema.
|
n = 10 |
n = 20 |
n = 30 |
n = 40 |
n = 50 |
|
|
\$O(n)\$ |
0.01 ms |
0.02 ms |
0.03 ms |
0.04 ms |
0.05 ms |
|
\$O(n log(n))\$ |
0.01 ms |
0.03 ms |
0.04 ms |
0.06 ms |
0.08 ms |
|
\$O(n^2)\$ |
0.10 ms |
0.40 ms |
0.90 ms |
1.60 ms |
2.50 ms |
|
\$O(n^3)\$ |
1.00 ms |
8.00 ms |
27.00 ms |
64.00 ms |
0.12 sg |
|
\$O(2^n)\$ |
1.02 ms |
1.04 sg |
17.90 min |
12 días |
35 años |
|
\$O(3^n)\$ |
0.59 sg |
58 min |
6 años |
3855 siglos |
\$2 * 10^8\$ siglos |
Los algoritmos polinomiales se consideran satisfactorios (cuanto menor sea el grado, mejor), y los algoritmos supra-polinomiales se consideran no satisfactorios.
Divide and Conquer
La técnica divide and conquer es una idea para diseñar algoritmos recursivos.
Un algoritmo divide and conquer divide recursivamente el problema en dos o más subproblemas del mismo tipo (o similar), hasta que los subproblemas son tan pequeños que se pueden resolver directamente.
Una vez hecho esto, las soluciones de los subproblemas se combinan para obtener una solución del problema original.
Esta técnica es la base de algoritmos eficientes para muchos problemas, como ordenamiento de arreglos, multiplicación de números grandes, y el cálculo de la transformada discreta de Fourier, entre otros.
Si la instancia \$I\$ de entrada es pequeña, entonces utilizar un algoritmo ad hoc (para esto) para el problema.
En caso contrario:
-
Dividir \$I\$ en sub-instancias \$I_1, I_2, ..., I_k\$ más pequeñas.
-
Resolver recursivamente las \$k\$ sub-instancias.
-
Combinar las soluciones para las \$k\$ sub-instancias para obtener una solución para la instancia original \$i\$.
Dos de los algoritmos de ordenamiento de arreglos más eficientes que se conocen están basados en divide and conquer: el algoritmo mergesort (Von Neumann, 1945) y el algoritmo quicksort (Hoare, 1960).
Ejemplo: Mergesort
Algoritmo divide and conquer para ordenar un arreglo \$A\$ de \$n\$ elementos.
-
Si \$n\$ es pequeño, ordenar por cualquier método sencillo.
-
Si \$n\$ es grande:
-
\$A_1 :=\$ primera mitad de \$A\$.
-
\$A_2 :=\$ segunda mitad de \$A\$.
-
Ordenar recursivamente \$A_1\$ y \$A_2\$ por separado.
-
Combinar \$A_1\$ y \$A_2\$ para obtener los elementos de \$A\$ ordenados (apareo de arreglos).
-
Este algoritmo contiene todos los elementos típicos de la técnica divide and conquer.
+-----------[ 27 10 12 20 25 13 15 22 ]---------+
| |
v v
+----[ 27 10 12 20 ]----+ +----[ 25 13 15 22 ]----+
| | | |
v v v v
+---[ 27 10 ]---+ +---[ 12 20 ]---+ +---[ 25 13 ]---+ +---[ 15 22 ]---+
| | | | | | | |
v v v v v v v v
[ 27 ] [ 10 ] [ 12 ] [ 20 ] [ 25 ] [ 13 ] [ 15 ] [ 22 ]
| | | | | | | |
| | | | | | | |
+-->[ 10 27 ]<--+ +-->[ 12 20 ]<--+ +-->[ 13 25 ]<--+ +-->[ 15 22 ]<--+
| | | |
| | | |
+--->[ 10 12 20 27 ]<---+ +--->[ 13 15 22 25 ]<---+
| |
| |
+---------->[ 10 12 13 15 20 22 25 27 ]<--------+
Ejemplo: Quicksort
El algoritmo quicksort para ordenar un arreglo es otro ejemplo basado en divide and conquer:
-
Seleccionar un elemento \$x\$ del arreglo (llamado pivot).
-
Permutar el arreglo para que queden primero los elementos menores o iguales a \$x\$, luego el mismo \$x\$ y finalmente los elementos mayores que \$x\$.
-
Recursivamente aplicar el mismo procedimiento sobre las dos "mitades" del arreglo.
Es una versión similar a mergesort, con la diferencia de que primero se separa el arreglo y luego se realizan las llamadas recursivas. En este caso, la combinación de las soluciones de los sub-problemas es sencilla.
Quicksort tiene un peor caso de \$O(n^2)\$. Si cada partición queda completamente desbalanceada (un subarreglo tiene tamaño \$n - 1\$ y el otro 0] cada llamada recursiva procesa un arreglo de tamaño apenas una unidad menor que el anterior, formando una cadena de \$n - 1\$ llamadas recursivas. Como cada partición cuesta \$O(n - 1)\$ operaciones, el trabajo total es:
El caso promedio, sin embargo, es de \$O(n log(n))\$
Se puede mejorar este algoritmo en la práctica con estas ideas:
-
Seleccionar el pivote aleatoriamente
-
Cuando el sub-problema es pequeño, utilizar un algoritmo \$O(n^2)\$ para ordenarlo, que en la práctica es más eficiente que el divide and conquer.
Ejemplo: multiplicando números grandes
Supongamos que necesitamos trabajar con números enteros arbitrariamente grandes (por ejemplo, para aplicaciones de criptografía, o para calcular \$pi\$ con muchos decimales).
No podemos usar los tipos numéricos primitivos, porque tienen
límites dados por el hardware. En este caso, hay que
emular la aritmética binaria del
microprocesador, implementando números representados como
arreglos de bits (típicamente arreglos de
boolean). En Java, la clase
BigInteger implementa esta idea.
El producto de dos enteros representados por arreglos de booleanos es \$O(n^2)\$, y hasta 1960 se pensaba que esta complejidad era lo mejor posible. Sin embargo, en 1960 Anatolii Karatsuba descubrió un método más eficiente, basado en divide and conquer.
Supongamos que tenemos \$x = x_1 10^M + x_2\$ e \$y = y_1 10^m + y_2\$. Podemos calcular el producto \$x xx y\$ con el siguiente algoritmo:
Luego de estos pasos, \$"Resultado " = x y\$.
El elemento crucial del algoritmo es que podemos hacer todas las multiplicaciones recursivamente utilizando el mismo algoritmo de Karatsuba. En este sentido, se trata de un algoritmo de divide and conquer, porque calculamos el producto de dos números en función de los productos de números más pequeños.
Si \$t(n)\$ es el tiempo del algoritmo para números de \$n\$ bits, entonces:
Se trata de una ecuación de recurrencia. La complejidad del algoritmo de Karatsuba es de \$O(n^1.585)\$.
A partir de Karatsuba, podemos encontrar múltiples algoritmos con sus siguientes complejidades:
-
Algoritmo de Karatsuba (1960): \$O(n^1.585)\$
-
Algoritmo de Tom-Cook (1963): \$O(n^1.46)\$
-
Algoritmo de Schönhage-Strassen (1971): \$O(n log n log log n)\$
-
En este trabajo, conjeturan una cota inferior de \$omega (n log n)\$
-
-
Algoritmo de Fürer (2007): \$O(n log n * 2^(O(log^* n)))\$
-
Algoritmo de Harvey-van der Hoeven (2019): \$O(n log n)\$
En la práctica, el algoritmo de Harvey-van der Hoeven es más eficiente que los algoritmos anteriores para números inmensamente grandes. No obstante, la existencia de un algoritmo \$O(n log n)\$ es un avance muy importante.
Introducción a Grafos
Definición
Un grafo es un par \$G = (V, E)\$ tal que:
-
\$V\$ es un conjunto finito (llamado el conjunto de vértices (vertex) de \$G\$).
-
\$E sube { ij in V xx V : i != j }\$ es un conjunto de aristas (edge).
(3)-----(6)---(7)
/ | \ \ / |
/ | \ \/ |
(1) | \ /\ |
\ | \ / \ |
\ | \ / \|
(2)----(4)----(5)
En este ejemplo, \$V = { 1, ..., 7}\$ y \$E = { 12, 13, 23, 24, 34, 36, 45, 47, 56, 57, 67}\$.
El orden de los extremos de una arista no es importante. Nos referimos indistintamente a la arista 34 como 43 o bien \${3, 4}\$.
-
Si \$ij in E\$, decimos que los vértices \$i\$ y \$j\$ son vecinos.
-
Dado \$i in V\$, definimos el vecindario de \$i\$ como \$N(i) = {j in V : ij in E}\$.
-
El grado (degree) de un vértice \$i in V\$ es \$d(i) = abs(N(i))\$.
Representamos con grafos relaciones simétricas entre entidades. Por ejemplo:
-
Rutas entre grupo de ciudades (los vértices representan las ciudades).
-
Mapas de ciudades (los vértices representan las esquinas).
-
Relaciones de amistad en una red social (los vértices representan las personas).
-
Cursos a dictar y superposiciones entre cursos (dos vértices son vecinos si sus cursos se solapan).
-
Antenas en una red de telefonía celular (dos vértices son vecinos si sus antenas tienen áreas de cobertura superpuestas).
-
Un camino entre dós vertices \$i\$ y \$j\$ es una secuencia de aristas desde \$i\$ hasta \$j\$.
-
La distancia entre dos vértices es la cantidad de aristas del camino más corto entre ellos.
-
Un grafo es conexo si existe un camino entre todo par de vértices.
-
Una componenta conexa es un subconjunto de vértices conexo, maximal con esta propiedad.
-
Un grafo conexo tiene exactamente una componente conexa.
-
Si \$i\$ y \$j\$ están en componentes conexas distintas, decimos que hay una distancia infinita entre ellos.
-
-
Un vértice aislado es un vértice \$i\$ con \$d(i) = 0\$ (que conforma una componenta conexa de tamaño 1).
(3) (6)---(7)
/ | \ \ |
/ | \ \ |
(1) | (4) \ |
\ | / \ |
\ | / \|
(2) (5)
Nos interesa programar algoritmos que trabajen sobre grafos. Para esto, debemos representar adecuadamante grafos en Java.
Matriz de adyacencia
La matriz de adyacencia de un grafo \$G\$ es una matriz \$A = (a_(ij)) in RR^(abs(V) xx abs(V))\$ tal que \$a_(ij) = 1\$ si \$ij in E\$ y \$a_(ij) = 0\$ en caso contrario.
Para el grafo conexo de 7 vértices del primer ejemplo, la matriz de adyacencia es el siguiente:
class Graph
{
private int _vertices;
private boolean[][] _adj;
public Graph(int n)
{
_vertices = n;
_adj = new boolean[n][n];
}
public void addEdge(int i, int j)
{
_adj[i][j] = _adj[j][i] = true;
}
public void removeEdge(int i, int j)
{
_adj[i][j] = _adj[j][i] = false;
}
public boolean edgeExists(int i, int j)
{
return _adj[i][j];
}
}Ventajas de esta representación:
-
Agregar una arista: \$O(1)\$.
-
Eliminar una arista: \$O(1)\$.
-
Consultar una arista: \$O(1)\$.
Desventajas de esta representación:
-
Agregar un vértice: \$O(n^2)\$.
-
Eliminar un vértice: \$O(n^2)\$.
-
Obtener todos los vecinos de un vértice: \$O(n)\$.
Matriz de incidencia
La matriz de incidencia de un grafo \$G\$ es una matriz \$M = (m_(ij) in RR^(abs(V) xx abs(E))\$ tal que \$m_(ie) = 1\$ si el vértice \$i\$ es uno de los extremos de la arista \$e\$, y \$m_(ie) = 0\$ en caso contrario.
En nuestro ejemplo, \$E = { 12, 13, 23, 24, 34, 36, 45, 47, 56, 57, 67}\$:
Siendo \$n\$ las filas y \$m\$ las columnas, la complejidad de esta representación es la siguiente:
-
Agregar una arista: \$O(n)\$.
-
Eliminar una arista: \$O(m)\$.
-
Consultar una arista: \$O(m)\$.
-
Agregar un vértice: \$O(m)\$.
-
Eliminar un vértice: \$O(n m)\$.
-
Obtener todos los vecinos de un vértice: \$O(1)\$.
Lista de vecinos
Una tercera opción es por medio de listas de vecinos asociadas con cada vértice:
class Graph
{
private ArrayList<HashSet<Integer>> _neighbors;
public Graph(int n)
{
_neighbors = new ArrayList<HashSet<Integer>>();
for (int i = 0; i < n ; i++)
_neighbors.add(new HashSet<Integer>());
}
public void addEdge(int i, int j)
{
_neighbors.get(i).add(j);
_neighbors.get(j).add(i);
}
public void eliminarArista(int i, int j)
{
_neighbors.get(i).remove(j);
_neighbors.get(j).remove(i);
}
public void existeArista(int i, int j)
{
return _vecinos.get(i).contains(j);
}
}Ventajas de esta represanción:
-
Obtener todos los vecinos de un vértice: \$O(1)\$.
-
Agregar un vértice: \$O(n)\$ en el peor caso, pero \$O(1)\$ amortizado.
-
Agregar una arista: \$O(1)\$ promedio.
-
Eliminar una arista: \$O(1)\$ promedio.
-
Consultar si existe una arista: \$O(1)\$ promedio.
Desventajas de esta representación:
-
Eliminar un vértice: \$O(n)\$.
Las operaciones sobre aristas son \$O(log n)\$ en el peor caso
si se usan TreeSets para representar los vecinos de
cada vértice.
Grafos dirigidos
Un grafo dirigido (o digrafo) es un par \$D = (N, A)\$ tal que:
-
\$N\$ es un conjunto finito (llamado el conjunto de nodos de \$G\$).
-
\$A sube { (ij) in V xx V : i != j }\$ es un conjunto de pares ordenados, llamados arcos.
A diferencia de los grafos (no dirigidos), ahora las aristas son pares ordenados.
(1)---->(3)---->(6) | | \ | | | \ | | | \ | | | \ | v v v v (2)---->(4)<----(5)
Diferenciamos entre el grado de entrada y el grado de salida de cada nodo.
-
\$d^(-) (i) = abs(N^(-) (i)) = abs( { j in N : (j, i) in A } )\$.
-
\$d^(+) (i) = abs(N^(+) (i)) = abs( { j in N : (i, j) in A } )\$.
Un camino entre dos nodos es una secuencia de arcos entre ellos, respetando el sentido de los arcos.
Testing unitario - JUnit
Llamamos testing unitario (unit testing) a las actividades tendientes a testear automáticamente unidades individuales de código fuente, para determinar si funcionan correctamente.
Como toda actividad de testing, el testing unitario no puede garantizar que no haya errores, pero proporciona cierto nivel de seguridad sobre el código, y nos permite encontrar muchos errores antes de que el código se integre al resto del sistema.
En un lenguaje orientado a objetos, por unidad individual nos referimos habitualmente a las clases y a sus métodos. Los tests unitarios son creados por los programadores al momento de escribir el código de negocio.
JUnit
Existen varios paquetes de testing unitario para cada entorno de desarrollo. En Java, el más popular es JUnit desarrollado por Kent Beck, Erich Gamma, David Saff y Mike Clark, de la Universidad de Calgary (Canadá).
Para instalarlo, se debe incluir en el build path el
archivo junit.jar.
Cada vez que se escribe una clase, por convención se agregan una o más clases con nombres terminados en "Test", que contienen los tests unitarios para la clase de negocio.
Ejemplo
Por ejemplo, tenemos la clase Person con su nombre
y edad:
class Person
{
private String _name;
private int _age;
public Person(String name, int age)
{
_name = name;
_age = age;
}
public void bithday()
{
++_age;
}
}
Escribimos un test unitario para testear
birthday():
class PersonTest
{
@Test
public void birthdayTest()
{
Person p = new Person("Alice", 17);
p.birthday();
assertEquals(18, p.getAge());
}
}
Este caso de test especifica que una persona
creada con 17 años debe tener 18 años luego de ejecutar el
método birthday() sobre ella.
Veamos la estructura del caso de test:
// Setup de los datos (el "test fixture")
Person p = new Person("Alice", 17);
// Ejecutamos (exercise) la funcionalidad a testear
p.birthday();
// Verificamos que el resultado sea el esperado
assertEquals(18, p.getAge());Todos los tests deben seguir la estructura setup-exercise-verify, idealmente con una línea de código en cada una. Puede haber también una cuarta etapa de teardown del test fixture.
Para ejecutar los tests unitarios, dentro de eclipse seleccionamos la acción menu:[Run As] sobre el proyecto y seleccionamos la opción "JUnit Test".
Se ejecutan todos los métodos calificados con
@Test, y se informa el resultado de cada uno. Si
hay tests que fallan, se informa cuáles fallaron y se puede
acceder a su código.
Es buena práctica ejecutar frecuentemente todos los tests unitarios Idealmente, todos los tests unitarios se deben ejecutar cada vez que se hace un cambio en la funcionalidad. Si esto no es posible, se deben ejecutar completos cada vez que se hace commit del código al repositorio. Si hay errores, se debe corregir inmediatamente.
Assertions
Se utilizan assertions para testear condiciones que se deben cumplir durante la ejecución de los tests unitarios.
-
assertEquals(expected, actual),assertArrayEquals(expected, actual) -
Requiere que los dos parámetros coincidan.
assertTrue(cond)-
Requiere que la condición sea verdadera.
assertFalse(cond)-
Requiere que la condición sea falsa.
assertNull(obj)-
Requiere que la referencia sea
null. assertNotNull(obj)-
Requiere que la referencia no sea
null.
Annotations
Se puede escribir código que se ejecuta antes de realizar los tests, por ejemplo para inicializar elementos comunes a los tests:
class SubjectTest
{
private List<Student> _students;
@Before
public void init()
{
_students = new List<Student>();
_students.add(new Student("Alice", "32514521/2011");
_students.add(new Student("Bob", "34521651/2012");
...
}
...
}Se pueden aplicar las siguientes anotaciones (annotations) a los métodos de la clase de test:
@Test-
Identifica a un método de test.
@Before-
Se ejecuta este método antes de cada test, habitualmente para inicializar los tests o establecer una conexión con la base de datos.
@After-
Se ejecuta este método después de los tests, habitualmente para cerrar conexiones o restaurar los valores originales, si corresponde.
@Ignore-
No ejecuta el método del test. Se utiliza para omitir tests que pueden llevar demasiado tiempo.
-
@Test(expected = Exception.class) -
Falla si el método no lanza la excepción especificada.
@Test(timeout = 100)-
Falla si el método no se ejecuta dentro del límite de tiempo especificado (en milisegundos).
Beneficios del unit testing
-
Permite tener cierta seguridad en cuanto a la correcta implementación de las unidades que se testean.
-
Si se testea toda la funcionalidad relevante, entonces es posible tener cierto grado de certeza de que la implementación es correcta.
-
Los tests proporcionan un entorno aislado para testear cada parte de la funcionalidad del sistema.
-
Es importante que cada test apunte a una parte distinta de la funcionalidad. Así es fácil aislar un problema en función de los tests que fallan.
-
Los tests no tienen que ser repetitivos, para no tener que modificar demasiados tests si cambia la interfaz o la funcionalidad.
-
-
El código de test bien diseñado proporciona documentación del código de producción.
Well designed tests are small isolated snippets of code that call into the system being tested, expecting certain results. A programmer can read the tests to understand what the tested code is supposed to do. So the tests are documents. They are written in a language you understand. They are utterly unambiguous. They are so formal that they execute. And they cannot get out of sync with the application.
That’s pretty close to documentation nirvana. I’ve certainly seen my share of documents that were hard to read, ambiguous, informal, and out of sync with the application. That fact that a good suite of tests cures those ills makes the tests pretty important.— Robert Martin
2014 -
Al diseñár el código para ser testeado, la calidad del diseño mejora sustancialmente.
Well designed tests force a certain degree of decoupling. Often that decoupling is beneficial to the design of the system (…) No one can doubt that well-considered decoupling is beneficial. Tests provide an opportunity for that consideration; and that adds to the importance of the tests.
— Robert Martin
2014 -
Una suite de test completa permite ganar confianza en el código, permitiendo refactorizaciones frecuentes.
A well designed test suite with a high degree of coverage eliminates, or at least strongly mitigates the fear of change. And when you aren’t afraid to change your code, you will clean it. And if you clean it, it won’t rot. And if it doesn’t rot, then the software team can go fast.
(…) The vast majority of programmers say that they have indeed been significantly slowed down by bad code. I mean, honestly, who hasn’t? So it stands to reason that if we keep the code clean, we won’t be slowed down by bad code. And that means a suite of tests is a key to going fast.
Let me state that more strongly. If you have a suite of tests that you can execute quickly, and if you trust that suite of tests enough, then you will not be afraid to change the code. That makes the code flexible.— Robert Martin
2014
Limitaciones del unit testing
-
El testing nunca garantiza la ausencia de errores.
Testing shows the presence, not the absence of bugs.
— Edgser Dijkstra
1969 -
Requiere de revisión permanente, para evitar que los tests queden desactualizados o resulten insuficientes a medida que la funcionalidad del sistema aumenta.
-
Puede ser complicado/costoso definir tests ortogonales y desacoplados entre sí, de modo tal que cada caso apunte a una funcionalidad específica y distinta del resto.
-
El testing unitario no permite encontrar errores derivados de la integración entre módulos, dado que cada módulo se testea por separado.
Ejemplo
Test unitarios para una clase que representa una materia, en el contexto de un sistema de registro de inscripciones a materias:
class SubjectTest
{
@Test
public void preRegistrationTest()
{
Subject subj = new Subject("Programming III");
Student stud = new Student("Alice", "32514521/2011");
assertFalse(subj.isRegistered(stud));
}
@Test
public void postRegistrationTest()
{
Subject subj = new Subject("Programming III");
Student stud = new Student("Alice", "32514521/2011");
subj.register(stud);
assertFalse(subj.isRegistered(stud));
}
}Es importante testar los casos borde:
@Test
public void noRegisteredTest()
{
Subject subj = new Subject("Programming III");
assertEquals(0, subj.amountApproved());
}
@Test
public void unregisteredTest()
{
Subject subj = new Subject("Programming III");
Student stud = new Student("Alice", "32514521/2011");
subj.register(new Student(new Student("Bob", "34521651/2012")));
subj.setFinalCalification(stud, 7);
assertEquals(7, subj.approvedAverage());
}Técnicas de testing
-
Para el diseño de tests:
-
Testear las excepciones que lanza el método, idealmente especificadas en su declaración. Las excepciones forman parte de la interfaz pública de un método.
-
Testear el happy path, con datos que hacen que el método se comporte de la forma esperada.
-
Testear los casos de borde, tanto de la especificación como el código (arreglos/strings vacíos, elementos al inicio/final del arreglo, etc.).
-
-
No se deben repetir tests, dado que en ese caso es más trabajo arreglar los tests cuando cambia la funcionalidad.
También podemos usar dos metodologías para escribir tests:
- Test First Development
-
Escribir los casos de test antes de implementar cada método. El objetivo es pensar qué se debe hacer antes de pensar cómo se implementará el método en cuestión.
- Test-Driven Development (TDD)
-
Escribir cada caso de test individual antes de su implementación, y a continuación implementarlo.
Las tres leyes de TDD:-
No se debe escribir código de producción sin tener antes un test que falla para ese código.
-
No se debe escribir más que un test unitario que falla.
-
No se debe escribir más código de producción que el estrictamente necesario para que pase el test que falla.
-
Consejos
-
Visualizar el testing unitario como una disciplina asociada con las actividades de desarrollo de software.
-
Escribir un caso de test para cada elemento individual de funcionalidad. Cada afirmación individual en la especificación debe tener al menos un caso de test.
-
Escribir tests inteligentes. No es necesario escribir tests para los getters y setters. En cambio, hay que enfocarse en el comportamiento central de cada componente.
-
Setear un entorno limpio para cada test. No es bueno que un test falle porque un test previo dejó datos inconsistentes o inadecuados.
-
Usar objetos falsos para no actuar sobre datos importantes.
-
Agregar nuevos tests cuando se modifica la funcionalidad. Es importante mantener los tests actualizados.
-
Escribir tests antes de corregir un bug. Es una forma de asegurarse de que el bug se corrigió, y también permite detectar si el bug reaparace.
-
Usar unit testing para asegurarse que la performance del sistema no empeora.
-
Ejecutar los tests continuamente. La situación ideal es que los tests se ejecuten automáticamente, y se envíen avisos a los desarrolladores si se encuentran problemas.
When I first encountered unit testing, I was sceptical and thought it was just extra work. But I gave it a chance, because smart people who I trusted told me that it’s very useful. Unit testing puts your brain into a state which is very different from coding state. It is challenging to think about what is a simple and correct set of tests for this given component. Once you start writing tests, you’d wonder how you ever got by without them. To make tests even more fun, you can incorporate pair programming. Whether you get together with fellow developers to write tests or write tests for each other’s code, fun is guaranteed. At the end of the day, you will be comfortable knowing your system really works because your tests pass.
2008
Recorrido de grafos
- Problema
-
Determinar si un grafo es conexo.
- Idea
-
Partir de un vértice \$s in V\$ arbitrario, y obtener todos los vértices que se pueden alcanzar a partir de \$s\$.
L := {s};
Mientras L != E (empty):
Seleccionar i en L y marcarlo;
Agregar a L todos los vecinos no marcados de i;
L := L\{i};
Fin
Los vértices marcados son los alcanzables desde s;Si la lista \$L\$ se implementa con una cola (queue), entonces el algoritmo se llama BFS (breadth-first search), y recorre los vértices en orden de distancia creciente desde \$s\$.
Si la lista \$L\$ se implementa con una pila (stack), entonces el algoritmo se llama DFS (depth-first search), y encuentra el vértice más lejano a \$s\$.
Si los vértices marcados son todos los vértices, el grafo es conexo.
Complejidad computacional
¿Qué complejidad computacional tiene este algoritmo?
O(1)
Mientras L != E (empty):
Para todos los vecinos no marcados de i;
O(1)
O(1)
FinEl ciclo anterior realiza \$n := abs(V)\$ iteraciones en el peor caso.
¿Cuál es la complejidad computacional de obtener todos los vecinos no marcados?
Si el grafo está implementado sobre una matriz de adyacencia, obtener los vecinos es \$O(n)\$. En este caso, el algoritmo completo es \$O(n^2)\$.
Sin embargo, si el grafo está implementado sobre listas de vecinos:
-
Obtener los vecinos de un vértice es \$O(1)\$.
-
Recorrer la lista de vecinos es \$O(d(1))\$.
Podemos realizar el siguiente análisis:
O(1)
Mientras L != E (empty):
Procesar los vecinos de i: O(d(i))
O(1)
FinEntonces, en este caso la complejidad computacional del algoritmo es \$sum_(i in V) O(d(i))\$.
Llamamos \$m := abs(E)\$ a la cantidad de aristas del grafo.
- Handshaking Lemma
-
\$sum_(i in V) d(i) = 2m\$
Entonces la complejidad computacional de BFS es:
-
\$O(n^2)\$ si el grafo está implementado sobre una matriz de adyacencia.
-
\$O(m)\$ si el grafo está implementado sobre listas de vecinos.
Es habitual escribir la complejidad de algoritmos sobre grafos en función de \$n = abs(V)\$ y \$m = abs(E)\$.
-
En general, \$m = O(n^2)\$, con lo cual el peor caso es el mismo para ambas implementaciones.
-
Si \$m = O(n)\$, decimos que el grafo es poco denso y entonces conviene la segunda implementación.
Tecnologías
Control de versiones
Se llama control de versiones (Version Control System) a las actividades relacionadas con la gestión de cambios en los archivos, configuración y bibliotecas de un producto (en este contexto, de un sistema de software).
Habitualmente se realiza con herramientas automatizadas y con servidores centralizados o semi-centralizados:
-
Concurrent Versions System (CVS)
-
SourceSafe (VSS)
-
Mercurial
-
SubVersion (SVN)
-
Git
Síntomas de un mal (o inexistente) control de versiones:
-
Se destina tiempo a mantener el código actualizado.
-
Se pierde tiempo buscando la última versión de cada archivo.
-
Se pierde funcionalidad ya implementada.
-
Reaparecen bugs ya corregidos.
Beneficios de un buen VCS:
-
Se realiza el control automáticamente.
-
No hay problema en desarrollar entre varias personas o en varias computadoras.
-
Se tienen historia de los cambios realizados.
-
Se pueden revertir los cambios.
-
Se pueden hacer cambios arriesgados en forma segura.
SVN
Es un VCS centralizado, con un servidor con un repositorio por cada proyecto y un funcionamiento similar a un sistema de archivos.
-
Se tiene un servidor que centraliza los repositorios.
-
Cada usuario tiene una copia local del repositorio completo, sin la historia previa.
Uso de SVN
-
Import: subir un proyecto existente al repositorio.-
Botón derecho sobre el proyecto, opción
-
Seleccionar el protocolo SVN.
-
Especificar la URL del proyecto (proporcionada por el servidor SVN, habitualmente a través de una interfaz web), usuario y clave.
-
-
Checkout: descargar por primera vez un proyecto que ya existe en un repositorio.-
En el menú principal, seleccionar la opción .
-
Seleccionar el tipo de proyecto .
-
Especificar la URL del proyecto (proporcionada por el servidor SVN, habitualmente a través de una interfaz web), usuario y clave.
-
Especificar el nombre local con el que se guardará el proyecto.
-
-
Update: actualizar la versión local descargando los últimos cambios en el repositorio.-
Botón derecho sobre el proyecto, opción .
-
-
Commit: registrar en el servidor los últimos cambios realizados.-
Botón derecho sobre el proyecto, opción .
-
Escribir un comentario y seleccionar los archivos a enviar al repositorio.
-
Git
Sistema de control de versiones distribuido, orientado a repositorios y con énfasis en la eficiencia.
-
Se tiene un servidor que permite el intercambio de los repositorios entre los usuarios.
-
Cada usuario tiene un copia local del repositorio completo, con toda la historia previa.
+-------------------------------+
| remote repository |
+-------------------------------+
| | ^
| fetch | |
| | | push
| v |
| +------------------+
pull | | local repository |
| +------------------+
| | ^
| | |
| | | commit
| | |
| | +---------------+
| | | index (cache) |
| | +---------------+
| checkout | ^
| HEAD | |
| | | add
v v |
+-------------------------------+
| working directory |
+-------------------------------+
Uso de Git
-
Clonamos un repositorio existente en un servidor a nuestro directorio de trabajo:
git clone <repositorio> [<directorio>]. -
Creamos un archivo y lo agregamos a la staging area:
git add <archivo>. -
Hacemos commit de los cambios al repositorio local:
git commit. -
Enviamos todos los cambios al servidor:
git push. -
Traemos todos los cambios del servidor:
git pull.
-
Consultas sobre el estado actual del repositorio:
git status,git diff. -
Borrar un archivo controlado por Git:
git rm <archivo>. -
Mover o renombrar un archivo controlado por Git:
git mv <archivo> <nuevo>.
Arquitecturas para interfaces de usuario
Las interfaces de usuario (GUI) involucran código que, dependiendo de la tecnología, puede ser extenso. El código de la GUI debe ser tratado con los mismos estándares de calidad que el código de negocio.
Desde acciones en la GUI se accede a la funcionalidad de negocio:
-
Esto tiene el riesgo de incluir inteligencia de negocio en el código encargado de la interfaz.
-
Es importante mantener separado el código encargado de la interfaz del código encargado de la funcionalidad de negocio.
Se debe seguir estrictamente el principio de separated presentation al momento de diseñar el código de las interfaces:
[Separated presentation] is a form of layering, where we keep presentation code and domain code in separate layers with the domain code unaware of presentation code.
Presentation code would manipulate GUI widgets and structures in a rich client application, HTTP headers and HTML in a web application, or command line arguments and print statements in a command line application. We then divide the application into two logical modules with all the presentation code in one module and the rest in another module. Further layering is often used to separate data source code from domain (business logic), and to separate the domain using a service layer.
2006
Arquitectura en tres capas
Una arquitectura multi-capa es una arquitectura de software dividida en niveles, desde la interfaz de usuario hasta el almacenamiento de los datos.
El modelo más habitual es contar con tres capas o niveles:
- Nivel de presentación
-
contiene la interfaz de usuario y no realiza procesamiento de información "de negocio". Sólo realiza el procesamiento necesario para presentar adecuadamante la información.
- Nivel de aplicación o de negocio
-
contiene la funcionalidad del sistema. En un diseño orientado a objetos, incluye las clases de negocio y su implementación.
- Nivel de datos
-
contiene el almacenamiento de la información y la funcionalidad asociada con el acceso a la información.
Es importante adoptar una arquitectura que permita cumplir con el principio de separated presentation. Algunas opciones:
-
Forms and controls.
-
Model-View-Controller.
-
Model-View-Presenter.
Forms and Controls
Las interfaces de usuario contienen controles visuales genéricos, que en general tienen la capacidad de almacenar información sencilla.
En la arquitectura forms and controls, se tienen interfaces visuales (llamados forms, frames, etc.) con controles visuales, y las interfaces realizan llamados al código de negocio.
El código de interfaz realiza llamados al código de negocio, para:
-
Ejecutar acciones solicitadas por el usuario.
-
Actualizar los controles visuales cuando cambia el estado del sistema.
En ningún momento el código de negocio debe llamar al código de la interfaz. Más aún, el código de negocio no debe conocer la identidad ni la tecnología utilizada por la interfaz.
Ejemplo: form para cargar un nuevo pedido.
Editar pedido
Cliente: -----------
Producto: ----------
Cantidad: ----------
Descuento: ---------
+-------+ +--------+
| Crear | | Volver |
+-------+ +--------+
El usuario carga los datos del pedido, que se guarda con "Crear". Cuando se modifica la cantidad, se calcula automáticamente el descuento.
Capturamos el evento asociado con el botón "Crear" y llamamos al código de negocio.
Button crear = new Button("Crear");
crear.addActionListener(new ActionListener<ActionEvent>()
{
@Override
public void actionPerformed(ActionEvent sv)
{
Date entrega = pickerEntrega.getDate();
Cliente cliente = (Cliente) comboCliente.getSelectedItem();
Producto producto = (Producto) comboProducto.getSelectedItem();
double cantidad = Double.parseDouble(TextCantidad.getText());
pedidos.crearPedido(cliente, producto, entrega, cantidad);
}
});Cuando se modifica la cantidad, queremos mostrar el porcentaje de descuento. Nunca se debe hacer esto:
TextField cantidad = new TextField(...);
cantidad.addActionListener(new ActionListener<ActionEvent>();
{
@Override
public void actionPerformed(ActionEvent sv)
{
double cantidad = Double.parseDouble(textCantidad.getText());
if (cantidad > 1000)
_descuento.setText("3.00 %");
else if (cantidad > 5000)
_descuento.setText("1.50 %");
else
_descuento.setText("0.00 %");
}
});El cálculo del descuento es código de negocio. Debemos mover este cálculo a un método adecuado en las clases de negocio.
TextField cantidad = new TextField(...);
cantidad.addActionListener(new ActionListener<ActionEvent>();
{
@Override
public void actionPerformed(ActionEvent sv)
{
double cantidad = Double.parseDouble(textCantidad.getText());
double descuento = cliente.descuento(cantidad);
_descuento.setText(Double.toString(descuento));
}
});-
Ventajas:
-
Se trata de una arquitectura sencilla y fácil de implementar.
-
Toda la lógica de la GUI queda contenida en las clases que implementan cada interfaz.
-
-
Desventajas:
-
El código de interfaz puede quedar demasiado recargado para las interfaces más complicadas.
-
La interfaz debe saber en qué momento cambia el estado del sistema, para actualizar los controles.
-
Model-View-Controller
Separamos la lógica de visualización de la lógica de actualización del sistema.
- Model
-
Las clases de negocio, que deben representar adecuadamante las entidades del dominio del problema en cuestión.
- View
-
El código encargado de mostrar la información al usuario, y que contiene los controles visuales.
- Controller
-
Código encargado de tomar el input del usuario y tomar las acciones necesarias sobre ese input, llamando al código del negocio.
+-------+ +---| MODEL |<---+ | +-------+ | | | updates manipulates | | | | v | +------+ +------------+ | VIEW | | CONTROLLER | +------+ +------------+ | ^ | | sees uses | | | +------+ | +----| USER |----+ +------+
Sin embargo, en este diagrama el modelo actualiza la vista, y para eso debe conocerla. Solucionamos este problema por medio de un Observer.
Para cada evento o grupo de eventos importantes, el código de negocio establece un observador:
public Interface ObservadorPedidos
{
public void notificar(Pedido pedido);
}
Esta declaración puede ser interna a alguna clase de negocio
o bien ser una interfaz independiente. El código de interfaz
contiene una o más clases que implementan esta interfaz, y
que actualizan la vista en el método
notificar().
Las clases de negocio en las que se producen cambios de estado tienen una lista de observadores:
public class Pedido
{
private ArrayList<ObservadorPedidos> observadores;
public void registrar(ObservadorPedidos observador)
{
observadores.add(observador);
}
}Cada vez que hay un cambio de estado, el código de negocio notifica a los observadores:
public void setCantidad(double cantidad)
{
_cantidad = cantidad;
_descuento = descuento(this);
notificarObservadores();
}
private void notificarObservadores()
{
for (ObservadorPedidos observador : observadores)
observador.notificar(this);
}El mecanismo de observadores es un caso particular del principio de inversión de dependencias.
-
El modelo no conoce los detalles de la interfaz.
-
Cuando el modelo cambia, la vista es notificada y los controles cambian automáticamente.
-
Se puede tener más de un par view-controller sobre el mismo modelo. Todas las vistas se actualizan automáticamente cuando hay cambios, dado el modelo puede tener más de un observador.
A pesar de que "Model-View-Controller" es un término muy utilizado, no es habitual ver implementaciones completas de esta arquitectura.
Model-View-Presenter
El mecanismo de interacción "circular" de MVC puede ser demasiado estricto. MVP es un intento de combinar MVC con forms and controls, dando una capa de presentación que combina responsabilidades de vista y controlador.
+--------------------+
| Passive View |
+--------------------+
| ^
| |
user events updates view
| |
v |
+--------------------+
| Presenter |
+--------------------+
| ^
v |
updates model state-change events
| ^
v |
+--------------------+
| Model |
+--------------------+
La vista es pasiva y solamente contiene controles visuales para mostrar la información. No contiene código para especificar cómo reaccionar ante las acciones del usuario.
Cuando se genera un evento sobre un control visual, se pasa el evento a un método adecuado del presenter. El presenter decide qué hacer en este caso, y ejecuta los métodos adecuados de la capa de negocio.
Cuando el modelo se modifica, el presenter reacciona y actualiza la vista. El presenter puede ser notificado por medio de observadores (observer synchronization), o bien consultando a los métodos adecuados del modelo ante cada cambio relevante (flow synchronization).
Técnicas de programación en WindowBuilder
Absolute Layout
Por defecto, las bibliotecas Swing ubican los
controles en posiciones predeterminadas (norte, sur, centro,
etc.). Para evitar esto, se debe ubicar un
JAbsoluteLayout como primer componente del frame,
para especificar coordenadas absolutas para los controles que
se posicionen a continuación en el designer.
Look and Feel
Se pueden seleccionar distintas apariencias para nuestra aplicación en Java. El conjunto de características que determinan la apariencia de la aplicación se denomina look and feel.
Para usar el look and feel del sistema, se deben agregar estas líneas en el constructor del form principal:
try {
UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
} catch (Exception e) {
... // debe estar en un try/catch
}
Para usar un look and feel alternativo, es necesario instalar
el archivo .jar correspondiente dentro del
build path del proyecto y cambiar la referencia en el
método setAndLookFeel().
Es importante utilizar un look and feel que se corresponda con las bibliotecas gráficas que estamos usando (en nuestro caso, usamos `Swing).
Por ejemplo, para usar el look and feel de
JTattoo, hacemos:
try {
UIManager.setLookAndFeel("com.jtatto.plaf.smart.SmartLookAndFeel");
} catch (Exception e) {
...
}Text fields
Los JTextFields permiten consultar y modificar el
texto con getText() y setText(),
respectivamente. Es importante recordar que estos dos métodos
trabajan con String, con lo cual hay que hacer
conversiones explícitas hacia/desde los otros tipos de datos:
String str = textField.getText();
int value = Integer.parseInt(str);
value++;
textField.setText(Integer.toString(value);Combo Boxes
Un combo box es adecuado cuando el usuario debe seleccionar entre un conjunto de opciones grande o bien determinado dinámicamente. Se evita que el usuario seleccione una alternativa incorrecta.
Para cargar las opciones (populate) del combo, se debe generar
un nuevo DefaultComboBoxModel con un arreglo de
strings:
comboBox.setModel(new DefaultComboBoxModel(new String[] {
"(seleccione un club)", "River Plate", "Boca Juniors", "Independiente",
"Racing Club", "Otros"
}));
El ComboBoxModel (y en general, los
models para los componentes de Swing) es el
modelo de datos del control, que especifica
qué datos se muestran y cómo se seleccionan.
Para obtener el item seleccionado, se puede consultar por
índice o valor, teniendo en cuenta que en el segundo caso se
obtiene un Object:
int index = comboBox.getSelectedIndex();
String valor = (String) comboBox.getSelectedItem();Radio buttons
Cuando las opciones son pocas y están prefijadas de antemano,
se puede usar un grupo de JRadioButtons. Se deben
ubicar todos los radio buttons dentro de un mismo
ButtonGroup:
private final ButtonGroup buttonGroup = new ButtonGroup();
JRadioButton rdbtnSingle = new JRadioButton("Single");
JRadioButton rdbtnMarried = new JRadioButton("Married");
buttonGroup.add(rdbtnSingle);
buttonGroup.add(rdbtnMarried);
Un ButtonGroup controla que haya a lo sumo un
RadioButton seleccionado dentro del grupo. Si no
se agrupan, puede haber dos de ellos seleccionados al mismo
tiempo.
Check boxes
Cuando las opciones no son excluyentes, se prefieren los
JCheckBoxes. Para obtener si un check box está
activado, se utiliza el método
boolean isSelected() sobre el
JCheckBox. La visualización de conjuntos de datos
se realiza habitualmente por medio de JTables:
table = new JTable();
DefaultTableModel model = new DefaultTableModel();
model.addColumn("DNI");
model.addColumn("Name");
model.addColumn("Residence");
model.addRow(new String[] { "25145125", "Alice", "Tribulato 332" });
model.addRow(new String[] { "29434342", "Bob", "Mitre 2265" });
model.addRow(new String[] { "25145125", "Carlos", "Mitre 1730" });
table.setModel(model);
Sin embargo, la visualización estándar no muestra las columnas
del modelo de datos. Para ver las columnas se debe ubicar la
tabla dentro de un JScrollPane.
Accediendo al modelo de datos de la tabla se pueden consultar y modificar celdas individuales:
TableModel model = table.getModel();
String s = (String) model.getValueAt(2,2);
model.setValueAt("Nuevo dato", 1, 1);
Para modificar la visualización de las celdas de la tabla, es
necesario crear un TableCellRenderer con los
atributos personalizados que sean necesarios, y asignarlo a la
columna correspondiente. Por ejemplo, para centrar la primera
columna de la tabla:
DefaultTableCellRenderer dtcr = new DefaultTableCellRenderer();
dtcr.setHorizontalAlignment(JLabel.CENTER);
TableColumn col = table.getColumnModel().getColumn(0);
col.setCellRenderer(dtcr);
Por medio del TableCellRenderer se controlan
todos los aspectos relacionados con la visualización de las
celdas. Por ejemplo, para cambiar el color:
DefaultTableCellRenderer dtcr = new DefaultTableCellRenderer();
dtcr.setHorizontalAlignment(JLabel.CENTER);
dtcr.setBackground(Color.RED);
dtcr.setForeground(Color.WHITE);
TableColumn col = table.getColumnModel().getColumn(0);
col.setCellRenderer(dtcr);El acceso al modelo de las columnas permite modificar otros atributos de las columnas. Por ejemplo, para fijar el ancho de las columnas podemos hacer:
table.setAutoReziseMode(JTable.AUTO-RESIZE-OFF);
table.getColumnModel().getColumn(0).setPreferredWidth(40);
table.getColumnModel().getColumn(1).setPreferredWidth(150);
table.getColumnModel().getColumn(2).setPreferredWidth(200);Otras opciones
Las tablas no son siempre la mejor alternativa para visualizar
listas de datos. Si hay una única columna y la selección es
importante, se puede usar una JList. Para que se
muestre la barra de desplazamiento, se debe rodear la lista
con un JScrollPane.
Apertura de nuevos forms
En habitual que se deba
abrir un nuevo form desde el form principal o
desde otros forms. Se deben generar nuevos
JFrames dentro del proyecto, y se crean con el
constructor adecuado (que puede recibir parámetros definidos
por el programador).
OtherFrame other = new OtherFrame();
other.setVisible(true);La comunicación entre los frames se pueden dar por medio de métodos públicos del frame secundario, o bien pasando una referencia al frame llamador.
Diálogos
Un diálogo (también llamado form modal) es una ventana que no permite continuar hasta que no sea cerrada.
Se deben generar nuevos JDialog dentro del
proyecto, llamando al constructor que recibe el padre y un
boolean que indica si el diálogo es modal.
public class DialogTest extends JDialog
{
public DialogTest(JFrame parent)
{
super(parent, true); // true = modal
this.setDefaultCloseOperation(JDialog.DISPOSE-ON-CLOSE);
}
}
La clase JOptionPane permite mostrar
cuadros de diálogo con formatos
pre-especificados. Permite generar mensajes y realizar
consultas sencillas, sin agregar una clase por cada tipo de
mensaje.
JOptionPane.showMessageDialog(frame, "El archivo se escribió correctamente.");
JOptionPane.showMessageDialog(frame,
"El archivo no se escribió correctamente.",
"Problemas",
JOptionPane.WARNING_MESSAGE);
);
JOptionPane.showMessageDialog(frame,
"Error! No se escribió el archivo.",
"Error",
JOptionPane.ERROR_MESSAGE);
);Se puede especificar una consulta con hasta tres opciones, del siguiente modo:
Object[] options = {"Sí, por favor", "No, gracias", "Cancelar"};
int n = JOption.showOptionDialog(frame,
"Se produjo un problema! Desea continuar?",
"Problemas",
JOptionPane.YES_NO_CANCEL_OPTION,
JOptionPane.QUESTION_MESSAGE,
null, // icono
options,
options[2] // valor inicial
);Ventana principal
Es habitual que la ventana principal contenga un menú principal y una barra de herramientas.
Se genera el menú agregando al frame la siguiente jerarquía:
-
El menú principal está dado por un
JMenuBar. -
Cada submenú es un
JMenu. -
Dentro de un submenú, cada opción es un
JMenuItem.
Un JMenuItem se comporta del mismo modo que un
JButton, y tiene asociado un
ActionListener con el evento
action → performed. Las
opciones checables dentro de los submenúes se
generan agregando JCheckBoxMenuItems, y seteando
la propiedad selected.
Para generar una barra de herramientas, se debe agregar un
JToolBar y darle las dimensiones adecuadas. Se
agregan los componentes necesarios al JToolBar,
especialmente JButton. Si no queremos que el
usuario modifique la ubicación de la toolbar, se debe
desactivar la propiedad floatable.
Es una buena práctica agregar tooltip texts a los controles, especialmente a los botones de la toolbar.
Los controles se organizan habitualmente por medio de
JPanel. La propiedad
border cuenta con muchas opciones para
manejar la visualización de los paneles. Una opción muy
utilizada es usar un TitledBorder, que genera un
nombre en la parte superior. Cada panel se maneja como un
frame y es importante ubicar un AbsoluteLayout si
queremos organizar los controles por medio de coordenadas
absolutas.
Lecturas
The Professional Programmer
¿Qué es un programador profesional?
El rasgo más importante de un programador es la responsabilidad personal. Un programador profesional toma responsabilidad de su carrera y de su trabajo, y un programador profesional no le pasa esa responsabilidad a otros.
-
Si sos profesional, sos responsable de tu carrera: uno es responsable de estar al día con nuevas tecnologías y estar actualizado, de seguir leyendo y aprendiendo. Un error es esperar que el empleador te enseñe. La relación entre tu empleador está escrita en un contrato: tu empleador promete pagarte, y vos prometés hacer un buen trabajo.
-
Los profesionales toman responsabilidad del código que escriben: no liberan código hasta que saben como funciona. Programadores profesionales esperan que QA (Quality Assurance) no encuentren nada en el código porque ellos no liberan código hasta haberlo testeado a fondo.
-
Los profesionales son jugadores de equipo: toman responsabilidad del equipo entero, no solo de su propio trabajo. Aprenden y enseñan entre ellos, se ayudan entre ellos. Cuando un compañero cae, el otro da un paso adelante, sabiendo que un día ellos van a ser los que necesiten ayuda.
-
Los profesionales no toleran listas grandes de bugs: una lista grande de bugs es un descuido. Sistemas con miles de issues en su issue-tracking es un síntoma de descuido. Solo los sistemas grandes pueden permitirse tener listas tan grandes que requieran automatización para manejarlos.
-
Los profesionales no hacen un desastre: ellos tienen orgullo de su trabajo. Ellos mantienen un código limpio, bien estructurado, y fácil de leer. Siguen estándares y buenas prácticas. Ellos nunca se apresuran y entregan un código desastroso cuando los tiempos de entrega se acercan.
Los profesionales son responsables. Toman responsabilidad de su carrera. Toman responsabilidad de que su código funcione apropiadamante. Toman responsabilidad de la calidad de su trabajo. No abandonan sus principios cuando el tiempo límite de entrega se acerca. Es más, cuando la presión aumenta, los profesionales se aferran más a las disciplinas que saben que son correctas.
Meaningful Names - Part I
Los nombres están en todas partes. Nombramos nuestras variables, funciones, argumentos, clases y paquetes. Nombramos nuestros archivos fuentes y directorios que lo contienen. Nombramos y nombramos. Si lo hacemos tantas veces, hay que hacerlo bien.
Nombres que revelan la intención
El nombre de una variable, función, o clase, debería responder todas las grandes preguntas. Debería contarte por qué existe, qué hace, y cómo se usa. Si el nombre requiere un comentario, entonces no es un buen nombre:
int d; // ellapsed time in days
El nombre d no revela nada. No evoca una
sensación de tiempo ni de días. Deberíamos elegir un nombre
que especifica que está siendo medido y en qué unidad de
medida:
int elapsedTimeInDays;
int daysSinceCreation;
int daysSinceModification;
int fileAgeInDays;Elegir nombres que revelan la intención hace que entender y modificar el código sea más fácil. Observemos el siguiente código:
public List<int[]> getThem()
{
List<int[]> list1 = new ArrayList<int[]>();
for (int[] x : theList)
if (x[0] == 4)
list1.add(x);
return list1;
}¿Por qué es difícil de entender este código? El problema no es la simplicidad del código, sino la implicidad del código: el grado en el que el contexto no es explícito en el código mismo. La implicidad del código requiere que sepamos las respuestas a las siguientes preguntas:
-
¿Qué hay en
theList? -
¿Cuál es el significado del índice 0 en
theList? -
¿Qué significado tiene el valor 4?
-
¿Cómo uso la lista retornada?
Las respuestas a las preguntas anteriores no estaban presentes en el código, pero podrían haber estado. Imaginemos que estamos trabajando en un juego de buscaminas. Renombremos el código anterior:
public List<int[]> getFlaggedCells()
{
List<int[]> flaggedCells = new ArrayList<int[]>();
for (int[] cell : theList)
if (cell[STATUS_VALUE] == FLAGGED)
flaggedCells.add(cell);
return flaggedCells;
}
La simplicidad del código no ha cambiado. Es exactamente el
mismo código anterior, pero el código ahora es mucho más
explícito. Podemos ir más allá y escribir una clase para las
celdas en vez de un array de int. Podemos incluso
añadir un método isFlagged para esconder los
números mágicos:
public List<Cell> getFlaggedCells()
{
List<Cell> flaggedCells = new ArrayList<Cell>();
for (Cell cell : theList)
if (cell.isFlagged())
flaggedCells.add(cell);
return flaggedCells;
}Con estos cambios, no es difícil entender que hace el código. Ese es el poder de elegir buenos nombres.
Evita la desinformación
Los programadores deberían evitar dejar pistas falsas que
oscurecen la intención del código. Deberíamos evitar palabras
cuyos significados varíen de nuestro significado deseado. Por
ejemplo, hp, aix, y
sco son elecciones malas porque son nombres de
plataformas de Unix o variantes. Incluso si estás codeando una
hipotenusa y hp luce como una buena abreviación,
podría ser desinformativo.
No te refieras a un grupo de cuentas como
accountList a menos que sea una
List. La palabra list significa algo
específico para los programadores. Si esa variable no es
actualmente una List, incluso podría llevar a
falsas conclusiones. Así que accountGroups o
simplemente accounts sería mejor.
Meaningful Names - Part II
Haz distinciones significativas
Los programadores crean problemas para ellos mismos cuando escriben código simplemente para satisfacer al compilador o intérprete. No es suficiente con añadir números o palabras ruidosas, incluso si el compilador está satisfecho. Si los nombres tienen que ser diferentes, entonces deberían decir algo diferente.
Nombres como a1, a2, …
, aN es lo opuesto a un significado intencional.
Estos nombres no son desinformativos, son no informativos; no
proveen información acerca de la intención del autor.
Considerá:
public static void copyChars(char a1[], char a2[])
{
for (int i = 0; i < a1.length; i++)
{
a2[i] = a1[i];
}
}
Esta función sería mejor si se usara source y
destination como nombres de argumento.
Los nombres ruidosos son otra forma de no informar. Imaginá
que tenés una clase Product. Si hay otra clase
llamada ProductInfo o ProductData,
tenés nombres diferentes sin que digan algo diferente.
Los nombres ruidosos son redundantes. La palabra
variable no debería aparecer en el nombre de una
variable. La palabra table no debería aparecer en
el nombre de una tabla. ¿Cómo NameString sería
mejor que solo name? ¿Acaso
Name podría ser algo más que un
String?. Por ejemplo:
getActiveAccount();
getActiveAccounts();
getActiveAccountsInfo();¿Cómo los programadores sabrían cuál función deberían llamar?
En la ausencia de convenciones específicas, la variable
moneyAmount es indistinguible de
money, o customerInfo de
customer, etc. Distinguí los nombres de tal
manera que el lector sepa cuál es la diferencia.
Usa nombres pronunciables
Si no podés pronunciar las palabras, no podés discutirlo sin sonar como un idiota. Esto importa porque programar es una actividad social. Habría que explicarles a los nuevos programadores la decisión de los nombres y pronunciarlos de formas estúpidas. Compará
class DtaRcrd102
{
private Date genymdhms;
private Date modymdhms;
private Final String pszqint = "102";
}con
class Customer
{
private Date generationTimestamp;
private Date modificationTimestamp;
private Final String recordID = "102";
}Usa nombres buscables
Uno fácilmente puede grepear por
MAX_CLASSES_PER_STUDENT, pero el número 7 podría
ser más difícil. La búsqueda podría terminar con parte de
nombres de archivos, otras deficiones de constantes, y en
varias expresiones dónde ese valor se está usando. Incluso
constantes con números largos podrían terminar con dígitos
transpuestos, causando bugs que evaden al programador.
Nombres como e son una pobre elección. Es una
letra común y aparece en todas partes. Los nombres largos
triunfan sobre nombres cortos, y nombres que se pueden buscar
prevalecen sobre constantes en el código.
Meaningful Names - Part III
Evitá mapeos mentales
Los lectores no deberían traducir tus nombres a otros que ellos ya conozcan.
Este es un problema con variables de una sola letra.
Ciertamente un contador en un loop puede ser i o
j si el scope es chico. Estos nombres son
tradicionales. Pero en otros contextos, son una elección pobre
de nombres. Solo es un placeholder que el lector debe mapear
al concepto actual.
En general los programadores son gente lista. Y la gente lista quiere presumir de sus capacidades mentales.
La diferencia entre un programador inteligente y un programador profesional es que el profesional entiende que la claridad obviamente gana. Los profesionales escriben código que otros puedan entender.
Nombres de clases
Las clases y objetos deberían ser sustantivos o frases
sustantivas como Customer,
WikiPage y Account. Evitá palabras
como Manager, Processor,
Data, etc. Un nombre de clase no debería ser un
verbo.
Nombres de métodos
Los métodos deberían ser verbos o frases verbales como
postPayment, deletePage, o
save. Accesores, mutadores y predicados deberían
ser nombrados por su valor y prefijados con get,
set y is (de acuerdo con el estándar
javabean).
String name = employee.getName();
customer.setName("Alice");
if (paycheck.isPosted()) ...Cuando los constructores están sobrecargados, es preferible usar métodos factory estáticos con nombres que describen los argumentos. Esto:
Complex fulcrumPoint = Complex.FromRealNumber(23.0);es mejor que esto:
Complex fulcrumPoint = new Complex(23.0);No te hagas el chistoso
Nombres como HolyHandGrenade es divertido, pero
solo para aquellos que comparten tu sentido del humor y
entienden el chiste. DeleteItems sería un nombre
más ideal. Elegí claridad sobre entretenimiento.
Esto aparece en forma de coloquialismos o jergas. No usés
whack() para decir kill(). No usés
nombres con referencias culturales, como
eatMyShorts() para abort().
Decí lo que quieras transmitir. Transmití lo que quieras decir.
Una sola palabra por concepto
Elegí una palabra para un concepto abstracto y se consistente.
Es confuso tener fetch, retrieve y
get como métodos equivalentes en diferentes
clases. Al final vas a estar navegando entre archivos de
código para saber qué término se usó en el código actual en el
que estés trabajando.
Es confuso tener un controller, un
manager y un driver en el mismo
código. ¿Cuál es la diferencia entre
DeviceManager y ProtocolController?
¿Por qué no son ambos controller o
manager? Estos nombres te llevan a pensar que dos
objetos son de diferente tipo, además de clases diferentes.
Float y Double
Evitá float y double cuando querés
respuestas exactas
Los tipos float y double están
diseñados para cálculos científicos. Realizan aritmética
binaria de punto flotante, que está diseñado para calcular
aproximaciones precisas sobre un amplio rango de magnitudes.
Pero no proveen exactitud.
float y double son
particularmente terribles para cálculos monetarios
porque es imposible representar 0.1 (o cualquier potencia
negativa de diez) como float o
double.
Por ejemplo, tengo $1.03 y gasto 42 centavos. ¿Cuánto gasté?:
System.out.println(1.03 - .42);Resultado: 0.6100000000000001.
Otro ejemplo. Tengo $1.00 y compro 9 caramelos a 10 centavos cada uno. ¿Cuál es mi cambio?:
System.out.println(1.00 - 9 * .10);Mi cambio: $0.09999999999999998.
Podés pensar "bueno, redondeo y listo", pero esto no siempre funciona. Por ejemplo, tengo $1, y veo caramelos a 10 centavos, 20 centavos, y así hasta $1. Comprás un caramelo de cada uno, empezando por el más barato hasta que no puedas comprar más. ¿Cuántos caramelos compré y cuál es mi vuelto?:
public static void main(String[] args)
{
double funds = 1.00;
int itemsBought = 0;
for (double price = .10; funds >= price; price += .10) {
funds -= price;
itemsBought++;
}
System.out.println(itemsBought + " items bought.");
System.out.println("Change: $" + funds);
}
Si ejecutás el programa, obtenés que solo podés comprar tres
caramelos, y tenés $0.3999999999999999 de vuelto.
¡Esto es incorrecto! La forma correcta de resolver esto es
usando BigDecimal, int, o
long para cálculos monetarios.
El anterior programa pero usando BigDecimal esta
vez:
public static void main(String[] args)
{
final BigDecimal TEN_CENTS = new BigDecimal(".10");
BigDecimal funds = new BigDecimal("1.00");
int itemsBought = 0;
for (BigDecimal price = TEN_CENTS; funds.compareTo(price) >= 0;
price = price.add(TEN_CENTS)) {
funds = funds.substract(price);
itemsBought++;
}
System.out.println(itemsBought + " items bought.");
System.out.println("Change: $" + funds);
}
Ahora, el programa nos dice que podemos comprar cuatro
caramelos y tenemos $0.00 de cambio. La respuesta
correcta.
La desventaja es que BigDecimal es menos
conveniente que un tipo primitivo, y además es muy lento. Para
problemas cortos quizás no sea un problema, pero para
problemas que empiezen a crecer, es un problema.
La alternativa es usar int o long, y
trackear el punto decimal uno mismo. En este ejemplo, se
convierte todo a centavos:
public static void main(String[] args)
{
int funds = 100;
int itemsBought = 0;
for (int price = 10; funds >= price; price += 10) {
funds -= price;
itemsBought++;
}
System.out.println(itemsBought + " items bought.");
System.out.println("Change: " + funds + " cents.");
}
Resumen: no usés float o double para
cualquier cálculo que requiera precisión. Usá
BigDecimal si querés trackear el punto decimal a
costa de la incoveniencia de no usar tipos primitivos.
BigDecimal te da control total sobre redondeos,
con diferentes tipos de redondeo. Si el rendimiento es
importante, y no te importa trackear vos mismo el punto
decimal, entonces usá int o long.
int para valores chicos, long para
números realmente grandes, y BigDecimal si los
valores son extremedamante grandes.