martes, 15 de marzo de 2011

Tercer Clase

NADA DE CORRER ARCHIVOS!
si se habla de correr un archivo implica un 1 directo
todo lo que se ve aca es para no andar moviendo los registros de aca para alla
por eso existe lo de las actualizaciones diferidas, se guardan en un archivo
aparte las altas y eventualmente las bajas tambien

se puede tener un archivo chiquito ordenado, pero implica que en las busquedas
hay que primero buscar en el archivo de novedades

se trabaja con bloques, si hay lugar se inserta, sino se agrega al archivo de
altas diferidas

REGISTROS ORDENADOS

    Actualizacion de Registros ( continuacion )
      
        Eliminacion
            se puede realizar en forma analoga a la insercion (individual o en
            forma diferida)

            Tambien se puede realizar en forma logica marcando el registro
            (p.e. si los identificadores - costo de un bit por registro). No
            conviene agregar un campor para marcas de borrado ( costo de un
            byte por registro )

    Mantenimiento

        Copias de respaldo con comandos del sistema operativo

        Si se hacen eliminaciones logicas, se puede requerir eliminar
        fisicamente los registros marcados en forma periodica (compactacion del
        archivo)



ORDENAMIENTO EXTERNO

    1. ordenacion de porciones de un archivo desordenado en memoria, generando
    varios achivos de trabajo ordenados

    2. fusion de archivos ordenados

    Mejoras

        reemplazo de registros que salen ordenados por registros desordenados:
        archivos ordenados con mas registros que la capacidad del buffer de
        ordenamiento

        ordenamiento interno por monticulos: menos movimiento de registros en
        el buffer de ordenamiento


    Archivo desordenado |----------------------------------------------------|
    Ram                 |----|

    la idea basica es ir cargando de a pedazos el archivo, ordenarlos en ram y
    generar un archivo de trabajo con ese pedazo del archivo ordenado

    asi vamos a tener muchos archivos de trabajo que son como intervalos de
    registros que van a estar ordenados
    luego haciendo un merge una fusion de todos estos ordenados, se obtiene el
    final ordenado.

    Luego               |----||----||----||----||----||----||----||----||----|

    y despues del merge, se juntan los pedazos y queda el final ordenado

    el arreglo en ram va a ser siempre de la misma longitud
    se cargan tantos como capacidad tenga el arreglo
    hay muchas variantes de algoritmo
    ej, otra posiblidad, para no estar ordenando registros de datos muy
    grandes, porque para ordenarlos hay que ir moviendolos en memoria de aca
    para alla.
    mover secuencias muy grandes en ram es tambien muy costoso.
    estas operaciones no son muy frecuentes, se hace en algun momento idle

    para mejorar las posibilidades, lo que se suele hacer es, en ves de cargar
    los registros completos en ram, se carga una especie de indice a los
    registros. la clave, y un offset.
    despues se ordenan esos pares, clave offset, y despues se va accediendo al
    archivo desordenado leyendo y guardado
    pero, esa lectura de los achivos en orden tambien es espantosa porque hay
    que ir a los saltos para poder reconstruirlo ordenado.

    hay que pensar en algoritmos que muevan la menor cantidad de registros
    porque estamos hablando de registros que pueden ser muy grandes, en bytes.



    la primera aproximacion puede ser, si yo aca tengo una capacidad de n
    registros, y el archivo desordenados tiene D registros, voy a tener D/n
    archivos ordenados finales


    ustedes pueden fijarse como objetivo que la max de ram que van a usar es x
    cant de kilobytes, y hay que programar todas las estructuras para que no
    excedan esa cantidad
    ya sea que se almacene todo el registro, o claves y offsets, no hay que
    superar esa cantidad

    hay mejoras que se pueden hacer en funcion de cuantos registros se ordenan
    o que tamaño final tienen las particiones

    y tambien hay problemas con el merge en cuanto a la cantidad maxima de
    archivo a abrir.
    el merge no se va a poder hacer todo junto, va a haber que tomar de a n.
    se diseña para fusionar de hasta a lo sumo 6,7,8,10 archivos a la ves
    entonces despues la fusion se hace de a grupos para poner razonabilidad, un
    limite a los recursos a usar

    se puede pensar en estrategias para aumentar la cantidad de registros a
    ordenar por vez

    una posiblidad es cuando ya cargue una porcion y la ordene en memoria.
    a medida que voy ordenando, voy liberando espacio en ram.

    que pasa si ese registro que acabo de guardar, aprovecho a ver si el
    siguiente registro desordenado del archivo original puede ordenarse tambien
    en el bloque que tengo en ram

    ahi puede ser quizas pueda ordenar mas registros que tiene el vector de
    ordenacion.
    todas estas mejoras aparecieron cuando se trabajaba con cintas
    ahora uno puede decir para que cuernos estamos torturandonos con esto si es
    poco utilizado o poco frecuente, pero bueno son soluciones o esqumas de
    solucion para resolver problemas como incremento del bagaje que ustedes se
    van a llevar para resolver problemas.
    puede ser que en el futuro sea necesario que tengan que optimizar el
    almacenamiento, que se yo.

    bueno a medida que voy sacando los registros ordenados y aprovecho ese
    espacio para ver si puedo ordenar mas.
    por cada uno que voy sacando ordenando, voy tomando uno mas

    si me viene uno que es mayor al que me vino ordenado, puedo reordenar lo
    que tengo en ram, si es menor lo puedo dejar dormido ahi.
    lo dejo dormido ahi y sigo trabajando con un buffer mas chico.

    tambien se puede trabajar con buffering. si los registros fueran de
    longitud fija, cada ves que vamos a acceder al disco podriamos tener un
    buffer lectura y uno de escritura, porque va a diferir y agrupar los
    accesos a disco.
    cuando vamos a disco vamos por varias cosas, estamos implementando un
    read-ahead
    y cuando vamos a grabar lo mismo, grabamos cuando el buffer se revalza
    pero esas son mejoras de la programacion, ahora vamos a concentrarnos en el
    algoritmo alto nivel

    si tenemos registros de longitud fija, y tenemos que mover registros que
    son grandes, de muchos bytes por vez, el mejor algoritmo que garantiza el
    menor movimiento de bytes es el heapsort

    estamos viendo el sort externo, tiene como objetivo ordenar un archivo,
    para ordenar usamos el heapsort o ordenamiento del monton o del monticulo

    en el peor de los casos para ordenar el heap se necesitan log base 2 n, con
    n la cantidad de registros en el archivo.

    entonces en cuanto al tema de aprovechar el espacio que queda libre cuando
    escribimos archivos ordenados vamos a tener dos opciones

    una va a ser siempre trabajar con la misma estructura con el mismo arreglo,
    ordenamos de menor a mayor, usamos el heapsort, osea que cuando sacamos
    algo ordenado va a ser la raiz del heap.
    cuando vemos si podemos agregar un registro mas desordenado. en el caso que
    ese registro sea mayor a esa raiz que acabamos de insertar, lo vamos a
    insertar en la raiz
    si el que tomamos desordenado, es menor que la raiz, no lo podemos meter en
    el heap, achicamos el heap poniendo la ultima hoja en la raiz, y poniendo
    el registro dormido en esa posicion
    cuando hayamos consumido todas las posiciones del heap y se hayan quedado
    todas las posiciones del heap dormida. cerramos el archivo de trabajo y
    reordenamos el heap para seguir trabajando
    replace-selection: el tamaño de los archivos va a ser el doble que el
    tamaño en ram

        Diapositiva:
            VARIANTES ORDENAMIENTO EXTERNO
                cuando no se puede incormporar un nuevo registro al buffer de
                ordanmiento de tamaño para n registros las opciones son:

                    se achica el buffer un registro y se usa el espacio para guardar al
                    registro con identificar menor al ultimo que salio ordenado
                    (replacement selection) en promedio se ordenan 2*n registros

                    no se achica el buffer: se guarda el registro en un archivo
                    temporal que no puede tener mas registros que el buffer de
                    ordenamiento( natural selection ) en promedio se ordenan e*n
                    registros


    si el archivo original esta ordenado inicialmente, va a ordenar de una
    si esta completamente al revez, va a generar archivos de el tamaño de la
    ram


    la variante, natural selection, consiste en ves de achicar el heap y
    congelarlo en el final, lo vamos a congelar en un archivo de trabajo
    temporal que no puede ser mayor al tamaño de la ram

    es como que voy durmiendo y me va quedando mas espacio para ordenar nuevos
    eso mejora la posibilidad.
    se llama natural porque el tamaño promedio es e por n aprox 2,7
    podemos tener mas del doble que la capacidad de ordenamiento en ram


