Estructuras de datos y algoritmos en Java, Parte 1: Descripción general

Los programadores de Java usan estructuras de datos para almacenar y organizar datos, y nosotros usamos algoritmos para manipular los datos en esas estructuras. Cuanto más comprenda las estructuras de datos y los algoritmos, y cómo funcionan juntos, más eficientes serán sus programas Java.

Este tutorial lanza una serie breve que presenta estructuras de datos y algoritmos. En la Parte 1, aprenderá qué es una estructura de datos y cómo se clasifican las estructuras de datos. También aprenderá qué es un algoritmo, cómo se representan los algoritmos y cómo usar funciones de complejidad de tiempo y espacio para comparar algoritmos similares. Una vez que tenga estos conceptos básicos, estará listo para aprender a buscar y ordenar con matrices unidimensionales, en la Parte 2.

¿Qué es una estructura de datos?

Las estructuras de datos se basan en tipos de datos abstractos (ADT), que Wikipedia define de la siguiente manera:

[Un] modelo matemático para tipos de datos donde un tipo de datos se define por su comportamiento (semántica) desde el punto de vista de un usuario de los datos, específicamente en términos de valores posibles, posibles operaciones sobre datos de este tipo y el comportamiento de estas operaciones.

A un ADT no le importa la representación en memoria de sus valores o cómo se implementan sus operaciones. Es como una interfaz Java, que es un tipo de datos que está desconectado de cualquier implementación. En contraste, una estructura de datos es una implementación concreta de uno o más ADT, similar a cómo las clases de Java implementan interfaces.

Algunos ejemplos de ADT incluyen Empleado, Vehículo, Matriz y Lista. Considere la lista ADT (también conocida como secuencia ADT), que describe una colección ordenada de elementos que comparten un tipo común. Cada elemento de esta colección tiene su propia posición y se permiten elementos duplicados. Las operaciones básicas admitidas por List ADT incluyen:

  • Creando una lista nueva y vacía
  • Agregar un valor al final de la lista
  • Insertar un valor dentro de la lista
  • Eliminar un valor de la lista
  • Iterando sobre la lista
  • Destruyendo la lista

Las estructuras de datos que pueden implementar List ADT incluyen arreglos unidimensionales de tamaño fijo y tamaño dinámico y listas de enlaces individuales. (Se le presentarán matrices en la Parte 2 y listas vinculadas en la Parte 3.)

Clasificación de estructuras de datos

Hay muchos tipos de estructuras de datos, que van desde variables únicas hasta matrices o listas enlazadas de objetos que contienen varios campos. Todas las estructuras de datos se pueden clasificar como primitivas o agregados, y algunas se clasifican como contenedores.

Primitivas vs agregados

El tipo más simple de estructura de datos almacena elementos de datos individuales; por ejemplo, una variable que almacena un valor booleano o una variable que almacena un número entero. Me refiero a estas estructuras de datos como primitivas .

Muchas estructuras de datos pueden almacenar varios elementos de datos. Por ejemplo, una matriz puede almacenar varios elementos de datos en sus distintas ranuras y un objeto puede almacenar varios elementos de datos a través de sus campos. Me refiero a estas estructuras de datos como agregados .

Todas las estructuras de datos que veremos en esta serie son agregados.

Contenedores

Todo aquello de lo que se almacenan y recuperan elementos de datos podría considerarse una estructura de datos. Los ejemplos incluyen las estructuras de datos derivadas de los ADT de empleado, vehículo, matriz y lista mencionados anteriormente.

Muchas estructuras de datos están diseñadas para describir varias entidades. Las instancias de una Employeeclase son estructuras de datos que existen para describir a varios empleados, por ejemplo. Por el contrario, algunas estructuras de datos existen como recipientes de almacenamiento genéricos para otras estructuras de datos. Por ejemplo, una matriz puede almacenar valores primitivos o referencias a objetos. Me refiero a esta última categoría de estructuras de datos como contenedores .

Además de ser agregados, todas las estructuras de datos que veremos en esta serie son contenedores.

