miércoles, 23 de noviembre de 2016

Programación del Sinclair QL (XIV): Estructuras de Datos. Pilas. QuickSort no recursivo



La estructura de datos fundamental

Mezclaré un poco los temas de algoritmos y de estructuras de datos, ya que son los dos aspectos fundamentales de la programación. Comenzamos por la mas usada en todos los ordenadores, las pilas son la base de los lenguajes, tanto nuestro querido Basic como de los modernos lenguajes orientados a objeto, todos usan las pilas para guardar datos de manera temporal.

Imaginemos una pila de platos. Cuando queremos poner un plato lo debemos ubicar siempre encima, y si deseamos sacar un plato siempre lo debemos retirar de la cima. De esta forma podemos ir poniendo y sacando platos de la pila, hasta que la pila se quede vacía, o hasta que ocupe todo el espacio y no pueda creer mas. El primer plato que pongamos en la pila no lo podemos sacar hasta que no hayamos retirado todos los que estén encima, por lo que se dice que el primero en entrar será el último en salir.

En Basic clásico, cuando se encuentra un GOSUB se introduce en la pila la dirección desde la que se ha llamado, y cuando encuentra el RETURN la saca de la pila y salta a la línea siguiente. De esta forma si encuentra varios GOSUB seguidos, introduce las direcciones en la pila, y luego siempre sabe a donde regresar con los RETURN conforme los encuentra. En los lenguajes modernos se usan mucho las pilas para pasar los parámetros de las funciones en las llamadas.

Hay una forma sencilla de crear una pila usando un arreglo y una variable que haga de puntero a la cima. Se inicia el puntero a cero, cuando se añade un elemento se incrementa el puntero y se añade en la posición del arreglo a la que apunta, si se solicita un elemento se leer de la posición apuntada y luego se resta uno. Si el apuntador es cero la pila está vacía. Esta técnica solo requiere saber de antemano el tamaño máximo de la pila, lo que no siempre es posible, pero funciona en cualquier versión del BASIC. En SuperBASIC es sencillo, al existir el elemento cero del arreglo lo usaré para guardar el puntero a la cima. Creo varias funciones para su manejo, una que inicia la pila con un tamaño por defecto, otra que la crea con un tamaño inicial, uno que nos indica si la pila está vacía, la que introduce un valor (en inglés PUSH) y hace crecer el tamaño de la pila si es necesario, la que lee un valor (en inglés POP), una para compactar la pila y reducir su tamaño al mínimo, y una ultima para cambiar el tamaño de la pila, tanto hacia arriba como hacia abajo.