ORDENAMIENTO POR MONTICULOS
HEAPSORT

    no hace falta armar el heap en ram

    ustedes el algoritmo de heapsort lo habran hecho de mayor a menor
    sacaban de la raiz al mayor, iban ordenando sacando y quedaba ordenado asi

    aca vamos a ordenar de menor a mayor, de manera que cada vez que sacamos
    sacamos el mayor

    para armar o reconstruir el heap, vamos a siempre hace comparaciones de la
    clave de un registro con la clave del padre, o de los hijos
    un heap es tal que los hijos estan en la posicion 2*i y 2*i +1
    y los padres estan en la posicion i/2

    un heap con n registros se va almacenar en las posiciones 1 a n, la raiz
    esta en 1

    Ejemplo de Seleccion por Reemplazo

        suponemos el achivo como la siguiente secuencia
        cada clave representa todo el socotroco de datos que es el registro

        29,132,234,68,130,49,197,35,110,146,174,153,189,200,115

        buffer de ordenacion con capacidad 7

    hay una funcion de construccion del heap que se va a usar una ves al inicio
    o ciclo o etapa de crear los archivo parciales o de trabajo ordenados

    ahi vamos a usar la insercion al final del heap

    entonces, vamos a tener que tener una funcion para poder llevar a cabo este
    algoritmo, que sea armar un heap dentro de un arreglo armado
    sea la primera vez o las veces internas que hay que despertar y armar un
    heap con los que estaban dormidos
    ahi agregamos al final y la construccion la hacemos comparados de derecha a
    izquierda, comparando con los padres hasta llegar a la raiz.

    luego, para los reemplazos, las inserciones no van a ser al final, van a
    ser en la raiz, para agregar algo al principio hay que comparar con los
    hijos, para ver si hay que intercambiar o no

    esto es lo que quiero que tengan claro porque es lo que siempre hacen mal
    en las evaluaciones, al sacar la raiz, corren todo y arman de izquierda a
    derecha, pero por eso quiero puntalizar los problemas y porque
  
    tenemos estas dos situaciones, tenemos todo el archivo cargado con
    registros desordenados, vamos a armar el heap insertando al final
    como? recorremos desde la pos 1 hasta la n, y cada registro que vamos
    pisando comparamos con el padre
    hasta la posicion 1 el arreglo es un heap
    vamos a la pos 2, comparamos con el padre a ver si hay que intercambiar, es
    heap
    vamos a la pos 3, el padre en la pos 1, si hay que intercambiar. lo hacemos
    es heap hasta la pos 3
    y asi llegando hasta la pos n
    si hay que cambiar, y el padre tiene padre, hay que seguir para atras

    eso es armar el heap, se hace una sola vez, para despertar a los congelados
    o la primera vez cuando se carga con registros desordenados



        aca se carga el buffer unica vez desde el archivo

        aca en la diapositiva estan mas tenues los ya ordenados

        2. se construye el heap en el buffer

        29 | 132 234 68 130 49 197
        29 132 | 234 68 130 49 197
        29 132 234 | 68 130 49 197
        29 132 234 68 | 130 49 197
        29 68 234 132 68 130 | 49 197
        29 68 234 132 68 130 49 | 197
        29 68 49 234 132 68 130 234 197
        29 68 49 234 132 68 130 197

        aca se fueron comparando, avanzando de a una verificando que es heap de
        tamaño k, para todo k de 1 a n


        ahora sale el 29 ordenado, y entra el 35 desordenado, como 35 es mayor
        que 29 lo puedo insertar en la razi del heap

        fijense que si yo ahora para que esto siga siendo un heap tengo que
        chequear que los hijos sean mas grande
        los hijos de la pos 1 estan en 2 y 3
        como 35 < 49 ya es un heap, no hay que mover nada
        35 68 49 234 132 68 130 197

        sigo extrayendo la raiz, saco el 35, entra el 110
        110 68 49 234 132 68 130 197
        ahora no hay heap, hay que intercambiar
        49 68 110 234 132 68 130 197

        los hijos de la pos 3 estan en 6 y 7

        49 68 110 132 130 234 197

        se toma otro desordenado

        146 68 110 132 130 234 197
        68 146 110 132 130 234 197


        sigue el ejemplo...

        cada ves que el arbol vuelve a ser heap, saco la raiz

        en el ultimo caso, el nuevo que entra no es mas grande que el ultimo
        que saque
        lo mando al final, y mando el ultimo como raiz
        rearmo el heap


    4. Fusionar los archivos de trabajo ordenados:
        Leer un identificador de cada archivo y obtener el del menor
        identificador

        1,5,9,12,16,19,21
        2,4,7,10,14,17
        3,6,8

        para hacer la etapa esta de fusion, en un caso real, quizas tenemos un
        20 o 30 archivos ordenados a fusionar
        cual seria el problema de hacer una fusion total?
        buscamos el menor cada archivo, y vamos comprarando y fusionando, es
        medio malo porque hay que ir saltando de sector en sector, de cilindro
        y cilindo
        y tambien esta la limitacion de los archivos abiertos por el OS

        cual el la trampa del merge clasico?
        si uno se pone como objetivo ordenar de a 5, voy a fusionar de a 5, la
        cantidad total de archivos si es multiplo de 5 es porque es por
        casualidad
        y cuando hicimos ese merge, lo mismo, queda un subgrupo que hay que
        volver a mergear

        ademas, si estamos fusionando de a 5, ahi tenemos un problema
        combinatorio de cual se a terminar primero, cual se termina primero
        cual segundo, o de a pares, es un problema combinatorio que crea un
        numero algoritmo gigante


        como seria el algoritmo para fusionar hasta 5?
        primero hay que pensar en un protocolo de designacion de los archivos
        para ver en que fase estamos
        si tenemos 30, archivos, vamos a fusionar de a 5 y vamos a tener
        fusionados de primera etapa, vamos a tener 2 o 3 grandes, que luego
        hay que volver a fusionar

        hay que identificar los temporales, cuando se termino la fusion, etc

        primero, para fusionar de a lo sumo 5, que es lo que necesitamos?

        un arreglo de 5 estructuras cada una que tenga el file descriptor para
        ese archivo, un buffer de lectura para ese archivo.
        en rigor de verdad, la misma cantidad de memoria que usamos para la
        parte de ordenacion
        cuando se libero la ordenacion, podemos usar eso para la fusion
        1mb supongase que estamos usando para el ordenamiento, la podemos
        dividir en 5 y definir 5 estructuras para guardar nuestras
        estructuras.

        entonces que hariamos? suponganse, bueno, nose que, trabajando a escala
        que aca van a entrar de a 2 para trabajar a escala

        cargamos el 1 y 5, 1 y 4, 3 y 6, 999, 999

        1,5,9,12,16,19,21
        2,4,7,10,14,17
        3,6,8

        |1,5|2,4|3,6|999|999|

        luego hay que buscar el minimo

        nos devuelve el 1, como producto de la fusion casamos el 1, y nos
        movemos una posicion a la derecha

        volvemos a buscar el minimo, ahora el 2, movemos una pos a la derecha

        otra vez, buscamos el minimo, ahora es 3, nos movemos a la derecha

        sacamos el 4, cuando queremos movernos, nos salta que tenemos que
        recargar, entonces, recargamos 7,10 y movemos el puntero al principio

        |1,5|7,10|3,6|999|999|

        recargas dentro de los buffers de fusion





