| Autor |
Mensaje |
pablo.martin.viva
Nivel 3
Registrado: 28 May 2006
Mensajes: 46
Ubicación: Capital Federal
Carrera: Sistemas
|
|
El tema en si es simple, lo que se plantea, vos generalmente, bah en el TP 3 mio de Mandrafina que era de Grafos del Compumap, y en el TP 2 de Mandrafina que era emitir un listado ordenado de habitantes que vivian en un codigo postal, con 4 archivos que se relacionaban entre si era bastante complicado, porque tenias que acceder eficientemente a 4 archivos.
En si la forma de encarar el problema, es primero, ver que relaciones hay entre los datos, por ejepmlo si como campo de un registro de un archivo hace relacion a un campo de un registro de otro archivo (Generalmente en lo que las bases de datos se lo llama foreign key o clave foranea). Viendo que relaciones hay, habria que plantear de que forma es mas eficiente acceder a los archivos.
Con todo esto me refiero que si yo supongamos tengo un archivo de personas con nombre, apellido, documento y necesito acceder eficientemente al archivo tanto por documento como por apellido.
Es primero y principal tratar al archivo y las listas indices que ordenan al archivo como un solo TDA, ya que tenes una forma mas centralizada de acceder a los datos, y todo eso se encarga el TDA de actualizar cada cosa, sabes que si actualizas un dato en el TDA IndicePersona lo va a hacer siempre y no te lo vas a comer vos en el medio del codigo, pero principalmente porque es toda una unidad, los datos del archivo como los indices sobre los cuales està ordenado el archivo.
Tambien yo plantearia en ese sentido tener un TDA Indice Persona cuyos atributos internos serian un ArchivoDeRegistros que apunte al archivo de personas fisico, y dos TDA Listas internos, uno que tenga datos interno un registro apellido y la posicion del registro en disco de ese dato. y otra lista que tenga como tipo de dato interno un registro que tenga documento y posicion del registro en el archivo de personas.
De forma que el TDA Indice Personas tendria una interfaz centralizada para acceder de forma eficiente a los datos de forma ordenada, en este caso tanto por apellido como por documento, ya que tengo dos listas internas que me mantienen los datos ordenados en memoria por los campos que yo quiero ordenar.
supongamos que mi TDA Indice Personas tiene un metodo llamado
Persona buscarPersona(IndicePersonas& indice, string documento) ;
Este metodo lo unico que hace es buscar en la lista que està ordenada por documentos y le pide la ubicacion del registro de la persona en el archivo, luego accede al archivo y devuelve ese regsitro de persona.
Lo mismo para el metodo
Persona buscarPersona(IndicePersonas& indice, string apellido);
Salvo que este metodo va a buscar a su lista interna que està ordenada por apellidos y le pide la ubicacion del registro en disco en el archivo y lo devuelve.
En el caso de que dos archivos tengan relacion entre si, como me toco en mi TP de Algo II de Grafos, donde tenia un archivo de calles con un ID de calle y un archivo de Tramos de calle con un ID de calle y un ID de tramo, yo cree un TDA Indice para cada archivo y despues un TDA Indice para ambos indices en conjunto.
Espero que todo esto se entienda un poco mas, y sino te explico despues con mas claridad.
Saludos
PABLO
|
|
|
|
|
|
| |
       |
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
Pregunta de tipo que mira desde afuera y no cursó dicha materia, etc.; ¿por qué plantean (desde la cátedra, no ustedes) resolver un problema de eficiencias utilizando justamente un tipo de datos taaan pobre en tiempos de acceso como las listas?... o sea, esté ordenada o no la lista la complejidad del acceso a un elemento X es la misma; el mismo problema puede resolverse con arrays desordenados con la misma eficiencia y con un array ordenado ya la eficiencia mejora drásticamente (ni hablar con árboles).
¿Alguien me da una idea al respecto?; insisto, pregunto como tipo que no sabe los mambos de la cátedra y quiere enterarse un poco más.
|
|
|
|
_________________
 ![[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]](images/latex/d678cf273c99d2546c259db3422b3d968b184721_0.png "[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]") ![[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]](images/latex/1e6580e1ed9e054ddefd65c0551c670c44f57f38_0.png "[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]")
