Hola de nuevo Antes de partir para el fin de semana, queremos compartir con ustedes una traducción del material que se preparó específicamente para el curso básico "Desarrollador iOS" .
Decidir qué estructura de datos usar para representar un conjunto de valores dado es a menudo mucho más difícil de lo que parece. Dado que cada tipo de estructura de datos está optimizado para un cierto número de casos de uso, elegir el ajuste adecuado para cada conjunto de datos a menudo puede tener un gran impacto en el rendimiento de nuestro código.
La biblioteca estándar de Swift viene con tres estructuras de datos principales:
Array ,
Dictionary y
Set , cada una de las cuales tiene su propio conjunto de optimizaciones, ventajas y desventajas. Veamos algunas de sus características, así como los casos en los que podríamos tener que ir más allá de la biblioteca estándar para encontrar la estructura de datos correcta para nuestros propósitos.
Linealidad de matriz
Array es probablemente una de las estructuras de datos más utilizadas en Swift, y existen buenas razones para ello. Almacena sus elementos secuencialmente, se clasifican fácilmente de una manera predecible, y cualquier valor puede almacenarse en él: desde estructuras hasta instancias de clases y otras colecciones.
Por ejemplo, aquí usamos una matriz para almacenar una colección de formas colocadas en un
Canvas en una aplicación de dibujo. Luego, cuando necesitamos renderizar el lienzo en una imagen, simplemente pasamos por la matriz para dibujar cada elemento usando
DrawingContext , de la siguiente manera:
struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } }
Cuando se trata de la representación secuencial de todas nuestras formas, como hicimos anteriormente, la matriz se adapta perfectamente. Las matrices no solo almacenan sus elementos de una manera muy eficiente, sino que también tienen un orden de clasificación garantizado, que proporciona un orden de representación predecible sin tener que realizar ningún trabajo adicional.
Sin embargo, como todas las demás estructuras de datos, las matrices tienen sus inconvenientes. En nuestro caso, encontraremos uno de sus inconvenientes cuando queramos eliminar formas del lienzo. Dado que los elementos de la matriz se almacenan por índice, siempre necesitamos encontrar primero con qué índice está asociada la figura antes de poder eliminarla:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } }
Al principio, el código anterior puede no parecer tan problemático, pero puede convertirse en un cuello de botella de rendimiento para cualquier lienzo que contenga una gran cantidad de formas, ya que
firstIndex es lineal (O (N)) en términos de
complejidad temporal .
Aunque podemos evitar esta limitación cuando usamos nuestro tipo de Canvas. Por ejemplo, siempre haciendo referencia a cifras por índice, y no por valor o ID, esto haría que nuestro código sea más complejo y frágil, ya que siempre tendríamos que estar seguros de que nuestros índices no caducan cuando el lienzo con el que estamos trabajando cambiará
Conjuntos de velocidad
En cambio, veamos si podemos optimizar el
Canvas sí cambiando su estructura de datos subyacente. Teniendo en cuenta el problema anterior, una de nuestras ideas iniciales podría ser utilizar
Set (sets) en lugar de
Array . Como ya discutimos en
El poder de los conjuntos en Swift , una de las ventajas significativas de los conjuntos sobre las matrices es que tanto la inserción como la eliminación siempre se pueden realizar en un tiempo constante (O (1)), ya que los elementos se almacenan por valor hash, no por índice.
Al actualizar
Canvas para usar conjuntos, obtenemos lo siguiente:
struct Canvas { var shapes: Set<Shape> func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func remove(_ shape: Shape) { shapes.remove(shape) } }
Una vez más, el código anterior puede verse bien, e incluso se compila sin problemas. Sin embargo, aunque resolvimos el problema de eliminación, también perdimos nuestro orden de representación estable, porque, a diferencia de las matrices, los conjuntos no nos dan un orden de clasificación garantizado, que es un obstáculo en esta situación, ya que parece que dibujaremos formas personalizadas en Al azar
Índices de indexación
Sigamos experimentando. Ahora veamos si podemos optimizar el
Canvas introduciendo un
Dictionary , que nos permite buscar el índice de cualquier forma en función de su ID. Comenzaremos cambiando el nivel de acceso de nuestra matriz de
shapes a
private para que podamos controlar la inserción de elementos utilizando el nuevo método de
add . Y cada vez que se agrega una nueva figura, también agregamos su índice a nuestro diccionario:
struct Canvas { private var shapes = [Shape]() private var indexes = [Shape.ID : Int]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { let index = shapes.count indexes[shape.id] = index shapes.append(shape) } }
Como ahora siempre sabemos en qué índice se almacena una figura determinada, podemos realizar rápidamente la eliminación en tiempo constante, como cuando se usa un conjunto:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } }
Sin embargo, hay un error bastante grave en nuestra nueva implementación de
Canvas . Cada vez que eliminamos una forma, invalidamos todos los índices que son más altos que el que acabamos de eliminar, ya que cada uno de estos elementos se moverá un paso al comienzo de la matriz. Podríamos resolver este problema ajustando estos índices después de cada eliminación, pero esto nuevamente nos llevaría de vuelta al territorio O (N), que tratamos de evitar desde el principio.
Nuestra última implementación tiene sus méritos. En general, usar una combinación de dos estructuras de datos puede ser una gran idea en tales situaciones, ya que a menudo podemos usar las fortalezas de una estructura de datos para compensar las deficiencias de la otra, y viceversa.
Entonces, intentemos nuevamente con una combinación diferente, pero esta vez comencemos considerando nuestros
requisitos reales :
- Necesitamos inserciones y eliminaciones para tener una complejidad de tiempo constante, y debería ser posible eliminar la figura sin conocer su índice base.
- Necesitamos un orden de clasificación garantizado para poder mantener un orden de representación estable.
Al observar los requisitos anteriores, resulta que aunque necesitamos un orden de clasificación estable, en realidad no necesitamos índices. Esto haría que la lista vinculada sea perfecta para nuestro caso de uso.
Las listas vinculadas consisten en nodos, donde cada nodo contiene un enlace (o enlace) al siguiente nodo de la lista, lo que significa que se puede ordenar de una manera predecible, sin la necesidad de actualizaciones de índice cuando se elimina un elemento. Sin embargo, la biblioteca estándar de Swift (hasta ahora) no contiene un tipo de lista vinculada, por lo que si queremos usarla, primero debemos crearla.
Crea una lista vinculada
Comencemos declarando una estructura de
List que rastreará el primer y último nodo de nuestra lista. Haremos que estas dos propiedades sean de solo lectura fuera de nuestro tipo para garantizar la coherencia de los datos:
struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? }
A continuación, creemos nuestro tipo de nodo (nodo), que crearemos una clase, porque queremos poder referirnos a los nodos
por referencia y no por valor . Nuestra lista estará doblemente conectada, lo que significa que cada nodo contendrá un enlace tanto a su próximo vecino como al anterior. Cada nodo también almacenará un valor, como este:
extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } }
La razón por la que debilitamos la propiedad anterior es para evitar los bucles de retención que aparecerían si mantuviéramos enlaces fuertes en ambas direcciones. Para obtener más información sobre cómo evitar los ciclos de retención, consulte el artículo "Administración de memoria" .
Esto es en realidad todo el código que necesitamos para que los valores se puedan almacenar en nuestra lista vinculada. Pero esta es solo la primera parte del rompecabezas, como en cualquier otra colección, también queremos poder iterar sobre él y cambiar su contenido. Comencemos con las iteraciones que, gracias al diseño Swift muy orientado al protocolo, se pueden implementar fácilmente al garantizar el cumplimiento del protocolo
Sequence e implementar el método
makeIterator :
extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator {
Dado que la iteración anterior es muy simple, utilizamos la biblioteca estándar AnyIterator para evitar la necesidad de implementar un tipo de iterador personalizado. Para escenarios más complejos, se puede implementar agregando una coincidencia a IteratorProtocol .
A continuación, agreguemos una API para modificar nuestra lista vinculada, comenzando con las inserciones. Ampliaremos la
List con el método
append , que agrega un nuevo nodo para el valor insertado y luego devuelve este nodo, de esta manera:
extension List { @discardableResult mutating func append(_ value: Value) -> Node { let node = Node(value: value) node.previous = lastNode lastNode?.next = node lastNode = node if firstNode == nil { firstNode = node } return node } }
Arriba, usamos el atributo @discardableResult , que le dice al compilador que no genere ninguna advertencia si no se utilizó el resultado de llamar a nuestro método, ya que no siempre estamos interesados en el nodo que se creó.
Dado que las listas vinculadas no se basan en índices, sino en mantener una cadena de valores a través de enlaces, la implementación de eliminaciones es solo una cuestión de actualizar los siguientes y anteriores vecinos de los nodos remotos para que apunten entre sí:
extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous
Con base en lo anterior, la versión inicial de nuestra Lista está completa y estamos listos para verificarla en acción. Actualicemos el lienzo para usar nuestra nueva lista, así como un diccionario que nos permita encontrar rápidamente qué nodo coincide con una ID de forma dada:
struct Canvas { private var shapes = List<Shape>() private var nodes = [Shape.ID : List<Shape>.Node]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { nodes[shape.id] = shapes.append(shape) } mutating func remove(_ shape: Shape) { guard let node = nodes.removeValue(forKey: shape.id) else { return } shapes.remove(node) } }
Ahora tenemos inserciones y eliminaciones rápidas, y un orden de clasificación predecible, sin la necesidad de agregar complejidad adicional al proceso de llamada, ¡es genial! Y, dado que nuestra nueva Lista es un tipo completamente universal, ahora podemos usarla siempre que necesitemos almacenar valores sin un índice de forma lineal.
Conclusión
A pesar de que las estructuras de datos son tan fundamentales que se pueden encontrar en todo tipo de lenguajes de programación, la decisión sobre cuál usar en cada situación específica puede requerir una cantidad significativa de pensamiento, prueba y experimentación, especialmente si queremos para que nuestro código siga siendo efectivo a medida que crece el conjunto de datos.
También es muy probable que la estructura de datos adecuada para cada situación específica pueda cambiar con el tiempo a medida que cambian nuestros requisitos, y a veces usar una combinación de varias estructuras de datos, y no solo una, puede ser una forma de lograr las características de rendimiento requeridas.
Continuaremos explorando el mundo de las estructuras de datos en los siguientes artículos, enfocándonos en aquellos que aún no están implementados en la biblioteca estándar. Como con tantas otras cosas, a veces necesitamos expandir nuestro pensamiento más allá de Swift para elegir la estructura de datos correcta para cada situación.
Puede encontrarme
en Twitter o enviarme un correo electrónico si tiene alguna pregunta, comentario o comentario.
Gracias por su atencion!