Estructura de Datos : Arreglos - Fundamentos

Definiciones

¿ Cómo definiría un grupo de programadores un arreglo ?

Un conjunto de posiciones de memoria consecutivas.
Un conjunto de pares de valores, índice y valor, donde para cada índice definido, hay un valor asociado con dicho índice.
Una colección de variables del mismo tipo, que son referenciadas con un nombre común.

¿ Cuál es el error de estas definiciones ?

Hay confusión entre la estructura de datos y la implementación.
La relación entre índice y valor, en términos matemáticos es una correspondencia o mapping, pero nos interesa un enfoque de ciencias de la computación.

¿ Cuál es la definición que interesa a las ciencias de la computación ?

En ciencias de la computación debe darse una definición más funcional, explicitando las definiciones de las funciones que son permitidas sobre la estructura de datos.
Por ejemplo, en el caso de los arreglos, arrays en inglés, solo nos interesan dos funciones, la que recupera valores desde el arreglo y la que almacena valores en el arreglo.

La siguiente es una definición, acorde con las ciencias de la computación :

structure ARRAY(value, index)

        declare CREATE()                   ----> array
                RETRIEVE(array, index)     ----> value
                STORE(array, index, value) ----> array

        for all A perteneciente a array
                  i, j perteneciente a index
                  x perteneciente a value

        let
                RETRIEVE(CREATE,i)       ====> error
                RETRIEVE(STORE(A,i,x),j) ====> if EQUAL(i,j) then x else RETRIEVE(A,j)
        end

end ARRAY

Donde :

CREATE produce un nuevo arreglo vacío.
RETRIEVE con dos entradas, un arreglo y un índice, devuelve el valor apropiado o un error.
STORE almacena un nuevo par, índice y valor, en el arreglo.
El primer axioma aclara que un arreglo recién creado no tiene duplas índice y valor, y querer recuperar el valor de un índice cualquiera nos lleva a un error.
El segundo axioma aclara que recuperar un valor que acaba de almacenarse equivale a preguntarse acerca de los índices intervinientes.

¿ Cuán performante es esta estructura de datos ?

Esta pregunta depende de la implementación de la estructura de datos. Por ejemplo, si los arreglos se implementan en memoria principal convencional con acceso al azar a cualquier posición de memoria, las funciones RETRIEVE y STORE se ejecutan en un tiempo constante, absolutamente independiente de la cantidad de pares que conforman el arreglo, estando en presencia de un órden de magnitud del tipo O(1).

¿ Como definir arreglos n dimensionales ?

Si interpretamos los índices como n dimensionales ( i1, i2, ..., in ) estamos en presencia de arreglos n dimensionales.

¿ Qué datos podemos almacenar en arreglos ?

Ruleta
- 7 10 8 17 29 11 13 2 32 35 24 17 0 5 16
Semana
- "Lunes" "Martes" "Miercoles" "Jueves" "Viernes" "Sabado" "Domingo"
Edificio
- "Subsuelo" "Planta Baja" "Primer Piso" "Segundo Piso" "Terraza"
Temperatura
- "27,2 C" "27,9 C" "28,5 C" "29,3 C" "31,0 C" "29,8 C" "28,6 C"
- 27,2 27,9 28,5 29,3 31,0 29,8 28,6
Polinomio
- 1 x**4 + 10 x**3 + 3 x**2 + 0 x**1 + 34 x**0
- 34 0 3 10 1

Interpretaciones