Estructuras de datos y algoritmos en colecciones de Java

El marco de colecciones de Java admite muchos tipos de estructuras de datos orientadas a contenedores y algoritmos asociados. Esta serie le ayudará a comprender mejor este marco.

Patrones de diseño y estructuras de datos

Se ha vuelto bastante común utilizar patrones de diseño para presentar a los estudiantes universitarios las estructuras de datos. Un artículo de la Universidad de Brown examina varios patrones de diseño que son útiles para diseñar estructuras de datos de alta calidad. Entre otras cosas, el documento demuestra que el patrón Adaptador es útil para diseñar pilas y colas. El código de demostración se muestra en el Listado 1.

Listado 1. Usando el patrón Adaptador para pilas y colas (DequeStack.java)

public class DequeStack implements Stack { Deque D; // holds the elements of the stack public DequeStack() { D = new MyDeque(); } @Override public int size() { return D.size(); } @Override public boolean isEmpty() { return D.isEmpty(); } @Override public void push(Object obj) { D.insertLast(obj); } @Override public Object top() throws StackEmptyException { try { return D.lastElement(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } @Override public Object pop() throws StackEmptyException { try { return D.removeLast(); } catch(DequeEmptyException err) { throw new StackEmptyException(); } } }

El Listado 1 contiene extractos de la DequeStackclase del artículo de la Universidad de Brown , que demuestra el patrón Adaptador. Tenga en cuenta que Stacky Dequeson interfaces que describen los ADT Stack y Deque. MyDequees una clase que implementa Deque.

Métodos de interfaz primordiales

El código original que Listado 1 se basa en no presentó el código fuente para Stack, Dequey MyDeque. Para mayor claridad, he introducido @Overrideanotaciones para mostrar que todos DequeStacklos métodos que no son constructores anulan los Stackmétodos.

DequeStackse adapta MyDequepara que pueda implementar Stack. Todos DequeStacklos métodos son llamadas de una línea a los Dequemétodos de la interfaz. Sin embargo, hay una pequeña arruga en la que las Dequeexcepciones se convierten en Stackexcepciones.

¿Qué es un algoritmo?

Utilizados históricamente como herramienta para el cálculo matemático, los algoritmos están profundamente conectados con la informática y, en particular, con las estructuras de datos. Un algoritmo es una secuencia de instrucciones que realiza una tarea en un período de tiempo finito. Las cualidades de un algoritmo son las siguientes:

