Introducción a las estructuras de datos

Los problemas más sencillos en programación a menudo se resuelven con sencillas operaciones aritméticas (contadores, multiplicación, división, módulos, etc.) sobre tipos de datos fundamentales como int o float, pero a medida que los problemas se vuelven más complejos y tenemos la necesidad de guardar los datos y sus relaciones en memoria para operar con ellos de la forma más eficiente posible, surge la necesidad de utilizar estructuras de datos.

Empecemos por revisar el array y su implementación en mis dos lenguajes favoritos: JS y PHP.

Algunas curiosidades sobre JS y PHP

Debido a las particularidades del lenguaje JS las estructuras de datos y su implementación están estrechamente relacionadas con los objects, básicamente porque que todas las estructuras de datos no primitivas en JS son, en el fondo, objects (de ahí el adagio “Everything is an object in JavaScript”).

En cuanto a PHP, su principal particularidad es que buena parte de las estructuras de datos se pueden implementar a partir del array. Según la propia documentación, a partir del array se pueden implementar las estructuras “list (vector), hash table (an implementation of a map), dictionary, collection, stack, queue, and probably more”.

En PHP5 se ofrecían algunas alternativas al array a través de la librería estándar SPL, pero a partir de PHP7 la solución más eficiente en casi todos los casos es el array o bien las estructuras de datos que ofrece la librería ds (al respecto, ver Efficient data structures for PHP 7).

En resumen, debido a las diferencias a bajo nivel de cada lenguaje, pueden existen diferencias entre la definición y comportamiento teóricos de una estructura de datos particular y su comportamiento real entre distintas versiones de JS o PHP y sus intérpretes.

El array ideal

Un array es una colección lineal de elementos a los que se puede acceder a través de un índice o key, estos elementos pueden tener valores repetidos y sin ningún orden en particular.

Típicamente a cada índice se le asigna una dirección u offset en memoria de forma que los elementos tienen direcciones consecutivas, por ello sólo es necesario guardar la dirección del primero como referencia para localizar al resto. Debido a esto, leer el valor relacionado con un índice particular en un array es una operación sencilla y rápida (O(1)).

Buscar un elemento dado en un array, en cambio, requiere de recorrer todos los índices y comprobar cada uno de los elementos en cada índice hasta dar con el elemento buscado (o informar de que no aparece), por lo que la búsqueda en un array es una operación menos eficiente que la lectura (O(n) en el peor caso).

La inserción y eliminación de elementos en el array también implican complejidades del orden de O(n) puesto que implican, en el peor caso, reindexar todo el resto de elementos del array después de la inserción o eliminación de un elemento al principio del array.

Implementación del array en JS V8

En JS sobre el motor V8 (chrome, Node…) los Array son “list-like object” que, al igual que cualquier otro Object puede contener propiedades (named properties) y elementos (integer-indexed elements) y que, por debajo, se comportan de distinto modo según lo que les metamos dentro.

Si limitamos nuestro Array a contener elementos indexados por integers contiguos el Array se comportará aproximadamente como un array ideal, porque a nivel de la máquina virtual, de hecho, se empleará un array para indexar y acceder a nuestros elementos.

Debido a esta peculiaridad del Array como Object en JS sobre V8, se pueden hacer cosas tan curiosas como éstas:

let fruits = ['Apple', 'Banana'];
fruits.length; // 2

fruits['hello'] = 'Eggplant';
fruits.length; // 2 (!) 

let hi = {toString: () => 'hello'};
fruits[hi]; // 'Eggplant' (!)

fruits[-1] = 'Tomato';
fruits.length; // 2 (!)

fruits[18] = 'Orange';
fruits.length; // 19 (!)

Puedes encontrar info más detallada sobre la gestión a bajo nivel de las propiedades y elementos de un Object en JS sobre V8 aquí y aquí.

Implementación del array en PHP7

Al igual que en JS sobre V8, en PHP el array es una construcción muy flexible, es decir, a partir de la cual se pueden construir diversas estructuras de datos y no sólo arrays “ideales”.

Para hacer posible esta flexibilidad, en PHP todos los array son, por debajo, “ordered maps” u “ordered dictionaries”, es decir, pares key-value cuyo orden de inserción en el array se mantiene representado en memoria.

En PHP7, mientras utilicemos el array para almacenar integer-indexed elements en orden ascendente el array se comportará aproximadamente como un array ideal, porque a bajo nivel se utiliza un array real para leer/encontrar los datos almacenados a través de su índice y offset en memoria.

Sin embargo, si utilizáramos el array para construir un array asociativo, “por debajo” se empleará una función de hashing para asignar y recuperar el índice numérico de cada named property (y entrará en funcionamiento un algoritmo para evitar colisiones), con lo que el array asociativo real perderá la eficiencia computacional característica del array “puro”.

Al respecto de PHP7 y sus optimizaciones en la implementación del array respecto a PHP5, puedes encontrar info detallada aquí.