Correspondencia entre funciones matemáticas y arreglos informáticos

                  F U N C I O N E S                                                   A R R E G L O S
                   ( Matematicas )                                                    ( Informatica )

       ..................>.....................                           ..................>.....................
       .                                      .                           .                                      .
       .    .............>...............     .                           .    .............>...............     .
       .    .                           .     .                           .    .                           .     .
  *-------------------*       *-------------------*                  *-------------------*       *-------------------*
  |    .    .         |       |         .     .   |                  |    .    .         |       |         .     .   |
  |    .    .         |     ..|...x  x  x  x  x   |                  |    .    .         |     ..|...x  x  x  x  x   |
  |    x    x    x....|..>... |                   |                  |    x    x    x....|..>... |                   |
  |                   |       |   x  x  x  x  x   |                  |                   |       |   x  x  x  x  x   |
  |                   |       |                   |                  |                   |       |                   |
  |                   |       |   x  x  x  x  x   |                  |                   |       |   x  x  x  x  x   |
  |                   |       |                   |                  |                   |       |                   |
  |      x     x......|..>... |   x  x  x  x  x   |                  |      x     x......|..>... |   x  x  x  x  x   |
  |      .            |     . |                   |                  |      .            |     . |                   |
  |      .............|..>....|...x  x  x  x  x   |                  |      .............|..>....|...x  x  x  x  x   |
  |                   |       |                   |                  |                   |       |                   |
  |                   |       |   x  x  x  x  x   |                  |                   |       |   x  x  x  x  x   |
  |    x    x    x....|..>... |                   |                  |    x    x    x....|..>... |                   |
  |    .    .         |     ..|...x  x  x  x  x   |                  |    .    .         |     ..|...x  x  x  x  x   |
  |    .    .         |       |            .  .   |                  |    .    .         |       |            .  .   |
  *-------------------*       *-------------------*                  *-------------------*       *-------------------*
       .    .                              .  .                           .    .                              .  .
       .    .............>..................  .                           .    .............>..................  .
       .                                      .                           .                                      .
       ..................>.....................                           ..................>.....................

      D O M I N I O             C O D O M I N I O                      I N D E X   S E T           V A L U E   S E T

Si f es una función del dominio A al codominio B, luego f asigna a cada elemento de A un único elemento de B.
Si a es un arreglo del index set A al value set B, luego a asigna a cada elemento de A un único elemento de B.

Tipos de Arreglos

Arreglos de 1 dimensión      ( indice1 )                                    ( i1 )

Arreglos de 2 dimensiones    ( indice1, indice2 )                           ( i1, i2 )

.......................

Arreglos de n dimensiones    ( indice1, indice2, .........., indicen )      ( i1, i2, ..........., in )

Arreglos y Memoria

Memoria de 1 Dimension

  M  ( j )                                        ------|---------------------------------------------------|------>
  M  ( m:v )                                            m                                                   v      j

Arreglos de 1 Dimension

  A  ( i1 )                                       -----------------|----------------------|------------------------>
  A  ( l1:u1 )                                                     l1                     u1                       i1

  Funcion j = f(i1) = m + ( i1 - 1 )

Arreglos de 2 Dimension

  A  ( i1, i2 )                                   ----------|------------------------------------|----------------->
  A  ( l1:u1, l2:u2 )                                       l2                                   u2                i2

  Funcion j = f( i1, i2 ) = m + ( i1 - 1 ) u2
                              + ( i2 - 1 )

Arreglos de 3 Dimension

  A  ( i1, i2, i3 )                               ----------------------------|-------------------------|---------->
  A  ( l1:u1, l2:u2, l3:u3 )                                                  l3                        u3         i3

  Funcion j = f( i1, i2, i3 ) = m + ( i1 - 1 ) u2u3
                                  + ( i2 - 1 ) u3
                                  + ( i3 - 1 )

Arreglos de n Dimension

  A  ( i1, i2, .........., in )                   -------------------|---------------------|----------------------->
  A  ( l1:u1, l2:u2, .........., ln:un )                             in                    un                      in

  Funcion j = f( i1, i2, i3, ..., in ) = m + ( i1 - 1 ) u2u3...un
                                           + ( i2 - 1 ) u3u4...un
                                           + ( i3 - 1 ) u4u5...un
                                           + ....................
                                           + ( in - 1 )

Ejemplos

Ejemplo de 1 dimension

  A  ( i1 )
  A  ( l1:u1 )
  A  (  3:7  )
  Cantidad de elementos = ( u1 - l1 + 1 ) =
                          (  7 -  3 + 1 ) =
                          5 elementos
  Si m1 = 1000 luego v1 = m1 + cantidad de elementos - 1 = 1000 + 5 - 1 = 1000 + 5 -1 = 1004


