Arreglos (Arrays)
Los arreglos son colecciones ,de tamaño fijo, de datos que ser organizan en una estrucutra lineal, podemos imaginar a un arreglo como varios contenedores alineados a los cuales se les asigna un entero cuyo conteo comienza de cero.. es decir un arrglo seria algo como loo siguiente..
[ ] [ ] [ ] [ ]
0 1 2 3
cada numero se denomina "Índice del arreglo" y nos proporciona un acceso directo a la posición en al que se encuentra el dato. Un arreglo debe declarar su tamaño en tiempo de compilación por lo que su funcionamiento es en memoria estática. El conteo de índices de un arreglo comienza desde cero, por lo que para acceder el n-esimo elemento debemos usar el índice (n-1). Es un error muy común el intentar acceder al elemento n a través del índice n, y escribir fuera de los limites del arreglo, en muchos lenguajes esto produce un error en tiempo de ejecución y el programa se cae, este es el caso de Java.. en otros como C++ el programa escribe en la locación de memoria continua al (n-1)-esimo elemento. Esto es
[ ] [ ] [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]... [ n-2 ] [ n-1 ] [ ] [ ]
Las posiciones en negrita son las posiciones contiguas en memoria, a la izquierda del primer elemento y la derecha del ultimo... c++ escribiría el dato en la primer locación en negrita a la derecha de n-1, mientras que Java nos avisaría que estamos escribiendo fuera con un ArrayOutOfBoundsException ...
Inserción:
La inserción en un arreglo se hace de forma directa, accediendo a través del índice..
Eliminación:
La eliminación resulta muy ineficiente pues debemos mover todos los datos de la estructura hacia la izquierda, de la siguiente manera,
Suponga que quiere eliminar el 3° elemento de un arreglo de dimensión 5 que contiene los siguientes valores {1,2,3,4,5}
la operación se realizaría de la siguiente manera
[1][2][3][4][5] --> [1][2][ ][4][5] ----> [1][2][4][ ][5] ---> [1][2][3][4][5][
Teniendo en cuenta que lo que se busca en la eliminación es sacar el elemento deseado, y que el siguiente ocupe su lugar..
Arreglos Bidimensionales (Matrices)
Un arreglo bidimensional es un arreglo de dos dimensiones, una especie de tabla que almacena datos cada posición esta identificada por un par (i,j) donde i es el numero de de fila y j el numero de columna.. un arreglo bidimensional se vería de la siguiente manera..
1 2 3 4 5
1 [1,1][1,2][1,3][1,4][1,5]
2 [2,1][2,2][2,3][2,4][2,5]
3 [3,1][3,2][3,3][3,4][3,5]
4 [4,1][4,2][4,3][4,4][4,5]
usaremos los arreglos bidimensionales mas adelante como una posible implementación de Grafos.
Bueno no hay mucho mas que decir de los arreglos.. pero sale a la vista la gran limitación de estos.. su imposibilidad de crecer en tiempo de ejecución.. la solución mas simple para una estructura lineal que necesita crecer en tiempo de ejecución es una Lista ligada.. que vernos a continuación.
viernes, 6 de junio de 2008
Ayuda terminada..
Hola, comentarles que ayer termine de ayudar a un amigo español que tenia ujn problema con Java.. tenia que entregar un trabajo final sobre Listas para aprovar la materia.. y solo sabia programar en Pascal... asiq trtamos de sacar algo en claro y ayer lo entrgo.. espero le vaya bine xq sino me mata!.. jaja...
jueves, 5 de junio de 2008
Una breve reseña matematica de concimientos utiles..
Sistemas de numeracion
Bueno daremos una breve reseña sobre los sistemas de numeracion mas comunes en ciencias de la computacion
-Sistema decimal
-Sistema hexadecimal
-Sistema binario
Sistema Decimal
El sistema decimal o sistema en base 10 es el sistema de numeracion que utilizamos todos los dias, este sistema posee diez digitos posibles para utilizar, 0,1,2,3,4,5,7,8 y 9.
Sistema hexadecimal
El sistema hexadecimalo sistema en base 16 es el sistema un sistema de numeracion muy usado en Cs de la comp, posee dieciseis digitos posibles para utilizar, 0,1,2,3,4,5,7,8,9,a,b,c,d,e y f . para convertir un numero de base hexa a base decimal debemos tener en cuenta que cada cifra es una potencia de 16, por lo que debemos multimplicar el valor decimal de cada cifra del numero por 16 y las posicion en que se encuentra comenzando a contar las posiciones de derecha a izq y suamarlas.. parece complicado pero es palabrerio veamos un ejemplo
1a3b = (11*(16^0))+(3*(16^1))+(10*(16^2))+(1*(16^3))= 11 + 48 +2560 + 4096 = 6715
Sistema Binario
El sistema binario o sistema en base 2 consta solo de los digitos 0 y 1, para convertir este numero a decimal usaremos la misma idea que par los hexa, solo que esta vez los numeros son pot de 2
Sistemas de numeracion
Bueno daremos una breve reseña sobre los sistemas de numeracion mas comunes en ciencias de la computacion
-Sistema decimal
-Sistema hexadecimal
-Sistema binario
Sistema Decimal
El sistema decimal o sistema en base 10 es el sistema de numeracion que utilizamos todos los dias, este sistema posee diez digitos posibles para utilizar, 0,1,2,3,4,5,7,8 y 9.
Sistema hexadecimal
El sistema hexadecimalo sistema en base 16 es el sistema un sistema de numeracion muy usado en Cs de la comp, posee dieciseis digitos posibles para utilizar, 0,1,2,3,4,5,7,8,9,a,b,c,d,e y f . para convertir un numero de base hexa a base decimal debemos tener en cuenta que cada cifra es una potencia de 16, por lo que debemos multimplicar el valor decimal de cada cifra del numero por 16 y las posicion en que se encuentra comenzando a contar las posiciones de derecha a izq y suamarlas.. parece complicado pero es palabrerio veamos un ejemplo
1a3b = (11*(16^0))+(3*(16^1))+(10*(16^2))+(1*(16^3))= 11 + 48 +2560 + 4096 = 6715
Sistema Binario
El sistema binario o sistema en base 2 consta solo de los digitos 0 y 1, para convertir este numero a decimal usaremos la misma idea que par los hexa, solo que esta vez los numeros son pot de 2
Hasta aqui va mi tutorial sobre estructuras de datos, he publcado los postes en el foro de oneble.. entren!!
Introducción a las estructuras de Datos
TDA
Un TDA, o Tipo Abstracto de Datos es básicamente un conjunto de datos de un mismo tipo que poseen operaciones para manipularlos, tales como comparaciones, asignaciones etc... Un TDA, posee una especificación lógica (independiente de su implementación) y una implementación (en un lenguaje dado). El acceso con el usuario en un TDA es limitado/nulo, los usuarios de este, solo deben conocer el nombre de las operaciones y su descripción no como llevan a cabo las tareas ni como almacenan la información para que cualquier cambio sobre estos no afecte a las aplicaciones que de el dependen.
Existen dos tipos de TDA's
Mutables: Existen operaciones que modifican sus datos
Inmutables: Las únicas operaciones de modificación son las de creación y destrucción
Estructura de datos
La técnica de abstracción de datos, nos dice que al diseñar una nueva estructura de datos, esta pasa automáticamente a ser un TDA que podrá ser implementado. La especificación lógica de una estructura, puede ser separada en los siguientes pasos..
________________________________________
1- Identificar los datos que se almacenaran en la estructura
En este paso se analiza que tipo datos se necesita que almacene la estructura..
________________________________________
2- Identificar la forma en que estos datos se organizaran:
Identificamos en este paso de que manera se relacionaran los datos dentro de la estructura.
Existen cuatro formas básicas de organizar la información
Organización lineal: los datos conforman una relación de "cadena" en la que cada elemento esta relacionado con otro de su tipo a través de una relación de uno a uno
Organización Jerárquica: en este tipo de organización la relación entre los datos es de uno a varios.
Organización en forma de Red: en este tipo de organización los elementos posen una relación de varios a varios formando una red de elementos
Organización Sin relación: en este tipo de organización los datos no tienen una relación directa, solo están dispersos en la estructura.
________________________________________
3- Definir las operaciones
Las operaciones de una estructura se pueden detallar de manera
Informal:
En la cual se escribiría un pequeño texto describiendo el funcionamiento de la operación y las pre y post condiciones
(el nombre de la operación )
(una breve descripción)
(la condición que debe tener la estructura para llevar a cabo la op)
(la modificacion que recibe la estructura luego de ejecutar la operación)
Formal: en la cual se utilizaría el lenguaje algebraico de la siguiente manera:
{Pre}Op{post} donde, pre son las precondiciones, Op es el nombre de la operación y post son las postcondiciones
________________________________________
Niveles de Abstracción
Podemos distinguir, en el desarrollo de una estructura, 3 niveles de abstracción
1- Un nivel lógico, es el nivel correspondiente a la especificación lógica de la estructura, en el nivel lógico se exponen las ideas separadas de su implementación
2- Un nivel Físico, es el nivel en el que se pasa a implementar la especificación desarrollada, en un lenguaje particular.
3- Un nivel de aplicación, es el nivel en el que se utiliza la estructura para resolver algún problema dado.
Bien hasta aquí tenemos 2 ideas separadas, la especificación lógica(independiente del lenguaje) y la implementación (en un lenguaje dado) pero como se relacionan estas dos ideas??..
veamos ahora las distintas formas de representar una estructura.
Formas de representar una estructura
La representación de una estructura es el punto de conexión entre la especificación lógica y la implementación. En esta etapa, se lleva al nivel de abstracción lógica al inicio del nivel físico, aquí se decide como se representaran las estructuras en memoria para poder explotar sus características.
Las estructuras se pueden almacenar de dos formas básicamente:
-Almacenamiento continuo: los datos de la estructura se almacenan en memoria en locaciones continuas de la siguiente manera
[1] [2] [3] .... [n]
donde cada [] representa una localidad de memoria, 1,2,... ,n los datos almacenados las relaciones están dadas según la posición en la que se encuentran
-Almacenamiento disperso: los datos se encuentran en distintos lugares de memoria pero están relacionados por enlaces que le indican dónde se encuentra el sig. elemento
[(k+1)|d(k+2)]...[1|d(2)] [3|d(4)] [4|d(k)] [2|d(3)]... [K|d(k+1)]....
esto es, en cada locación de memoria se almacena, el dato, y la dirección "d" del siguiente dato de la estructura
Ventajas y desventajas de un almacenamiento continuo
Por un lado, el almacenamiento continuo permite, una gran facilidad de recorrido, y muchas veces gran eficiencia a la hora de verificar propiedades sobre la estructura, pero se caen de manera drástica a la hora de insertar y eliminar elementos, ya que como no existe un espacio entre cada elemento, la única forma de insertar un elemento entre medio de 2 existentes es desplazar la estructura completamente, al igual que al eliminar un elemento, se deben mover todos los elementos para ocupar el espacio libre
Ventajas y desventajas del almacenamiento disperso
El almacenamiento disperso posee como principal ventaja, el hecho de que la memoria se utiliza de forma mucho mas eficiente, y se pueden insertar y eliminar elementos de la estructura sin tener que desplazar el resto de los ya insertados. Po r otro lado, una representación dispersa presenta una caída en eficiencia espacial, por el hecho de que cada localidad almacena dos componentes, un dato y una referencia al siguiente dato de la estructura.
Conclusiones finales
Por lo general, cualquier estructura puede ser representada usando almacenamientos continuos o dispersos, pero muchas veces uno sobrepasa al otro por alguna característica particular. Es decir, en algunas estructuras necesitaremos un rápido recorrido sin importar el tiempo de inserción o preferiremos una rápida inserción y eliminación, esto dependerá de la estructura que se este creando y de la capacidad de diseño del programador...
Memoria estática y Memoria Dinámica
Bueno, aquí posteando nuevamente.. en este post analizaremos las diferencias entre la memoria estática y la memoria dinámica
Memoria RAM de una computadora
Bueno, para comenzar con la memoria estática, debemos primero hacer una breve intro al concepto de memoria RAM. Bien la memoria RAM (Random Acces Memory) es la memoria temporal de una computadora, todo lo que se almacena en RAM se pierde automáticamente al cortarse el suministro de electricidad hacia esta. Traten de imaginar a la memoria como una serie de cajas alineadas a la cual se le asigna una dirección especifica en base hexadecimal, algo como lo que sigue
.... [0x001 ] [0x002] [0x003]...
la computadora accede a las localidades de memoria a través de esas direcciones hexa.. podemos distinguir dos tipos de almacenamiento a la hora de programar, el almacenamiento en memoria estática y el almacenamiento en memoria dinámica
Memoria estática
Al escribir un programa, declaramos las variables y constantes que este usara, y las utilizamos a nuestro placer sabiendo que siempre tendremos ese lugar para guardar valores, pero por que podemos asegurar esto???.. Pues bien. A la hora de compilar, el compilador evalúa la cantidad de variables y constantes que este contiene y reserva para su ejecución el espacio de memoria necesario para realizar los almacenamientos sin tener que solicitar más. Esta memoria, que se reserva en tiempo de compilación se conoce como Memoria Estática, la memoria estática no puede crecer ni achicarse en tiempo de ejecución (cuando se esta corriendo el programa) lo que nos presenta una inmensa desventaja. Cuando un programador calcula el espacio de memoria que puede llegar a ocupar su programa, decimos que este esta evaluando cuanto puede "escalar" su programa, es decir como se comportara el programa frente a entradas de distintos tamaños. El uso de memoria estática produce programas que no escalan bien, pues por lo general no se conca el tamaño de entrada que puede llegar a manejar un programa por lo que se podrían tomar dos decisiones, una seria reservar un espacio lo suficientemente grande como para almacenar y procesar cualquier entrada, pero esto significaría un inmenso desperdicio de memoria si el programa no llega a entradas grandes durante una de sus ejecuciones, y por mas grande que lo hagamos, igualmente se presentaría una limitación en algún punto distante, la otra opción y la que por lo general se debe utilizar es el uso de la Memoria Dinámica..
Memoria Dinámica
Bien, como dijimos la memoria estática presenta una gran limitación para proyectos que deben escalar. Entonces como podemos solucionar el problema de no conocer hasta la cantidad de datos que manejara nuestro programa?.. pues bien, la respuesta es la memoria dinámica, pues como funciona??
La memoria RAM , posee un espacio denominado HEAP, este espacio esta reservado para los pedidos de memoria del sistema operativo. El crecimiento y decrecimiento del HEAP, esta determinado por el decrecimiento y crecimiento (respectivamente) de la pila de ejecución. Ahora bien, en memoria estática, los valores se almacenaban directamente en la posición de memoria reservada, en un almacenamiento continuo cuyo tamaño esta dado por el tamaño que utiliza el tipo de datos para almacenarse en memoria, por ejemplo supongamos que un entero ocupa 5 bytes, entonces se reservan 5 bytes de memoria, y el valor almacenado ocupa esas 5 locaciones, de la siguiente forma.
[ val ] [val ] [val ] [val ] [val ]
0x001 0x002 0x003 0x004 0x005
La memoria dinámica, se asigna en tiempo de ejecución cuando el programa la solicita, es decir con el uso de esta memoria, se crean espacios de de memoria mientras el programa se esta ejecutando, pero ahora bien, como creamos accedemos a estos espacios??..
La creación de valores en memoria dinámica se hace pidiendo al SO (sistema operativo de ahora en mas) que permita el acceso a una de las locaciones disponibles del HEAP para almacenar nuestros datos, ahora nuestros programas solo estarán limitados por la capacidad del HEAP, y no por el limite que fijamos en tiempo de programación. Pero como podemos acceder a estos espacios creados?
Como estos espacios se crean en tiempo de ejecución, no tienen una etiqueta asociada necesariamente, por lo que necesitamos una forma de ubicarlos dentro del HEAP, por lo que entra en juego un concepto muy importante de programación, los punteros.
Punteros
El concepto de un puntero puede resultar bastante difícil de entender al principio, pero es indispensable una buena comprensión de este.
Un puntero no es nada mas ni nada menos que una variable que almacena una dirección de memoria. Es decir, un puntero guarda una referencia a una posición que almacena un elemento dado, es decir si usáramos un puntero para referenciar la variable propuesta en el ejemplo anterior
[ val ] [val ] [val ] [val ] [val ]
0x001 0x002 0x003 0x004 0x005
El puntero debería apuntar a la dirección donde comienza el dato almacenado, esto seria,
Puntero a val-- [0x001]
Los punteros se pueden utilizar para referenciar las direcciones que creamos en el HEAP, cuando una variable en memoria dinámica pierde su referencia se dice que se produjo una fuga de memoria o (Memory Leak) , es muy importante evitar las fugas de memoria, por lo que debemos tener muy en claro como estamos referenciando los espacios de memoria creados. Entonces, si tenemos un puntero a un elemento, lo único que tenemos es almacenada la dirección donde se encuentra el elemento, pues bueno, entonces podemos tener varios punteros que contengan el mismo valor?
La respuesta es si, varios punteros que apuntan a un objeto conforman muchas referencias a un mismo elemento por lo que modificar cualquiera de los punteros modifica al elemento en si. Las estructuras de datos tiene una gran base en el uso de punteros, pues nos permitirán que las estructuras crezcan y se achiquen según necesitemos. Es muy importante también saber que si solicitamos una localidad de memoria HEAP debemos ser buenos y devolverla en algún momento para que esta quede a disposición del SO nuevamente y pueda ser reutilizada.
Bien esto concluye una breve intro a los conceptos de memoria estática y dinámica, muy importantes para poder continuar con el desarrollo del curso. En próximos posts comenzaremos con el análisis de las primeras estructuras básicas nativas de todo lenguaje, los arreglos.
Introducción a las estructuras de Datos
TDA
Un TDA, o Tipo Abstracto de Datos es básicamente un conjunto de datos de un mismo tipo que poseen operaciones para manipularlos, tales como comparaciones, asignaciones etc... Un TDA, posee una especificación lógica (independiente de su implementación) y una implementación (en un lenguaje dado). El acceso con el usuario en un TDA es limitado/nulo, los usuarios de este, solo deben conocer el nombre de las operaciones y su descripción no como llevan a cabo las tareas ni como almacenan la información para que cualquier cambio sobre estos no afecte a las aplicaciones que de el dependen.
Existen dos tipos de TDA's
Mutables: Existen operaciones que modifican sus datos
Inmutables: Las únicas operaciones de modificación son las de creación y destrucción
Estructura de datos
La técnica de abstracción de datos, nos dice que al diseñar una nueva estructura de datos, esta pasa automáticamente a ser un TDA que podrá ser implementado. La especificación lógica de una estructura, puede ser separada en los siguientes pasos..
________________________________________
1- Identificar los datos que se almacenaran en la estructura
En este paso se analiza que tipo datos se necesita que almacene la estructura..
________________________________________
2- Identificar la forma en que estos datos se organizaran:
Identificamos en este paso de que manera se relacionaran los datos dentro de la estructura.
Existen cuatro formas básicas de organizar la información
Organización lineal: los datos conforman una relación de "cadena" en la que cada elemento esta relacionado con otro de su tipo a través de una relación de uno a uno
Organización Jerárquica: en este tipo de organización la relación entre los datos es de uno a varios.
Organización en forma de Red: en este tipo de organización los elementos posen una relación de varios a varios formando una red de elementos
Organización Sin relación: en este tipo de organización los datos no tienen una relación directa, solo están dispersos en la estructura.
________________________________________
3- Definir las operaciones
Las operaciones de una estructura se pueden detallar de manera
Informal:
En la cual se escribiría un pequeño texto describiendo el funcionamiento de la operación y las pre y post condiciones
Formal: en la cual se utilizaría el lenguaje algebraico de la siguiente manera:
{Pre}Op{post} donde, pre son las precondiciones, Op es el nombre de la operación y post son las postcondiciones
________________________________________
Niveles de Abstracción
Podemos distinguir, en el desarrollo de una estructura, 3 niveles de abstracción
1- Un nivel lógico, es el nivel correspondiente a la especificación lógica de la estructura, en el nivel lógico se exponen las ideas separadas de su implementación
2- Un nivel Físico, es el nivel en el que se pasa a implementar la especificación desarrollada, en un lenguaje particular.
3- Un nivel de aplicación, es el nivel en el que se utiliza la estructura para resolver algún problema dado.
Bien hasta aquí tenemos 2 ideas separadas, la especificación lógica(independiente del lenguaje) y la implementación (en un lenguaje dado) pero como se relacionan estas dos ideas??..
veamos ahora las distintas formas de representar una estructura.
Formas de representar una estructura
La representación de una estructura es el punto de conexión entre la especificación lógica y la implementación. En esta etapa, se lleva al nivel de abstracción lógica al inicio del nivel físico, aquí se decide como se representaran las estructuras en memoria para poder explotar sus características.
Las estructuras se pueden almacenar de dos formas básicamente:
-Almacenamiento continuo: los datos de la estructura se almacenan en memoria en locaciones continuas de la siguiente manera
[1] [2] [3] .... [n]
donde cada [] representa una localidad de memoria, 1,2,... ,n los datos almacenados las relaciones están dadas según la posición en la que se encuentran
-Almacenamiento disperso: los datos se encuentran en distintos lugares de memoria pero están relacionados por enlaces que le indican dónde se encuentra el sig. elemento
[(k+1)|d(k+2)]...[1|d(2)] [3|d(4)] [4|d(k)] [2|d(3)]... [K|d(k+1)]....
esto es, en cada locación de memoria se almacena, el dato, y la dirección "d" del siguiente dato de la estructura
Ventajas y desventajas de un almacenamiento continuo
Por un lado, el almacenamiento continuo permite, una gran facilidad de recorrido, y muchas veces gran eficiencia a la hora de verificar propiedades sobre la estructura, pero se caen de manera drástica a la hora de insertar y eliminar elementos, ya que como no existe un espacio entre cada elemento, la única forma de insertar un elemento entre medio de 2 existentes es desplazar la estructura completamente, al igual que al eliminar un elemento, se deben mover todos los elementos para ocupar el espacio libre
Ventajas y desventajas del almacenamiento disperso
El almacenamiento disperso posee como principal ventaja, el hecho de que la memoria se utiliza de forma mucho mas eficiente, y se pueden insertar y eliminar elementos de la estructura sin tener que desplazar el resto de los ya insertados. Po r otro lado, una representación dispersa presenta una caída en eficiencia espacial, por el hecho de que cada localidad almacena dos componentes, un dato y una referencia al siguiente dato de la estructura.
Conclusiones finales
Por lo general, cualquier estructura puede ser representada usando almacenamientos continuos o dispersos, pero muchas veces uno sobrepasa al otro por alguna característica particular. Es decir, en algunas estructuras necesitaremos un rápido recorrido sin importar el tiempo de inserción o preferiremos una rápida inserción y eliminación, esto dependerá de la estructura que se este creando y de la capacidad de diseño del programador...
Memoria estática y Memoria Dinámica
Bueno, aquí posteando nuevamente.. en este post analizaremos las diferencias entre la memoria estática y la memoria dinámica
Memoria RAM de una computadora
Bueno, para comenzar con la memoria estática, debemos primero hacer una breve intro al concepto de memoria RAM. Bien la memoria RAM (Random Acces Memory) es la memoria temporal de una computadora, todo lo que se almacena en RAM se pierde automáticamente al cortarse el suministro de electricidad hacia esta. Traten de imaginar a la memoria como una serie de cajas alineadas a la cual se le asigna una dirección especifica en base hexadecimal, algo como lo que sigue
.... [0x001 ] [0x002] [0x003]...
la computadora accede a las localidades de memoria a través de esas direcciones hexa.. podemos distinguir dos tipos de almacenamiento a la hora de programar, el almacenamiento en memoria estática y el almacenamiento en memoria dinámica
Memoria estática
Al escribir un programa, declaramos las variables y constantes que este usara, y las utilizamos a nuestro placer sabiendo que siempre tendremos ese lugar para guardar valores, pero por que podemos asegurar esto???.. Pues bien. A la hora de compilar, el compilador evalúa la cantidad de variables y constantes que este contiene y reserva para su ejecución el espacio de memoria necesario para realizar los almacenamientos sin tener que solicitar más. Esta memoria, que se reserva en tiempo de compilación se conoce como Memoria Estática, la memoria estática no puede crecer ni achicarse en tiempo de ejecución (cuando se esta corriendo el programa) lo que nos presenta una inmensa desventaja. Cuando un programador calcula el espacio de memoria que puede llegar a ocupar su programa, decimos que este esta evaluando cuanto puede "escalar" su programa, es decir como se comportara el programa frente a entradas de distintos tamaños. El uso de memoria estática produce programas que no escalan bien, pues por lo general no se conca el tamaño de entrada que puede llegar a manejar un programa por lo que se podrían tomar dos decisiones, una seria reservar un espacio lo suficientemente grande como para almacenar y procesar cualquier entrada, pero esto significaría un inmenso desperdicio de memoria si el programa no llega a entradas grandes durante una de sus ejecuciones, y por mas grande que lo hagamos, igualmente se presentaría una limitación en algún punto distante, la otra opción y la que por lo general se debe utilizar es el uso de la Memoria Dinámica..
Memoria Dinámica
Bien, como dijimos la memoria estática presenta una gran limitación para proyectos que deben escalar. Entonces como podemos solucionar el problema de no conocer hasta la cantidad de datos que manejara nuestro programa?.. pues bien, la respuesta es la memoria dinámica, pues como funciona??
La memoria RAM , posee un espacio denominado HEAP, este espacio esta reservado para los pedidos de memoria del sistema operativo. El crecimiento y decrecimiento del HEAP, esta determinado por el decrecimiento y crecimiento (respectivamente) de la pila de ejecución. Ahora bien, en memoria estática, los valores se almacenaban directamente en la posición de memoria reservada, en un almacenamiento continuo cuyo tamaño esta dado por el tamaño que utiliza el tipo de datos para almacenarse en memoria, por ejemplo supongamos que un entero ocupa 5 bytes, entonces se reservan 5 bytes de memoria, y el valor almacenado ocupa esas 5 locaciones, de la siguiente forma.
[ val ] [val ] [val ] [val ] [val ]
0x001 0x002 0x003 0x004 0x005
La memoria dinámica, se asigna en tiempo de ejecución cuando el programa la solicita, es decir con el uso de esta memoria, se crean espacios de de memoria mientras el programa se esta ejecutando, pero ahora bien, como creamos accedemos a estos espacios??..
La creación de valores en memoria dinámica se hace pidiendo al SO (sistema operativo de ahora en mas) que permita el acceso a una de las locaciones disponibles del HEAP para almacenar nuestros datos, ahora nuestros programas solo estarán limitados por la capacidad del HEAP, y no por el limite que fijamos en tiempo de programación. Pero como podemos acceder a estos espacios creados?
Como estos espacios se crean en tiempo de ejecución, no tienen una etiqueta asociada necesariamente, por lo que necesitamos una forma de ubicarlos dentro del HEAP, por lo que entra en juego un concepto muy importante de programación, los punteros.
Punteros
El concepto de un puntero puede resultar bastante difícil de entender al principio, pero es indispensable una buena comprensión de este.
Un puntero no es nada mas ni nada menos que una variable que almacena una dirección de memoria. Es decir, un puntero guarda una referencia a una posición que almacena un elemento dado, es decir si usáramos un puntero para referenciar la variable propuesta en el ejemplo anterior
[ val ] [val ] [val ] [val ] [val ]
0x001 0x002 0x003 0x004 0x005
El puntero debería apuntar a la dirección donde comienza el dato almacenado, esto seria,
Puntero a val-- [0x001]
Los punteros se pueden utilizar para referenciar las direcciones que creamos en el HEAP, cuando una variable en memoria dinámica pierde su referencia se dice que se produjo una fuga de memoria o (Memory Leak) , es muy importante evitar las fugas de memoria, por lo que debemos tener muy en claro como estamos referenciando los espacios de memoria creados. Entonces, si tenemos un puntero a un elemento, lo único que tenemos es almacenada la dirección donde se encuentra el elemento, pues bueno, entonces podemos tener varios punteros que contengan el mismo valor?
La respuesta es si, varios punteros que apuntan a un objeto conforman muchas referencias a un mismo elemento por lo que modificar cualquiera de los punteros modifica al elemento en si. Las estructuras de datos tiene una gran base en el uso de punteros, pues nos permitirán que las estructuras crezcan y se achiquen según necesitemos. Es muy importante también saber que si solicitamos una localidad de memoria HEAP debemos ser buenos y devolverla en algún momento para que esta quede a disposición del SO nuevamente y pueda ser reutilizada.
Bien esto concluye una breve intro a los conceptos de memoria estática y dinámica, muy importantes para poder continuar con el desarrollo del curso. En próximos posts comenzaremos con el análisis de las primeras estructuras básicas nativas de todo lenguaje, los arreglos.
miércoles, 4 de junio de 2008
Les comento que hoy comeze cmo moderador de un foro de programacion en la seccion de estructuras de datos.. pueden ver y preguntar aqui es un gran foro visiten y dejen sus preguntas..
Empezando mi blog...
Hola a todos los que caigan en mi blog, la idea principal es crear un espacio para compartit todo aquello que voy aprendiendo acerca de la programacion y las ciencias de la computacion en general..
Suscribirse a:
Entradas (Atom)