viernes, 25 de noviembre de 2016

Programación del Sinclair QL (XV): Estructuras de Datos. Colas



Otra estructura de datos muy usada

Las colas son la otra estructura de datos simple mas usada. Se comporta como cualquier cola, cuando llegas te pones al final, y conforme se va procesando lo que está en la cabecera vas avanzando. Aquí la máxima es que el primero en entrar es el primero en salir.

Todos usáis una impresora en vuestro ordenador, cuando enviar cosas a imprimir se colocan en una cola de trabajos, y se van procesando de uno en uno. De esta forma podemos tener todos los trabajos de impresión que necesitemos, nuestros o de otros usuarios, y no se lía la impresora ya que los procesa por estricto orden de llegada.

Las colas son sencillas de implementar usando un arreglo y dos variables que hacen de punteros, uno a la cabeza y otro a la cola, conforme llegan los elementos se aumenta el apuntador a la cola y se ubican en el lugar que indique, cuando se desea sacar algo se usa el elemento ubicado en la posición apuntada por la cabeza y se aumenta el apuntador. La cola esta vacía cuando la cabeza supera a la cola. Para evitar que crezcan indefinidamente, cuando se saca un elemento de la cola y esta queda vacía, se reinician los punteros de cabeza y cola. Otro proceso importante es que muchas veces se introducen un conjunto de elementos a una velocidad y se retiran a otra, con lo que puede que el puntero de cola alcance el tamaño máximo disponible, pero como la cabeza ha avanzado queda espacio disponible al comienzo de la cola, por lo que para recuperar ese espacio hay que compactar la cola, desplazando todos los elementos hacia el comienzo.

Esta implementación de la cola que realizo en SuperBASIC usando un arreglo es muy sencilla, utilizo el elemento 0 del arreglo como apuntador a la cabecera, y el elemento 1 como apuntador a la cola, de esta forma mantengo toda la información de manejo en el arreglo. Dispongo de una serie de procedimientos y funciones para el manejo:
  • COLA_CREAR crea una cola con un tamaño mínimo
  • COLA_NUEVA crea una cola del tamaño que se le indique y un margen mínimo
  • COLA_VACIA retorna un booleano que indica si la cola está vacía
  • COLA_ADD añade un dato al final de la cola, si está llena intenta compactarla, si sigue llena la amplia al doble de su tamaño
  • COLA_EXTRACT retorna el dato ubicado en la cabecera de cola
  • COLA_REDUCE reduce la cola al tamaño real que ocupa mas el margen mínimo
  • COLA_CAMBIA cambia su tamaño al que se le indique, puede ser mayor o menor que el tamaño actual de la cola, pero nunca la reduce a menos del numero de elementos que contiene mas el margen mínimo
  • COLA_INIT de uso interno por los otros procesos, sirve para inicializar los punteros de la cola, no debe ser usada mas que por los otros procesos de manejo de la cola
  • COLA_COMPACTA de uso interno por los otros procesos, pasa todos los elementos ocupados por la cola al principio de la misma, dejando todo el espacio libre al final.