Ejemplo de 4 dimensiones

  A  ( i1, i2, i3, i4 )
  A  ( l1:u1, l2:u2, l3:u3, l4:u4, )
  A  (  4:5,   2:4,   1:2,   3:4, )
  Cantidad de elementos = ( u1 - l1 + 1 ) * ( u2 - l2 + 1 ) * ( u3 - l3 + 1 ) * ( u4 - l4 + 1 ) =
                          (  5 -  4 + 1 ) * (  4 -  2 + 1 ) * (  2 -  1 + 1 ) * (  4 -  3 + 1 ) =
                          24 elementos
  Si m1 = 1000 luego v1 = m1 + cantidad de elementos - 1 = 1000 + 24 - 1 = 1000 + 24 -1 = 1023

Tipos de Ordenamientos en Arreglos Multidimensionales

Arreglos de 2 dimensiones    ( indice1, indice2 )

        Ordenamiento por filas

        *----*----*----*----*
        | 00 | 01 | 02 | 03 |
        *----*----*----*----*           *----*----*----*----*----*----*----*----*----*----*----*----*
        | 04 | 05 | 06 | 07 |  ------>  | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
        *----*----*----*----*           *----*----*----*----*----*----*----*----*----*----*----*----*
        | 08 | 09 | 10 | 11 |
        *----*----*----*----*

        Ordenamiento por columnas

        *----*----*----*----*
        | 00 | 01 | 02 | 03 |
        *----*----*----*----*           *----*----*----*----*----*----*----*----*----*----*----*----*
        | 04 | 05 | 06 | 07 |  ------>  | 00 | 04 | 08 | 01 | 05 | 09 | 02 | 06 | 10 | 03 | 07 | 11 |
        *----*----*----*----*           *----*----*----*----*----*----*----*----*----*----*----*----*
        | 08 | 09 | 10 | 11 |
        *----*----*----*----*

        Ordenamiento por arreglos

        *----*          *----*
        |  --|--------> | 00 |   ( fila 0 )
        *----*          *----*
        |  --|-----+    | 01 |
        *----*     |    *----*
        |  --|--+  |    | 02 |
        *----*  |  |    *----*
                |  |    | 03 |
                |  |    *----*
                |  |
                |  |    *----*
                |  +--> | 04 |   ( fila 1 )
                |       *----*
                |       | 05 |
                |       *----*
                |       | 06 |
                |       *----*
                |       | 07 |
                |       *----*
                |
                |       *----*
                +-----> | 08 |   ( fila 2 )
                        *----*
                        | 09 |
                        *----*
                        | 10 |
                        *----*
                        | 11 |
                        *----*

Observar que el caso de ordenamiento por arreglos la variable apunta a un arreglo de arreglos. Si bien el arreglo multidimensional de dos dimensiones puede definirse como integer[][] numeros = new integer[3][4], donde existen 3 filas y 4 columnas, numeros[i], variando i de 0 a 2, determinan las filas, y numeros[i][j], variando i de 0 a 2 y j de 0 a 3, determinan cada celda. En la disposicion de ordenamiento por arreglos, conmutar una fila por otra, es tan economico como conmutar un apuntador de fila por otro. En las otras disposiciones es mucho mas complejo.