ARBOLES BALANCEADOS

    rudold bayer y ed mccreight describieron a los arboles b en un articulo en
    1972
    se mantienen balanceados en altura, con todos los nodos hoja al mismo nivel
    las operaciones de busqueda y actualizacion afectan a pocos nodos
    garantizan que mas de determinada proporcion de la capacidad de cada nodo
    este ocupada

    hay nodos interno que apuntan a otros nodos, y nodos hoja que no tienen ningun hijo

    los nodos van a ser bloques de organizacion de registros

    los registros pueden ser de longitud fija o de longitud variable

    los nodos sucesores se referencian por su posicion relativa en el archivo y
    las referencias son campos de control en los nodos

    las raices se mantienen siempre en una posicion fija del archivo, por
    ejemplo la 0

    los nodos requieren campos de control generlaes como contador de registros
    contenidos y nivel del nodo, las hojas tienen el nivel mas bajo
  
    las hojas tienen mas capacidad util que el resto de los nodos por no
    requerir referencias a sucesores

    vamos a numerar los niveles empezando desde la raiz que es el nivel 0 hasta
    llegar a la raiz, esto es asi porque hay muchas mas hojas que nodos y
    muchos mas nodos que raices, si queremos etiquetar el nivel en cada nodo,
    las mas propensas a cambiar son las hojas, por eso, son nivel 0

    una cuestion para la administracion de los nodos es la raiz va a estar en
    la posicion 0, o en la posicion 1 si quieramos tener info de cabezera del
    archivo o info de control que quisieramos guardar

    cada nodo tiene que tener como tamaño uno de bloque 2^n*512 para que ayuden
    las optimizaciones de lectura escritura de sistema operativo y disco

    ahora redefinido formalmente un arbol para trabajar en disco en un archivo,
    podemos hablar que tiene que cumplir las siguiente condiciones