NOTA: Las líneas marcadas con :: son opcionales, sirven para limpiar los elementos que se van extrayendo y que sea mas sencillo visualizar los datos de las pruebas, pero no son necesarias para el funcionamiento de las rutinas.
1000 REMark --------------------------------------------------------------
1010 REMark -- ESTRUCTURAS DE DATOS                                     --
1020 REMark --   Modulo....: Cola                                       --
1030 REMark --   Objetivo..: Cola usando un arreglo simple              --
1040 REMark --   Autor.....: javu61, 11/2016                            --
1050 REMark --   Procesos..:                                            --
1060 REMark --     COLA_CREAR      -- Crear la cola                     --
1070 REMark --     COLA_NUEVA(tam) -- Crea la cola con un tamaño        --
1080 REMark --     COLA_INIT       -- Inicializa una cola               --
1090 REMark --     b=COLA_VACIA    -- Ver si la cola esta vacia         --
1100 REMark --     COLA_ADD(dato)  -- Introduce un dato en la cola      --
1110 REMark --     v=COLA_EXTRACT  -- Saca un dato de la cola           --
1120 REMark --     COLA_REDUCE     -- Compacta y reduce su tamaño       --
1130 REMark --     COLA_CAMBIA(tam)-- Cambia el tama‰o de la cola       --
1140 REMark --     COLA_COMPACTA   -- Compacta la cola                  --
1150 REMark --   Puntero...: Se usa el elemento cero del arreglo como   --
1160 REMark --               puntero a la cabeza, y el elemento 1 como  --
1170 REMark --               puntero a la cola                          --
1180 REMark --------------------------------------------------------------
1190 :
1200 REMark --------------------------------------------------------------
1210 REMark --     COLA_CREAR      -- Crea la cola                      --
1220 REMark --------------------------------------------------------------
1230 DEFine PROCedure COLA_CREAR
1240   COLA_NUEVA 10,5 : REMark Espacio para 10 elementos, crece minimo 5
1250 END DEFine 
1260 :
1270 REMark --------------------------------------------------------------
1280 REMark --     COLA_NUEVA(tam,fac) -- Crea la cola con un tama‰o y  --
1290 REMark --                            con un factor de crecimiento  --
1300 REMark --------------------------------------------------------------
1310 DEFine PROCedure COLA_NUEVA(tam,fac)
1320   LET COLA_FACTOR = fac
1330   LET COLA_CABEZA = 0
1340   LET COLA_COLA   = 1
1350   DIM ArrCola(tam+1) : REMark Elementos 0 y 1 se usan como punteros
1360   COLA_INIT
1370 END DEFine 
1380 :
1390 REMark --------------------------------------------------------------
1400 REMark --     COLA_INIT -- Inicializa una cola                     --
1410 REMark --------------------------------------------------------------
1420 DEFine PROCedure COLA_INIT
1430   ArrCola(COLA_CABEZA) = 2 : REMark Puntero a cabeza
1440   ArrCola(COLA_COLA)   = 1 : REMark Puntero a cola
1450 END DEFine 
1460 :
1470 REMark --------------------------------------------------------------
1480 REMark -- b = COLA_VACIA      -- Ver si la cola esta vacia         --
1490 REMark -- RETORNA: Booleano (Si, No)                               --
1500 REMark --------------------------------------------------------------
1510 DEFine FuNction COLA_VACIA
1520   RETurn (ArrCola(COLA_CABEZA) > ArrCola(COLA_COLA))
1530 END DEFine 
1540 :
1550 REMark --------------------------------------------------------------
1560 REMark --     COLA_ADD(dato) -- Introduce un dato en la cola, si   --
1570 REMark --                       esta llena crece al doble          --
1580 REMark --------------------------------------------------------------
1590 DEFine PROCedure COLA_ADD(dato)
1600   IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 
1610     COLA_COMPACTA
1620   END IF 
1630   IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 
1640     COLA_CAMBIA(DIMN(ArrCola)*2)
1650   END IF 
1660   ArrCola(COLA_COLA)=ArrCola(COLA_COLA)+1
1670   ArrCola(ArrCola(COLA_COLA))=dato
1680 END DEFine 
1690 :
1700 REMark --------------------------------------------------------------
1710 REMark -- v = COLA_EXTRACT    -- Saca un dato de la cola           --
1720 REMark -- RETORNA: Valor de la cabeza de la cola                   --
1730 REMark --------------------------------------------------------------
1740 DEFine FuNction COLA_EXTRACT
1750   LOCal valor
1760   :
1770   IF COLA_VACIA THEN 
1780     PRINT"Error: Cola vacia"
1790     STOP
1800   END IF 
1810   :
1820   valor=ArrCola(ArrCola(COLA_CABEZA))
1830   :: ArrCola(ArrCola(COLA_CABEZA))=0
1840   ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1
1850   IF COLA_VACIA THEN COLA_INIT
1860   RETurn valor
1870 END DEFine 
1880 :
1890 REMark --------------------------------------------------------------
1900 REMark --     COLA_REDUCE     -- Compacta y reduce su tama‰o       --
1910 REMark --------------------------------------------------------------
1920 DEFine PROCedure COLA_REDUCE
1930   COLA_COMPACTA
1940   COLA_CAMBIA(ArrCola(COLA_CABEZA)+COLA_FACTOR)
1950 END DEFine 
1960 :
1970 REMark --------------------------------------------------------------
1980 REMark --     COLA_CAMBIA -- Cambia el tama‰o de la cola           --
1990 REMark --------------------------------------------------------------
2000 DEFine PROCedure COLA_CAMBIA(tam)
2010   LOCal b(DIMN(ArrCola)),minimo,i
2020   :
2030   COLA_COMPACTA
2040   FOR i=0 TO ArrCola(COLA_COLA)
2050     IF i > DIMN(ArrCola) THEN EXIT i
2060     b(i)=ArrCola(i)
2070   END FOR i
2080   minimo = ArrCola(COLA_COLA)-ArrCola(COLA_CABEZA)+1 + COLA_FACTOR
2090   IF tam < minimo      THEN tam = minimo
2100   IF tam < COLA_FACTOR THEN tam=tam+COLA_FACTOR
2110   COLA_NUEVA tam,COLA_FACTOR
2120   FOR i=0 TO b(COLA_COLA)
2130     ArrCola(i)=b(i)
2140   END FOR i
2150 END DEFine 
2160 :
2170 REMark --------------------------------------------------------------
2180 REMark --     COLA_COMPACTA   -- Compacta la cola                  --
2190 REMark --------------------------------------------------------------
2200 DEFine PROCedure COLA_COMPACTA(tam)
2210   LOCal i,ini,fin
2220   :
2230   IF (NOT COLA_VACIA) AND (ArrCola(COLA_CABEZA) > 2) THEN 
2240     ini=ArrCola(COLA_CABEZA)
2250     fin=ArrCola(COLA_COLA)
2260     COLA_INIT
2270     FOR i=ini TO fin
2280       COLA_ADD ArrCola(i)
2290     END FOR i
2300     :: FOR i=fin+1 TO DIMN(ArrCola) : ArrCola(i)=0
2310   END IF 
2320 END DEFine 
Además de esta implementación mas simple, existe la posibilidad de aprovechar mejor el espacio evitando ampliaciones, cuando la cola alcanza el final del espacio, mira si hay sitio libre al comienzo, lo que será habitual si se han extraído elementos, y continua la cola por allí hasta alcanzar la cabeza. Ahora hay que poner el indicador de cola vacia al sacar un elemento, no podemos fiarnos de que los punteros se crucen ya. Las funciones que se manejan externamente son iguales a las anteriores, solo cambian las funciones de uso interno. He definido los procedimientos siguientes:
  • COLA_CREAR crea una cola con un tamaño mínimo
  • COLA_NUEVA crea una cola del tamaño que se le indique y un margen mínimo
  • COLA_VACIA retorna un booleano que indica si la cola está vacía
  • COLA_ADD añade un dato al final de la cola, si está llena intenta compactarla, si sigue llena la amplia al doble de su tamaño
  • COLA_EXTRACT retorna el dato ubicado en la cabecera de cola
  • COLA_REDUCE reduce la cola al tamaño real que ocupa mas el margen mínimo
  • COLA_CAMBIA cambia su tamaño al que se le indique, puede ser mayor o menor que el tamaño actual de la cola, pero nunca la reduce a menos del numero de elementos que contiene mas el margen mínimo
  • COLA_INIT de uso interno por los otros procesos, sirve para inicializar los punteros de la cola, no debe ser usada mas que por los otros procesos de manejo de la cola
  • COLA_REORDENA de uso interno por los otros procesos, pasa todos los elementos ocupados por la cola al principio de la misma, dejando todo el espacio libre al final.  Es la única función que tiene otro nombre entre las dos versiones, ya que realmente hacen lo mismo pero de forma un poco diferente.