|
|
   |
 |
|
pablo.martin.viva
Nivel 3
Registrado: 28 May 2006
Mensajes: 46
Ubicación: Capital Federal
Carrera: Sistemas
|
|
El problema es que yo en el archivo no se cuantos datos o registros voy a tener y puede que cambie con el tiempo, eso ya de por si me descarta los arrays que son estàticos.
Tambien podria plantear el hecho de usar arrays dinàmicos, o un puntero a un registro y eso convertirlo en un array dinàmico, pero es mucho mas ineficiente que una lista, ya que primero tengo espacios en memoria malgastados y segundo cuando el array dinamico alcanzó su maximo fisico tengo que crear un nuevo array mas grande y copiar todos los elementos del array original al nuevo array redimensionado, se pierde mucha eficiencia en eso y encima en mantener los arrays ordenados, mas alla de que se use heapsort o quicksort que son relativamente rapidos en un caso normal.
Por otro lado a este punto de la materia, al menos en las dos primeras tercios del cuatrimestre ves solamente estructuras de datos lineales tipo listas, pilas y colas, no ven estructuras arboreas, eso se ve al final, es por eso que de una se plantea hacer un indice de un archivo usando una lista, por mas ineficiente que sea.
De todas formas se sabe que para indices lo mejor que hay uasta el momento y lo que usan casi todas las bases de datos son las estructuras de arbol B y sus derivadas como arbol B+, arbol B* etc.
Creo que toda la vida prefiero un arbol de busqueda binario balanceado, ya sea un AVL, un red black tree o un arbol 2,3,4 antes que una lista, pero por los conocimientos que tienen al inicio y mitad de la cursada de Algoritmos II, no podemos esperar que implementen un indice de un archivo usando un arbol B, B+ o ni siquiera un arbol AVL.
Saludos
PABLO
|
|
|
|
|
|
| |
|
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
| pablo.martin.viva escribió:
|
|
Tambien podria plantear el hecho de usar arrays dinàmicos, o un puntero a un registro y eso convertirlo en un array dinàmico, pero es mucho mas ineficiente que una lista, ya que primero tengo espacios en memoria malgastados y segundo cuando el array dinamico alcanzó su maximo fisico tengo que crear un nuevo array mas grande y copiar todos los elementos del array original al nuevo array redimensionado, se pierde mucha eficiencia en eso y encima en mantener los arrays ordenados, mas alla de que se use heapsort o quicksort que son relativamente rapidos en un caso normal.
|
Pero, ¿no estás levantando los archivos completos primeros para tenerlos después en memoria?; en ese caso podés construir un array (dinámico, claro) desordenado, en principio, y ordenarlo después... sea como sea, no hay ningún punto en el cual eso sea más ineficiente que usar una lista; y si no querés tener todo en bloques consecutivos podés clusterizar al array.
El tiempo de acceso a un dato de un array ordenado es de ![[tex]\mathcal O (\log n)[/tex]](images/latex/878791ecf39a4371f5813a36fc3fd386eaef9d83_0.png "[tex]\mathcal O (\log n)[/tex]") versus el ![[tex]\mathcal O (n)[/tex]](images/latex/715a7938f28137c00eb61d3f8781ff7f75d30e30_0.png "[tex]\mathcal O (n)[/tex]") de la lista; los órdenes de inserción son ambos de ; por lo tanto construir una u otra estructura lleva el mismo tiempo...
Si no quisieras tener el array ordenado mientras lo creás y ordenarlo al final, bajás la complejidad total del ![[tex]\mathcal O (n^2)[/tex]](images/latex/59ca3a6cb31fe673ea1b67331a1daa8f1870e7b0_0.png "[tex]\mathcal O (n^2)[/tex]") que te da armar una lista completa o un array completo ordenado a ![[tex]\mathcal O(n \log n)[/tex]](images/latex/66ca11f3a1b2668aced0c41adc9a718175e75e7a_0.png "[tex]\mathcal O(n \log n)[/tex]") ...
Es decir, nunca resolver eso con listas va a ser eficiente; mirado desde cualquier punto de vista, que resolverlo con arreglos... mi pregunta apuntaba a si, más allá de la aplicación de listas, que es el TDA contenedor más facil de implementar, y que está bien que lo implementen; pasa por este tema de que les hagan creer que realmente ganan algo implementándolo de esa manera... o sea, es mentira que sea eficiente; es muy lindo como trabajo de aplicación, pero las cosas que traen de Algoritmos I ya funcionan mejor para solucionar un problema así.
|
|
|
|
_________________
|
|
| |
|
|
cazador4
Nivel 4
Registrado: 17 Jun 2005
Mensajes: 106
Ubicación: Caballito
Carrera: No especificada
|
|
Mira la idea de que den pilas, listas y colas no es ver el optimo rendimiento de la aplicacion.
Te digo esto dps de ir a una clase que daban un ejercicio de final, de catedra carolo.
te toman 2 ejercicios uno de alguna primitiva de con arboles y otra sobre alguna nueva primitiva del tda AB.
te digo que no quieren optimo rendimiento porque hoy por ejemplo nos dieron un final resuelto que habia como 4 llamadas a funciones que mandaban como parametro 2 veces el arbol y sabiendo que siempre tenes que manejarte con recursividad..
imaginate si tenes un arbol enorme...
pincharia al toque ya que necesitarias muchisima memoria...
no se si se entiende.. pero uno de los ayudantes me contesto a mi pregunta: ¿pero esto no es completamente imposible de que ande? a lo que respondio que se toma basicamente la estructura del arbol sin importar que realmente sea un caso que se use...
de todas formas no me parece mal ya que la idea creo es poder entender un arbol, como se maneja, etc etc mas alla de que dps hagas algo eficiente o no con el....
saludos.
|
|
|
|
|
|
| |
 |