ORGANIZACION B
    el nodo raiz es una hoja o tiene al menos dos nodos sucesores

    cada nodo tiene un succesor mas que la cantidad de elementos que cargue y
    a cada elemento se asocia un sucesor izquiero y otro derecho

    cada nodo excepto el raiz tiene ocupada al menos la mitad de su capacidad

    los elementos de cada odo estan ordenados por un identificador

    en cada nodo cada eleento tiene identificador mayor que el ultimo elemento
    del sucesor izquiero y menor que el primer elemento del sucesor derecho

    balancear no es pedirle un registro al hermano
    balancear es considerar la suma de carga de los dos nodos y ver que queden
    mitad y mitad



    ejemplo
      
        capacidades de elementos en nodos internos y hojas respec 4, 7
        los dos primeros campos de cada nodo indican nivel y cantidad de
        elementos
        los elementos que se muestran son solo identificadores, que pueden
        representar registros completos

        NODO0: 2, 1 ; 7(611) 8
        NODO7: 1, 2 ; 1( 184) 5 (387) 3
            NODO1: 0, 7 ; (10)(19)(40)(140)(150)(165)
            NODO5: 0, 7 ; (199)(200)(238)(268)(278)(300)(320)
            NODO3: 0, 4 ; (461)(463)(489)(569)
        NODO8: 1, 2 ; 2(801) 6 (880) 4
            NODO2: 0, 4 ; (750)(762)()....


    para la creacion del arbol, digamos para tener un arbol abierto vamos a
    necesitar un file handler, un file handler de nodos libres
    cuando se fusionan unos nodos y uno queda libre, se va al final, no es lo
    mejor
    lo mejor es tener un mapa de bits
    se puede guardar en la posicion 0 del archivo para ver cuantos registros
    hay, y tambien un mapa de bits para ver que nodo esta libre

    tambien se puede bufferizar, para tener la raiz siempre en memoria, despues
    siempre que se modifique la raiz, en ves que quede sin escribir, la guardo,
    pero la sigo dejando en ram

    entonces, digamos como que le liberamos un poco de trabajo al sistema
    operativo para bufferize mas cosas