1000 REMark --------------------------------------------------------------
1010 REMark -- ESTRUCTURAS DE DATOS                                     --
1020 REMark --   Modulo....: Cola                                       --
1030 REMark --   Objetivo..: Cola usando un arreglo, cola circular      --
1040 REMark --   Autor.....: javu61, 11/2016                            --
1050 REMark --   Procesos..:                                            --
1060 REMark --     COLA_CREAR      -- Crear la cola                     --
1070 REMark --     COLA_NUEVA(tam) -- Crea la cola con un tamaño        --
1080 REMark --     COLA_INIT       -- Inicializa una cola               --
1090 REMark --     b=COLA_VACIA    -- Ver si la cola esta vacia         --
1100 REMark --     COLA_ADD(dato)  -- Introduce un dato en la cola      --
1110 REMark --     v=COLA_EXTRACT  -- Saca un dato de la cola           --
1120 REMark --     COLA_REDUCE     -- Reordena y reduce su tamaño       --
1130 REMark --     COLA_CAMBIA(tam)-- Cambia el tama‰o de la cola       --
1140 REMark --     COLA_REORDENA   -- Reordena la cola                  --
1150 REMark --   Puntero...: Se usa el elemento cero del arreglo como   --
1160 REMark --               puntero a la cabeza, y el elemento 1 como  --
1170 REMark --               puntero a la cola                          --
1180 REMark --------------------------------------------------------------
1190 :
1200 REMark --------------------------------------------------------------
1210 REMark --     COLA_CREAR      -- Crea la cola                      --
1220 REMark --------------------------------------------------------------
1230 DEFine PROCedure COLA_CREAR
1240   COLA_NUEVA 10,5 : REMark Espacio minimo 10 elementos
1250 END DEFine 
1260 :
1270 REMark --------------------------------------------------------------
1280 REMark --     COLA_NUEVA(tam,fac) -- Crea la cola con un tama‰o y  --
1290 REMark --                            con un factor de crecimiento  --
1300 REMark --------------------------------------------------------------
1310 DEFine PROCedure COLA_NUEVA(tam,factor)
1320   LET COLA_FACTOR = factor
1330   LET COLA_CABEZA = 0
1340   LET COLA_COLA   = 1
1350   DIM ArrCola(tam+1) : REMark Elementos 0 y 1 se usan como punteros
1360   COLA_INIT
1370 END DEFine 
1380 :
1390 REMark --------------------------------------------------------------
1400 REMark --     COLA_INIT -- Inicializa una cola                     --
1410 REMark --------------------------------------------------------------
1420 DEFine PROCedure COLA_INIT
1430   ArrCola(COLA_CABEZA) = 0 : REMark Puntero a cabeza
1440   ArrCola(COLA_COLA)   = 0 : REMark Puntero a cola
1450 END DEFine 
1460 :
1470 REMark --------------------------------------------------------------
1480 REMark -- b = COLA_VACIA      -- Ver si la cola esta vacia         --
1490 REMark -- RETORNA: Booleano (Si, No)                               --
1500 REMark --------------------------------------------------------------
1510 DEFine FuNction COLA_VACIA
1520   RETurn (ArrCola(COLA_CABEZA) = 0)
1530 END DEFine 
1540 :
1550 REMark --------------------------------------------------------------
1560 REMark --     COLA_ADD(dato) -- Introduce un dato en la cola, si   --
1570 REMark --                       esta llena crece al doble          --
1580 REMark --------------------------------------------------------------
1590 DEFine PROCedure COLA_ADD(dato)
1600   REMark Si la cola estΠvacia, posiciono al comienzo
1610   IF ArrCola(COLA_COLA)=0 THEN 
1620     ArrCola(COLA_CABEZA)=2
1630     ArrCola(COLA_COLA)  =1
1640   ELSE 
1650     :
1660     REMark Si la cola alcanza la cabeza, estΠlleno
1670     IF ArrCola(COLA_COLA)+1 = ArrCola(COLA_CABEZA) THEN 
1680       COLA_CAMBIA(DIMN(ArrCola)*2)
1690     END IF 
1700     :
1710     REMark Si la cola alcanza el final del arreglo
1720     IF ArrCola(COLA_COLA) = DIMN(ArrCola) THEN 
1730       IF ArrCola(COLA_CABEZA) >2 THEN 
1740         ArrCola(COLA_COLA)=1
1750       ELSE 
1760         COLA_CAMBIA(DIMN(ArrCola)*2)
1770       END IF 
1780     END IF 
1790   END IF 
1800   :
1810   ArrCola(COLA_COLA)=ArrCola(COLA_COLA)+1
1820   ArrCola(ArrCola(COLA_COLA))=dato
1830 END DEFine 
1840 :
1850 REMark --------------------------------------------------------------
1860 REMark -- v = COLA_EXTRACT    -- Saca un dato de la cola           --
1870 REMark -- RETORNA: Valor de la cabeza de la cola                   --
1880 REMark --------------------------------------------------------------
1890 DEFine FuNction COLA_EXTRACT
1900   LOCal valor
1910   :
1920   IF COLA_VACIA THEN 
1930     PRINT"Error: Cola vacia"
1940     STOP
1950   END IF 
1960   :
1970   valor=ArrCola(ArrCola(COLA_CABEZA))
1980   :: ArrCola(ArrCola(COLA_CABEZA))=0
1990   ArrCola(COLA_CABEZA)=ArrCola(COLA_CABEZA)+1
2000   IF ArrCola(COLA_CABEZA) > DIMN(ArrCola) THEN 
2010     ArrCola(COLA_CABEZA)=2
2020   END IF 
2030   :
2040   REMark Ver si cola vacia
2050   IF ArrCola(COLA_CABEZA) = ArrCola(COLA_COLA)+1 THEN COLA_INIT
2060   RETurn valor
2070 END DEFine 
2080 :
2090 REMark --------------------------------------------------------------
2100 REMark --     COLA_REDUCE     -- Reordena y reduce su tama‰o       --
2110 REMark --------------------------------------------------------------
2120 DEFine PROCedure COLA_REDUCE
2130   COLA_REORDENA
2140   COLA_CAMBIA(0)
2150 END DEFine 
2160 :
2170 REMark --------------------------------------------------------------
2180 REMark --     COLA_CAMBIAR -- Cambia el tama‰o de la cola          --
2190 REMark --------------------------------------------------------------
2200 DEFine PROCedure COLA_CAMBIA(tam)
2210   LOCal b(DIMN(ArrCola)),mintam,i
2220   :
2230   COLA_REORDENA
2240   FOR i=0 TO ArrCola(COLA_COLA) : b(i)=ArrCola(i)
2250   :
2260   mintam = ArrCola(COLA_COLA)-ArrCola(COLA_CABEZA)+1 + COLA_FACTOR
2270   IF tam < mintam      THEN tam=mintam
2280   IF tam < COLA_FACTOR THEN tam=tam+COLA_FACTOR
2290   COLA_NUEVA tam, COLA_FACTOR
2300   :
2310   FOR i=0 TO b(COLA_COLA)
2320     ArrCola(i)=b(i)
2330   END FOR i
2340 END DEFine 
2350 :
2360 REMark --------------------------------------------------------------
2370 REMark --     COLA_REORDENA   -- Reordena la cola                  --
2380 REMark --------------------------------------------------------------
2390 DEFine PROCedure COLA_REORDENA
2400   LOCal b(DIMN(ArrCola)),i,j,ini,fin
2410   :
2420   ini=ArrCola(COLA_CABEZA)
2430   fin=ArrCola(COLA_COLA)
2440   j=1
2450   :
2460   REMark Copio de la cabeza al final o a la cola
2470   FOR i=ini TO DIMN(ArrCola)
2480     IF (fin > ini) AND (i > fin) THEN EXIT i
2490     j=j+1: : b(j)=ArrCola(i)
2500   END FOR i
2510   :
2520   REMark Copio del inicio a la cola
2530   IF (fin < ini) THEN 
2540     FOR i=2 TO fin
2550       j=j+1: : b(j)=ArrCola(i)
2560     END FOR i
2570   END IF 
2580   :
2590   ArrCola(COLA_CABEZA) = 2
2600   ArrCola(COLA_COLA)   = j
2610   FOR i= 2 TO j : ArrCola(i)=b(i)
2620   :: FOR i=j+1 TO DIMN(ArrCola) : ArrCola(i)=0
2630 END DEFine 