Funciones primitivas y secundarias

                                   Usuario


        *------------------------------------------------------------*
        |                                                            |
        |                   Funciones Secundarias                    |
        |                                                            |
        |                                                            |
        |            *---------------------------------*             |
        |            |                                 |             |
        |            |      Funciones  Primitivas      |             |
        |            |                                 |             |
        |            |                                 |             |
        |            |            *-------*            |             |
        |            |            |       |            |             |
        |            |            | Datos |            |             |
        |            |            |       |            |             |
        |            |            *-------*            |             |
        |            |                                 |             |
        |            |                                 |             |
        |            |                                 |             |
        |            |                                 |             |
        |            *---------------------------------*             |
        |                                                            |
        |                                                            |
        |                                                            |
        |                                                            |
        *------------------------------------------------------------*

        |<------------------ Numero Fijo de Componentes ( n ) ----------------->|

        *-----------------------------------------------------------------------*
        | | |X| | |X|X|X| | | | | |X|X| | | |X|X|X|X|X|X| | | | |X|X| | | | | | |
        *-----------------------------------------------------------------------*
                                  A
                                  |
        Indice ( 0, n-1 ) --------+      X = Componentes ( Todos del mismo Tipo )

        crearArreglo(arreglo)
        recuperarComponente(arreglo, posicion, componente)
        almacenarComponente(arreglo, posicion, componente, arreglo)


        crearArreglo(capacidad, arreglo)
        averiguarCapacidad(arreglo, capacidad)
        ejecutarCopia(arreglo, arreglo)
        ejecutarLlenado(arreglo, componente, arreglo)
        ejecutarLlenadoRango(arreglo, posicionDesde, posicionHasta, componente arreglo)
        ejecutarClasificacion(arreglo, arreglo)
        ejecutarClasificacionRango(arreglo, posicionDesde, posicionHasta, arreglo)
        ejecutarBusqueda(arreglo, componente, posicion)
        ejecutarBusquedaRango(arreglo, posicionDesde, posicionHasta, componente, posicion)
        ejecutarIgualdad(arreglo, arreglo, boolean)

Las variables en negrita son variables de salida.

Tiempos de Computación

Los arreglos son estructuras de datos que viven en memoria principal de la computadora y la característica fundamental, de la memoria principal, es que el acceso a cualquier posición de memoria, es constante, ya sea para almacenar datos o recuperar datos de una posición de memoria. Estamos entonces ante una estructura de datos que responde con un órden de magnitud O(1) para almacenar y recuperar datos de un elemento del arreglo. Claro está que el espacio que demanda un arreglo, es de un órden de magnitud O(n), o sea lineal.

Archivos en Arreglos

Definiciones de Archivos :

Un archivo ( file ) es un colección de registros ( records ).
Un registro tiene uno o más campos ( fields ).
Un campo es un contenedor de información.
Una clave ( key ) es un campo usado para distinguir a los registros.
Un ejemplo :
- Guía Telefónica :
  - Campo Nombre
  - Campo Dirección
  - Campo Número
  - Aplicación 1 : Busca por Nombre
  - Aplicación 2 : Busca por Número
  - Aplicación 3 : Busca por Dirección

Las condiciones iniciales son las siguientes :

Utilizaremos arreglos para almacenar el archivo en memoria principal.
Los registros del archivo ya estan en memoria principal.
Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.
Existen en memoria tantos arreglos como campos tenga el archivo.
Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo.

Registros almacenados secuencialmente en memoria :

              R1   R2   R3             Ri             Rn
   ........------------------.......--------.......--------.......
            |    |    |    |         |    |         |    |
   ........------------------.......--------.......--------.......

Registros almacenados no secuencialmente en memoria :

Indice       int    int    float        int    boolean    int    string                          Registros
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  0          |    | |    | |          | |    | |        | |    | |                   |               R1
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  1          |    | |    | |          | |    | |        | |    | |                   |               R2
       ......*----*.*----*.*----------*.*----*.*--------*.*----*.*-------------------*......
  2    .     |    | |    | |          | |    | |        | |    | |                   |     . slot    R3
       ......*----*.*----*.*----------*.*----*.*--------*.*----*.*-------------------*......
  3          |    | |    | |          | |    | |        | |    | |                   |               R4
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  4          |    | |    | |          | |    | |        | |    | |                   |               R5
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  5          |    | |    | |          | |    | |        | |    | |                   |               R6
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  .          .    . .    . .          . .    . .        . .    . .                   .
  .          .    . .    . .          . .    . .        . .    . .                   .
  .          .    . .    . .          . .    . .        . .    . .                   .
  .          .    . .    . .          . .    . .        . .    . .                   .
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  n - 3      |    | |    | |          | |    | |        | |    | |                   |               Rn-2
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  n - 2      |    | |    | |          | |    | |        | |    | |                   |               Rn-1
             *----* *----* *----------* *----* *--------* *----* *-------------------*
  n - 1      |    | |    | |          | |    | |        | |    | |                   |               Rn
             *----* *----* *----------* *----* *--------* *----* *-------------------*