|
Sebastian Santisi
Administrador Técnico
Edad: 42
Registrado: 23 Ago 2005
Mensajes: 17451
|
|
| cazador4 escribió:
|
|
de todas formas no me parece mal ya que la idea creo es poder entender un arbol, como se maneja, etc etc mas alla de que dps hagas algo eficiente o no con el....
|
Ah, bárbaro entonces... lo que me había llamado la atención es que varios habían mencionado la eficiencia; a eso había venido mi comentario.
Con respecto al stack, perdele el miedo... si un árbol binario completo tiene ![[tex]\mathrm{log}_2 (\mathrm{cantidad de hojas})[/tex]](images/latex/4d3828f7c6731b09ed67eaa8fe506bcee5a4a268_0.png "[tex]\mathrm{log}_2 (\mathrm{cantidad de hojas})[/tex]") de altura, creeme que un árbol que te reventara el stack en la recursividad no entra en memoria... hacé algún programita de testing sencillo para probar cuánto mide tu stack, de la onda de:
void f(void) {
static int i = 0;
std::cout << "Llamada " << i++ << std::endl;
f();
}
int main(void) {
f();
return 0;
}
Vas a ver que el stack tarda muuuucho en pinchar; si querés apurar el test, metele un array adentro a la función así ocupa más.
Donde sí es más facil pinchar el stack es haciendo un recorrido recursivo de una lista, porque tenés tantos llamados como nodos. Igual es dificil. Más que nada, es lento por los pusheos y popeos de cada call a la función.
|
|
|
|
_________________
|
|
| |
|
|
Conan
Moderador
Edad: 39
Registrado: 30 Ago 2005
Mensajes: 2390
Ubicación: Longchamps
Carrera: Electrónica y Informática
|
|
  |
|
|
|
|
Ir a página Anterior 1, 2
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro
No podés responder a temas en este foro
No podés editar tus mensajes en este foro
No podés borrar tus mensajes en este foro
No podés votar en encuestas en este foro
No Podéspostear archivos en este foro
No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
.