Para realizar las pruebas de las colas he creado un pequeño programita que me las automatiza, siempre hay que definir una serie de pruebas de funcionamiento diversas y pensadas para probar los puntos vulnerables de las rutinas, y luego pasarlas para las dos rutinas, lo que al usar las funciones con el mismo nombre me aseguro de funciona y ambas pasan las mismas pruebas.

100 MODE 4: PAPER 0 : CLS
110 INPUT "Cual prefiere (1)=Simple (2)=Circular",t$
120 IF t$<>"1" AND t$<>"2" THEN GO TO 110
130 n$="mdv1_ed_cola_arreglo" & t$
140 PRINT "Cargando ";n$
150 MERGE n$
160 :
170 MODE 4: PAPER 0 : CLS : LET No=0 : LET Si=1
180 t1=DATE
190 :
200 COLA_CREAR
210 :
220 PRINT "PRUEBA 1: Introduce 3 elementos y los extrae"
230 FOR i=1 TO 3   : mete(i)
240 FOR i=1 TO 3   : saca(i)
250 PRINT
260 :
270 PRINT "PRUEBA 2: Introduce 9, extrae 5, introduce 3, extrae 9"
280 FOR i=1 TO 9   : mete(i)
290 FOR i=1 TO 5   : saca(i)
300 FOR i=10 TO 13 : mete(i)
310 FOR i=6 TO 13  : saca(i)
320 PRINT
330 :
340 PRINT "PRUEBA 3: Inroduce 9, Extrae 2, introduce 10 y reduce"
350 FOR i=1 TO 9   : mete(i)
360 FOR i=1 TO 2   : saca(i)
370 FOR i=10 TO 19 : mete(i)
380 PRINT "CM "; : COLA_REDUCE : ver
390 PRINT
400 :
410 PRINT "PRUEBA 4: Extrae elementos hasta error por vacia"
420 FOR i=3 TO 19  : saca(i)
430 t2=DATE
440 PRINT "Tard֠";t2-t1;" segundos"
450 saca(0)
460 STOP
470 :
480 DEFine PROCedure mete(a)
490   PRINT "EN ";a;" - ";
500   COLA_ADD(a)
510   ver
520 END DEFine 
530 :
540 DEFine PROCedure saca(a)
550   PRINT "SA ";
560   s=COLA_EXTRACT
570   IF a<>s THEN PRINT "ERROR" : STOP
580   PRINT s;" - "; : ver
590 END DEFine 
600 :
610 DEFine PROCedure ver
620   LOCal xx
630   :
640   IF COLA_VACIA THEN 
650     PRINT "v ";
660   ELSE 
670     PRINT "  ";
680   END IF 
690   PRINT ArrCola(0);!ArrCola(1);": ";
700   FOR xx=2 TO DIMN(ArrCola) : PRINT !ArrCola(xx);
710   PRINT
720 END DEFine 

En ambos casos ha tardado 24 segundos en ejecutarse, ya que la diferencia es mínima entre ambas, con mas datos seguro que la primera es mas rápida que la segunda si no hay aumentos de tamaño por ser mas simple, pero la segunda ganará cuando tenga muchos movimientos de entrada y salida continua, por no necesitar reordenar ni ampliar la cola.

Todo lo que he desarrollado hasta ahora de algoritmos de ordenación y de estructuras de datos está aquí para que lo podáis descargar.

No hay comentarios:

Publicar un comentario