6150 REMark --------------------------------------------------------------
6160 REMark --     PILA_CREAR      -> Crea la pila                      --
6170 REMark --------------------------------------------------------------
6180 DEFine PROCedure PILA_CREAR
6190   REMark Espacio minimo en la pila
6200   LET PILA_FACTOR = 10
6210   DIM ArrPila(PILA_FACTOR)
6220 END DEFine 
6230 :
6240 REMark --------------------------------------------------------------
6250 REMark --     PILA_NUEVA(tam) -> Crea la pila con un tama‰o        --
6260 REMark --------------------------------------------------------------
6270 DEFine PROCedure PILA_NUEVA(tam)
6280   LET PILA_FACTOR = tam
6290   DIM ArrPila(tam)
6300 END DEFine 
6310 :
6320 REMark --------------------------------------------------------------
6330 REMark -- b = PILA_VACIA      -> Ver si la pila esta vacia         --
6340 REMark -- RETORNA: Booleano (Si, No)                               --
6350 REMark --------------------------------------------------------------
6360 DEFine FuNction PILA_VACIA
6370   RETurn NOT ArrPila(0)
6380 END DEFine 
6390 :
6400 REMark --------------------------------------------------------------
6410 REMark --     PILA_PUSH(dato) -> Introduce un dato en la pila, si  --
6420 REMark --                        esta llena crece al doble         --
6430 REMark --------------------------------------------------------------
6440 DEFine PROCedure PILA_PUSH(dato)
6450   IF ArrPila(0) = DIMN(ArrPila) THEN 
6460     PILA_CAMBIA(ArrPila(0)*2)
6470   END IF 
6480   ArrPila(0)=ArrPila(0)+1
6490   ArrPila(ArrPila(0))=dato
6500 END DEFine 
6510 :
6520 REMark --------------------------------------------------------------
6530 REMark -- v = PILA_POP        -> Saca un dato de la pila           --
6540 REMark -- RETORNA: Valor de la cima de la pila                     --
6550 REMark --------------------------------------------------------------
6560 DEFine FuNction PILA_POP
6570   IF PILA_VACIA THEN 
6580     PRINT"Error: Pila vacia"
6590     STOP
6600   END IF 
6610   ArrPila(0)=ArrPila(0)-1
6620   RETurn ArrPila(ArrPila(0)+1)
6630 END DEFine 
6640 :
6650 REMark --------------------------------------------------------------
6660 REMark --     PILA_COMPACTA   -> Compacta la pila                  --
6670 REMark --------------------------------------------------------------
6680 DEFine PROCedure PILA_COMPACTA
6690   PILA_CAMBIA(ArrPila(0)+PILA_FACTOR)
6700 END DEFine 
6710 :
6720 REMark --------------------------------------------------------------
6730 REMark --     PILA_CAMBIAR -> Cambia el tamaño de la pila          --
6740 REMark --------------------------------------------------------------
6750 DEFine PROCedure PILA_CAMBIA(tam)
6760   LOCal b(tam),i
6770   :
6780   FOR i=0 TO tam
6790     IF i > DIMN(ArrPila) THEN EXIT i
6800     b(i)=ArrPila(i)
6810   END FOR i
6820   IF tam < ArrPila(0)  THEN tam=ArrPila(0)+PILA_FACTOR
6830   IF tam < PILA_FACTOR THEN tam=tam+PILA_FACTOR
6840   DIM ArrPila(tam)
6850   FOR i=0 TO tam : ArrPila(i)=b(i)
6860 END DEFine 


La línea 6460 es la que permite hacer crecer la pila si se llena. Hay varias técnica posibles para fijar el tamaño en que se aumentar la pila automáticamente:
  • La mas sencilla es usar in incremento fijo, de forma que cada vez que se llene se aumente su tamaño en ese valor. Funciona si la pila crece pocas veces y en poca cantidad cada vez. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño + Cantidad. Si elegimos 10 aumenta en forma de 10, 20, 30, 40, 50, 60, 70...
  • Una muy usada es incrementar en un porcentaje del tamaño, de esta forma conforme mas crece el tamaño se va adaptando.  Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño + (Anterior_Tamaño * Porcentaje / 100), si elegimos porcentaje del 50% el crecimiento es 10, 15, 23, 35, 53, 80, 120,...
  • El crecimiento exponencial es sencillo y efectivo, igual que el porcentual intenta crecer mas cuanto mas grande sea el tamaño inicial, se basa en multiplicar el tamaño por un factor, de forma que aumenta mas rápido que usando el porcentual, aunque hay que usarlo con cuidado ya que el tamaño crece muy rápido, pero es bueno si hay pocas ampliaciones. Se usa la fórmula Nuevo_Tamaño = Anterior_Tamaño * Factor. En mi rutina uso el factor 2 que es bueno para crecer en un factor 10, 20, 40, 80, 160, 320, 640...
La rutina PILA_CAMBIA es la que permite cambiar el tamaño del arreglo. Como SuperBASIC no permite ampliar el arreglo de manera estándar, es necesario crear un arreglo temporal, copiar la pila en el, cambiar el tamaño de la pila, y volver a copiar el temporal a la pila. Esto cuesta un tiempo, por eso hay que buscar un tamaño de incremento adecuado.

Veamos un uso práctico de la pila, escribiré el algoritmo QuickSort para que en lugar de ser recursivo use la pila para ir guardando inicio y fin de las sublistas, y así cambio el proceso por uno iterativo.