PRIMITIVAS B
    de Creacion
        podemos crear una raiz vacia que sea hoja vacia de 0 elementos

    la Carga

        inserta elementos ordenados por identificador, los registros van a la
        ultima hoja con restricciones de contenido especiales

        aca con los arboles hay una situacion especial
        si queremos hacer una copia de resguardo
        aca la densidad de carga y todo eso es lo mismo que para los arboles en
        ram, un 75%, si tenemos la mitad y el llego, el promedio es 75%
        ehh
        si queremos hacer una copia de resguardo, podemos hacer un recorrido in
        order y bajar todos los archivos a uno secuencial
        el recorrido in order nos deja todos los registros ordenados

        si quisieramos levantar esos archivos ordenados de nuevo en una
        estructura de arbol, surge un problema, a medida que los voy metiendo
        se van partiendo a la mitad, y la densidad de carga promedio va a ser
        50%....

        si tenemos un archivo de carga ordenado tenemos que hacer una primitiva
        de carga especial

        si es un archivo de carga desordenado, podemos usar la carga comun

        para esta primitiva de carga no va hacer falta chequear unicidad ni
        buscar espacio libre
        ademas queremos que los nodos esten cargados

        lo que hago aca, quito la restriccion de que la raiz este cargada por
        lo menos la mitad y toda la rama derecha


    de Recuperacion de Registros

        buscar
            consulta o recuperacion unitaria de registro dado un identificar,
            falla si no se encurntra un reistro con este identificador
          
        listar
      

    Insercion recursiva
        hay una que trabaja con la raiz, y otra interna que trabaja con los
        hijos de la raiz

        la principal, no recursiva, puede invocarse pasando por parametro la
        raiz y el registro completo a insertar
        y va a necesitar tambien por referencia, cuando algo no entra tiene que
        subir para arriba
        hay otro parametro que es el resultado de la insercion, donde cada nodo
        cuando se invoca el resultado interno va a decir como quedo, quedo
        actualizado, si no hubo ninguna novedad, o si quedo en overflow
        el que resuelve que hacer siempre va a ser el padre de un nodo

        el principal recibe la raiz como parametro por referencia y puede
        llamar al insertar recursivo con estos tres parametros, este insertar
        recursivo recibe el nodo con quien trabajar y puede instanciar en
        memoria dinamica a lo sumo a dos hijos, para invocarse recursivamente
        cuando estemos en una instancia que este en una hoja, no necesita nada
        para insertarse recursivamente
        cuando esta en una hoja no va a usar mucho espacio, va a ser chiquito
        el registro de activacion para la funcion seria muy grande y reventaria
        la memoria stack enseguida

        en el ejemplo

            se pasa a insertar principal con la clave y la raiz, este principal
            lee el izquierdo, e invoca al insertar recursivo con el nodo 7
            el insertar recursivo, busca el 202 dentro de si, y como no esta y
            es un nodo interno no es un nodo hoja, instancia a un nodo hijo y
            se invoca recursivamente pasando por referencia al nodo 5 y el
            registro que sigue bajando por referencia
            entonces la segunda invocacion del insertar interno llego al fin de
            la recursion porque estamos en una hoja, inserta el 202, pero ya
            tenemos 7.. no cabe... bueno, pero como aca queremos que el
            algoritmo de insertar interno sea colaborativo, va a devolverle al
            padre, el que tiene que quedar en el medio y el que tiene que
            incorporar el padre para si.. aca el 202 cae en la 3ra posicion
            cuando tengamos que partir vamos a partir 4 y 3, tenemos que
            devolverle el 266
            entonces esta ultima invocacion de la recursion, acomoda todo para
            colaborar con el padre, le devuelve al padre el 266 y le dice
            revente, desborde, y termina la ejecucion de la segunda ejecucion
            se desapila, pero el hijo lo leyo el padre
            la primer invocacion lo que va a hacer es acomodar el safarancho,
            como? procura un nodo nuevo, instancia una nueva variable local, ya
            en una variable local instancio para leer y leerse recursivamente
            ahora instancia otra para poder dividir el contenido de este nodo,
            que va a hacer?
            va a copiar estos ultimos tres en el nodo nuevo, copia los ultimos
            3, a este nodo simplemente le descuenta el contenido y va a tener
            que grabar esta primera invocacion del recursivo, va a tener que
            grabar al nodo 5, va a tener que procurar una posicion nueva para
            este nodo, grabar este segundo nodo hijo nuevo, aca va a ser al
            final del archivo porque no hay nodos libres, seguramente en el
            nodo 9, y el nodo 7 va a tener que agregar dentro de si el 266,
            acompañado con el 9, a la derecha del 5
            si el 7 revienta, hace lo mismo para arriba
            fijense que el nodo 0 que tiene la raiz es principal, no es
            recursivo
            el principal tiene que custoriar que la raiz este siempre en la
            posicion 0

            diapositiva de Arboles

No hay comentarios:

Publicar un comentario en la entrada