  • Recibe cero o más entradas
  • Produce al menos una salida
  • Consta de instrucciones claras y sin ambigüedades
  • Termina después de un número finito de pasos
  • Es lo suficientemente básico como para que una persona pueda realizarlo con lápiz y papel.

Tenga en cuenta que, si bien los programas pueden ser de naturaleza algorítmica, muchos programas no terminan sin intervención externa.

Many code sequences qualify as algorithms. One example is a code sequence that prints a report. More famously, Euclid's algorithm is used to calculate the mathematical greatest common divisor. A case could even be made that a data structure's basic operations (such as store value in array slot) are algorithms. In this series, for the most part, I'll focus on higher-level algorithms used to process data structures, such as the Binary Search and Matrix Multiplication algorithms.

Flowcharts and pseudocode

How do you represent an algorithm? Writing code before fully understanding its underlying algorithm can lead to bugs, so what's a better alternative? Two options are flowcharts and pseudocode.

Using flowcharts to represent algorithms

A flowchart is a visual representation of an algorithm's control flow. This representation illustrates statements that need to be executed, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. Figure 1 reveals the various symbols that flowcharts use to visualize algorithms.

Consider an algorithm that initializes a counter to 0, reads characters until a newline (\n) character is seen, increments the counter for each digit character that's been read, and prints the counter's value after the newline character has been read. The flowchart in Figure 2 illustrates this algorithm's control flow.

A flowchart's simplicity and its ability to present an algorithm's control flow visually (so that it's is easy to follow) are its major advantages. Flowcharts also have several disadvantages, however:

  • It's easy to introduce errors or inaccuracies into highly-detailed flowcharts because of the tedium associated with drawing them.
  • It takes time to position, label, and connect a flowchart's symbols, even using tools to speed up this process. This delay might slow your understanding of an algorithm.
  • Flowcharts belong to the structured programming era and aren't as useful in an object-oriented context. In contrast, the Unified Modeling Language (UML) is more appropriate for creating object-oriented visual representations.

Using pseudocode to represent algorithms

An alternative to flowcharts is pseudocode, which is a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, there are no hard-and-fast rules for writing pseudocode.

You should strive for consistency when writing pseudocode. Being consistent will make it much easier to translate the pseudocode into actual source code. For example, consider the following pseudocode representation of the previous counter-oriented flowchart:

 DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 DO READ ch IF ch GE '0' AND ch LE '9' THEN count = count + 1 END IF UNTIL ch EQ '\n' PRINT count END

The pseudocode first presents a couple of DECLARE statements that introduce variables ch and count, initialized to default values. It then presents a DO loop that executes UNTILch contains \n (the newline character), at which point the loop ends and a PRINT statement outputs count's value.

For each loop iteration, READ causes a character to be read from the keyboard (or perhaps a file--in this case it doesn't matter what constitutes the underlying input source) and assigned to ch. If this character is a digit (one of 0 through 9), count is incremented by 1.

Choosing the right algorithm

The data structures and algorithms you use critically affect two factors in your applications:

  1. Memory usage (for data structures).
  2. CPU time (for algorithms that interact with those data structures).

It follows that you should be especially mindful of the algorithms and data structures you use for applications that will process lots of data. These include applications used for big data and the Internet of Things.

Balancing memory and CPU

When choosing a data structure or algorithm, you will sometimes discover an inverse relationship between memory usage and CPU time: the less memory a data structure uses, the more CPU time associated algorithms need to process the data structure's data items. Also, the more memory a data structure uses, the less CPU time associated algorithms will need to process the data items–leading to faster algorithm results.

As much as possible, you should strive to balance memory use with CPU time. You can simplify this task by analyzing algorithms to determine their efficiency. How well does one algorithm perform against another of similar nature? Answering this question will help you make good choices given a choice between multiple algorithms.

Measuring algorithm efficiency

Some algorithms perform better than others. For example, the Binary Search algorithm is almost always more efficient than the Linear Search algorithm–something you'll see for yourself in Part 2. You want to choose the most efficient algorithm for your application's needs, but that choice might not be as obvious as you would think.

For instance, what does it mean if the Selection Sort algorithm (introduced in Part 2) takes 0.4 seconds to sort 10,000 integers on a given machine? That benchmark is only valid for that particular machine, that particular implementation of the algorithm, and for the size of the input data.

As computer scientist, we use time complexity and space complexity to measure an algorithm's efficiency, distilling these into complexity functions to abstract implementation and runtime environment details. Complexity functions reveal the variance in an algorithm's time and space requirements based on the amount of input data:

  • A time-complexity function measures an algorithm's time complexity--meaning how long an algorithm takes to complete.
  • Una función de complejidad espacial mide la complejidad espacial de un algoritmo, es decir, la cantidad de sobrecarga de memoria requerida por el algoritmo para realizar su tarea.

Ambas funciones de complejidad se basan en el tamaño de la entrada ( n ), que de alguna manera refleja la cantidad de datos de entrada. Considere el siguiente pseudocódigo para la impresión de matrices:

 DECLARE INTEGER i, x[] = [ 10, 15, -1, 32 ] FOR i = 0 TO LENGTH(x) - 1 PRINT x[i] NEXT i END

Funciones de complejidad temporal y complejidad temporal

Puede expresar la complejidad de tiempo de este algoritmo especificando la función de complejidad de tiempo , donde (un multiplicador constante) representa la cantidad de tiempo para completar una iteración de bucle y representa el tiempo de configuración del algoritmo. En este ejemplo, la complejidad del tiempo es lineal.t(n) = an+bab