ALGORITMO QuickSort_Pila (arreglo, primero, ultimo)
 
  Pila.Push(primero, ultimo)      
  REPETIR
 
    Pila.Pop(primero, ultimo)   
    REPETIR
      izquierda ← primero
      derecha ← ultimo
      pivote ← ENTERO((primero + ultimo)/2))    
    
      REPETIR
        MIENTRAS arreglo(izquierda) < arreglo(pivote) 
          izquierda ← izquierda + 1
        FIN_MIENTRAS
        MIENTRAS arreglo(derecha) > arreglo(pivote) do 
         derecha ← derecha - 1
        FIN_MIENTRAS
        SI izquierda <= derecha ENTONCES
          SI izquierda <> derecha ENTONCES
            INTERCAMBIA_ELEMENTOS(izquierda, derecha)
          FIN_SI       
          izquierda ← izquierda + 1
          derecha ← derecha - 1
        FIN_SI
      HASTA_QUE izquierda >= derecha
      
      SI derecha - primero > ultimo - izquierda ENTONCES 
        SI primero < derecha ENTONCES
          Pila.Push(primero, derecha)
        FIN_SI
        primero ← izquierda
      SI NO
        SI izquierda < ultimo ENTONCES 
          Pila.Push(izquierda, ultimo)
        FIN_SI
        ultimo ← derecha
      FIN_SI
    HASTA_QUE primero >= ultimo
  HASTA_QUE Pila.Vacia 


Esto se traduce muy sencillo a superBASIC, solo hay que tomar nuestra rutina QuickSort y añadirle primero la creación de la pila, introducimos en ella como inicio comienzo y fin, cambiamos la llamada recursiva por introducir inicio y fin de la sublista en la pila, y seguir iterando hasta que la pila quede vacía.

100 DEFine PROCedure Rapida_Pila (arreglo,sentido,primero,ultimo)
110   IF ultimo=0 THEN ultimo=DIMN(arreglo)
120   QsortP arreglo, sentido, primero, ultimo
130 END DEFine 
140 :
150 DEFine PROCedure QsortP (arreglo,sentido,primero,ultimo)
160   LOCal rep_pila,pivote,izquierda,derecha,r1,r2,r3
170   :
180   PILA_CREAR
190   PILA_PUSH primero : PILA_PUSH ultimo
200   REPeat rep_pila
210     :
220     REMark Sacamos en orden inverso al introducido
230     ultimo = PILA_POP : primero = PILA_POP
240     :
250     IF (primero+1 = ultimo) THEN 
260       IF COMPARA(arreglo(primero),arreglo(ultimo),sentido) = 1 THEN 
270         SWAP arreglo(primero),arreglo(ultimo)
280       END IF 
290     ELSE 
300       izquierda = primero
310       derecha = ultimo
320       pivote = INT((primero + ultimo) / 2)
330       :
340       REPeat r1
350         IF (izquierda > pivote) OR (derecha < pivote) THEN EXIT r1
360         REPeat r2
370           IF (izquierda > pivote) THEN EXIT r2
380           IF COMPARA(arreglo(izquierda),arreglo(pivote),sentido)<>-1
390             EXIT r2
400           END IF 
410           izquierda = izquierda + 1
420         END REPeat r2
430         REPeat r3
440           IF (derecha < pivote) THEN EXIT r3
450           IF COMPARA(arreglo(derecha),arreglo(pivote),sentido)<>1
460             EXIT r3
470           END IF 
480           derecha = derecha - 1
490         END REPeat r3
500         SWAP arreglo(izquierda), arreglo(derecha)
510         izquierda = izquierda + 1
520         derecha = derecha - 1
530         IF (izquierda - 1) = pivote THEN 
540           derecha = derecha + 1
550           pivote = derecha
560         ELSE IF (derecha + 1) = pivote THEN 
570           izquierda = izquierda - 1
580           pivote = izquierda
590         END IF 
600       END REPeat r1
610       IF (primero < pivote-1) THEN 
620          PILA_PUSH primero : PILA_PUSH pivote-1
630       END IF 
640       IF (ultimo > pivote+1) THEN 
650         PILA_PUSH pivote+1 : PILA_PUSH ultimo
660       END IF 
670     END IF 
680     IF PILA_VACIA THEN EXIT rep_pila
690   END REPeat rep_pila
700 END DEFine 

No hay comentarios:

Publicar un comentario