Repaso: elegir la estructura correcta
En esta página
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Una biblioteca de barrio decide llevar su administración con algoritmos en vez de con papel. Necesita, al mismo tiempo, varias cosas: sumar cada libro nuevo al catálogo en el orden en que llega, poder consultar los datos de un libro por su código sin revisar el catálogo entero, saber al instante si una persona ya está registrada como socia, anotar en una lista de espera a quienes quieren un libro que ya está prestado, y poder deshacer el último préstamo si el bibliotecario se equivoca al registrarlo. Ninguna de esas cinco necesidades pide la misma estructura, y nada en el enunciado lo aclara de entrada.
Los dos posts anteriores de esta serie presentaron, en total, cinco estructuras: lista, diccionario, conjunto, pila y cola. Este post no agrega ninguna nueva: resuelve un único problema, de principio a fin, reconociendo en cada tramo cuál de esas cinco corresponde. Ningún título de sección va a decir "acá va un diccionario" ni "acá va una pila": eso es, en cada tramo, lo primero que hay que decidir.
El catálogo completo de la biblioteca guarda todos los libros en el orden en que se fueron incorporando, sin ninguna clave que los distinga entre sí: dos ejemplares distintos pueden tener el mismo título, y lo único que importa es que quede el registro de que entraron, uno después del otro.
Pista: pensar qué estructura permite mantener un orden de llegada exacto sin necesitar una clave única por cada valor, y sin problema si dos valores se repiten.
algoritmo agregar_al_catalogo(catalogo, libro):
agregar libro al final de catalogo
devolver catalogoCon catalogo en ["Cien años de soledad", "Rayuela", "El aleph"], agregar_al_catalogo(catalogo, "Ficciones") deja catalogo en ["Cien años de soledad", "Rayuela", "El aleph", "Ficciones"]: cuatro libros, en el orden exacto en que se fueron sumando. Ni un diccionario ni un conjunto sirven acá: el primero necesitaría una clave que nada en el problema pide todavía, y el segundo ni siquiera podría guardar el mismo título dos veces.
Cada libro tiene además un código único (su ISBN interno), y en el mostrador hace falta poder consultar el título que le corresponde a un código sin recorrer el catálogo entero libro por libro.
Pista: hay una clave -el código- y un valor que depende de ella -el título-. Esa relación, clave con valor, ya tiene una estructura propia.
algoritmo datos_de_libro(indice, codigo):
devolver el valor asociado a la clave codigo en indiceCon indice en {"B001": "Cien años de soledad", "B002": "Rayuela", "B003": "El aleph"}, datos_de_libro(indice, "B002") devuelve "Rayuela" directamente, sin comparar el código pedido contra cada entrada del catálogo. La lista del tramo anterior podría guardar los mismos libros, pero para encontrar uno por código habría que revisarla posición por posición: el diccionario resuelve exactamente el problema de buscar por algo que no es una posición.
Antes de prestar un libro, hay que confirmar que quien lo pide ya está registrado como socio de la biblioteca. No hace falta ningún otro dato sobre esa persona en este momento, solo saber si está o no está en el registro.
Pista: la pregunta es de presencia pura, sin ninguna clave que buscar ni ningún valor asociado que leer. Eso descarta tanto a la lista como al diccionario.
algoritmo es_socio(socios, dni):
devolver socios contiene dniCon socios en {"30111222", "30333444", "30555666"}, es_socio(socios, "30333444") devuelve verdadero, y es_socio(socios, "30999888") devuelve falso. Un diccionario también podría resolver esto -asociando cada documento a, por ejemplo, verdadero-, pero cargaría una clave con un valor que ninguna pregunta necesita leer nunca. El conjunto pide exactamente lo que hace falta y nada más.
Cuando alguien pide un libro que ya está prestado, se anota en una lista de espera para ese título. Cuando el ejemplar se devuelve, se le avisa a la primera persona que se anotó, sin importar cuántas más se hayan sumado después mientras esperaba.
Pista: hay dos momentos distintos -anotarse, y ser atendido- y el segundo tiene que respetar el orden exacto en que ocurrió el primero. Eso es una regla de entrada y salida, no de presencia ni de búsqueda por clave.
algoritmo anotar_en_espera(espera, dni):
encolar dni en espera
devolver esperaalgoritmo atender_siguiente(espera):
devolver desencolar esperaCon espera en ["30111222", "30555666"], anotar_en_espera(espera, "30777000") la deja en ["30111222", "30555666", "30777000"]. Si en ese momento se devuelve un ejemplar y se llama a atender_siguiente(espera), el resultado es "30111222" -el primero que se anotó, aunque ya haya otros dos esperando detrás- y espera queda en ["30555666", "30777000"]. Una pila resolvería mal este mismo problema: llamaría siempre al último en anotarse, no al primero.
El sistema guarda además un historial de los préstamos más recientes, para poder deshacer el último si el bibliotecario se equivoca al cargarlo -por ejemplo, si registra un préstamo a la persona equivocada-. Deshacer siempre afecta al movimiento más reciente, nunca a uno anterior.
Pista: acá el orden importa al revés que en la lista de espera. Lo último que entró es lo primero que hay que poder sacar.
algoritmo deshacer_ultimo_prestamo(historial):
devolver desapilar historialCon historial en ["B002 a 30111222", "B003 a 30333444"], deshacer_ultimo_prestamo(historial) devuelve "B003 a 30333444" -el préstamo cargado más recientemente- y deja historial en ["B002 a 30111222"]. Si la cola del tramo anterior se usara acá, se deshacería siempre el préstamo más viejo del historial, exactamente al revés de lo que hace falta.
Con los cinco tramos resueltos por separado, se arma un único algoritmo que llama a cada uno y junta los resultados, siguiendo la misma idea de plan_mudanza del post de repaso anterior: el algoritmo principal no vuelve a resolver nada, solo pide cada resultado y lo combina.
algoritmo dia_en_la_biblioteca(catalogo, libro_nuevo, indice, codigo_consulta, socios, dni_consulta, espera, dni_nuevo, historial):
llamar a agregar_al_catalogo con catalogo y libro_nuevo para obtener el catalogo_actualizado
llamar a datos_de_libro con indice y codigo_consulta para obtener el titulo
llamar a es_socio con socios y dni_consulta para obtener el resultado_socio
llamar a anotar_en_espera con espera y dni_nuevo para obtener la espera_actualizada
llamar a atender_siguiente con espera_actualizada para obtener el siguiente_atendido
llamar a deshacer_ultimo_prestamo con historial para obtener el prestamo_deshecho
devolver el catalogo_actualizado, el titulo, el resultado_socio, el siguiente_atendido y el prestamo_deshechoCon los datos de todo el post (el catálogo de tres libros más "Ficciones", el índice de tres códigos, los tres socios registrados, la lista de espera de dos personas más quien se anota al final, y el historial de dos préstamos): dia_en_la_biblioteca devuelve el catálogo con sus cuatro libros, "Rayuela" como título consultado, verdadero como resultado de socio, "30111222" como siguiente atendido de la fila, y "B003 a 30333444" como el préstamo que se deshizo. Cinco estructuras distintas -una lista, un diccionario, un conjunto, una cola y una pila- resolvieron, cada una, el tramo que le correspondía, sin que el enunciado general lo separara por adelantado.
Elegir la estructura correcta no es memorizar cuál usar en cada caso: es reconocer qué pregunta hay que responder. Si importa el orden de llegada y puede haber valores repetidos, es una lista. Si hace falta buscar por algo que no es una posición, es un diccionario. Si la única pregunta es presencia, es un conjunto. Si hay que respetar quién llegó primero, es una cola. Si hay que deshacer lo más reciente, es una pila.
El próximo paso de la serie deja las estructuras de datos por un momento y se concentra en algo que esta serie viene usando desde el post de descomposición sin haberlo formalizado todavía: qué es, con precisión, una función.