Olá novamente. Antes de partir para o fim de semana, queremos compartilhar com você uma tradução do material que foi preparado especificamente para o curso básico "iOS-developer" .
Decidir qual estrutura de dados usar para representar um determinado conjunto de valores geralmente é muito mais difícil do que parece. Como cada tipo de estrutura de dados é otimizada para um certo número de casos de uso, a escolha do ajuste certo para cada conjunto de dados geralmente pode ter um grande impacto no desempenho do nosso código.
A biblioteca padrão do Swift vem com três estruturas de dados principais -
Array ,
Dictionary e
Set , cada uma com seu próprio conjunto de otimizações, vantagens e desvantagens. Vejamos algumas de suas características, bem como casos em que talvez precisemos ir além da biblioteca padrão para encontrar a estrutura de dados correta para nossos propósitos.
Linearidade da matriz
Array é provavelmente uma das estruturas de dados mais usadas no Swift, e há boas razões para isso. Ele armazena seus elementos sequencialmente, eles são facilmente classificados de maneira previsível e qualquer valor pode ser armazenado nele: de estruturas a instâncias de classes e outras coleções.
Por exemplo, aqui usamos uma matriz para armazenar uma coleção de formas colocadas em uma
Canvas em um aplicativo de desenho. Então, quando precisamos renderizar a tela em uma imagem, passamos pela matriz para desenhar cada elemento usando o
DrawingContext - da seguinte maneira:
struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } }
Quando se trata de renderização seqüencial de todas as nossas formas, como fizemos acima, a matriz se encaixa perfeitamente. As matrizes não apenas armazenam seus elementos de uma maneira muito eficiente, mas também têm uma ordem de classificação garantida, o que fornece uma ordem de renderização previsível sem a necessidade de fazer nenhum trabalho adicional.
No entanto, como todas as outras estruturas de dados, as matrizes têm suas desvantagens. No nosso caso, encontraremos uma de suas desvantagens quando queremos remover formas da tela. Como os elementos da matriz são armazenados por índice, sempre precisamos primeiro descobrir a qual índice a figura está associada antes de podermos excluí-la:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } }
A princípio, o código acima pode não parecer tão problemático, mas pode se tornar um gargalo de desempenho para qualquer tela que contenha um grande número de formas, pois o
firstIndex é linear (O (N)) em termos de
complexidade de
tempo .
Embora possamos contornar essa limitação, usamos o nosso tipo de tela. Por exemplo, sempre nos referindo a figuras por índice, e não por valor ou ID - isso tornaria nosso código mais complexo e mais frágil, pois sempre teríamos que ter certeza de que nossos índices não expiram quando a tela com a qual estamos trabalhando vai mudar.
Conjuntos de velocidade
Em vez disso, vamos ver se podemos otimizar o próprio
Canvas alterando sua estrutura de dados subjacente. Considerando o problema acima, uma de nossas idéias iniciais pode ser usar
Set (sets) em vez de
Array . Como já discutimos em
O poder dos conjuntos no Swift , uma das vantagens significativas dos conjuntos sobre as matrizes é que a inserção e a exclusão sempre podem ser executadas em um tempo constante (O (1)), pois os itens são armazenados pelo valor do hash, não pelo índice.
Ao atualizar o
Canvas para usar conjuntos, obtemos o seguinte:
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) } }
Novamente, o código acima pode parecer correto e até compila sem problemas. No entanto, embora tenhamos resolvido o problema de exclusão, também perdemos nossa ordem de renderização estável - porque, diferentemente das matrizes, os conjuntos não nos dão uma ordem de classificação garantida - o que é um obstáculo nessa situação, pois parece que vamos desenhar formas personalizadas em aleatoriamente.
Indexação de índices
Vamos continuar a experimentar. Agora vamos ver se podemos otimizar o
Canvas introduzindo um
Dictionary , o que nos permite procurar o índice de qualquer forma com base em seu ID. Começaremos alterando o nível de acesso de nossa matriz de
shapes para
private para que possamos controlar a inserção de elementos usando o novo método
add . E sempre que uma nova figura é adicionada, também adicionamos seu índice ao nosso dicionário:
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 agora sempre sabemos em qual índice uma determinada figura está armazenada, podemos executar rapidamente a exclusão em tempo constante, como ao usar um conjunto:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } }
No entanto, há um bug bastante sério em nossa nova implementação do
Canvas . Cada vez que excluímos uma forma, na verdade invalidamos todos os índices superiores ao que acabamos de excluir - já que cada um desses elementos move uma etapa para o início da matriz. Poderíamos resolver esse problema ajustando esses índices após cada exclusão, mas isso nos levaria novamente ao território O (N), que tentamos evitar desde o início.
Nossa mais recente implementação tem seus méritos. Em geral, o uso de uma combinação de duas estruturas de dados pode ser uma ótima idéia em tais situações, pois geralmente podemos usar os pontos fortes de uma estrutura de dados para compensar as deficiências da outra e vice-versa.
Então, vamos tentar novamente com uma combinação diferente, mas desta vez vamos começar considerando nossos
requisitos reais :
- Precisamos de inserções e exclusões para ter uma complexidade de tempo constante e deve ser possível excluir a figura sem conhecer seu índice base.
- Precisamos de uma ordem de classificação garantida para poder manter uma ordem de renderização estável.
Observando os requisitos acima, verifica-se que, embora precisemos de uma ordem de classificação estável, na verdade não precisamos de índices. Isso tornaria a lista vinculada perfeita para o nosso caso de uso.
As listas vinculadas consistem em nós, em que cada nó contém um link (ou link) para o próximo nó da lista, o que significa que pode ser classificado de maneira previsível - sem a necessidade de atualizações de índice quando um item é excluído. No entanto, a biblioteca padrão Swift (até agora) não contém um tipo de lista vinculada; portanto, se quisermos usá-lo, primeiro devemos criá-lo.
Crie uma lista vinculada
Vamos começar declarando uma estrutura de
List que rastreará o primeiro e o último nó da nossa lista. Tornaremos essas duas propriedades somente leitura fora do nosso tipo para garantir a consistência dos dados:
struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? }
Em seguida, vamos criar nosso tipo de nó (nó), que criaremos uma classe, porque queremos poder nos referir a nós
por referência e não por valor . Nossa lista será duplamente conectada, o que significa que cada nó conterá um link para o próximo vizinho e o anterior. Cada nó também armazenará um valor - assim:
extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } }
O motivo pelo qual enfraquecemos a propriedade anterior é evitar os loops de retenção que apareceriam se mantivéssemos laços fortes nas duas direções. Para saber mais sobre como evitar ciclos de retenção, consulte o artigo "Gerenciamento de memória" .
Na verdade, esse é todo o código que precisamos para que os valores possam ser armazenados em nossa lista vinculada. Mas esta é apenas a primeira parte do quebra-cabeça, como em qualquer outra coleção, também queremos poder iterá-lo e alterar seu conteúdo. Vamos começar com iterações que, graças ao design Swift, muito orientado ao protocolo, podem ser facilmente implementadas, garantindo a conformidade com o protocolo
Sequence e implementando o método
makeIterator :
extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator {
Como a iteração acima é muito simples, usamos a biblioteca padrão AnyIterator para evitar a necessidade de implementar um tipo de iterador personalizado. Para cenários mais complexos, ele pode ser implementado adicionando uma correspondência ao IteratorProtocol .
Em seguida, vamos adicionar uma API para modificar nossa lista vinculada, começando com as inserções. Vamos estender a
List com o método
append , que adiciona um novo nó ao valor inserido e, em seguida, retorna esse nó - assim:
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 } }
Acima, usamos o atributo @discardableResult , que informa ao compilador para não gerar nenhum aviso se o resultado da chamada de nosso método não tiver sido usado, pois nem sempre estamos interessados no nó que foi criado.
Como as listas vinculadas não se baseiam em índices, mas na manutenção de uma cadeia de valores por meio de links, a implementação de exclusões é apenas uma questão de atualizar os vizinhos seguintes e anteriores dos nós remotos para que eles apontem um para o outro:
extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous
Com base no exposto, a versão inicial da nossa Lista é concluída e estamos prontos para verificá-la em ação. Vamos atualizar o Canvas para usar nossa nova lista, bem como um dicionário que nos permita encontrar rapidamente qual nó corresponde a um determinado ID de forma:
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) } }
Agora temos inserções e exclusões rápidas, e uma ordem de classificação previsível, sem a necessidade de adicionar complexidade extra ao processo de chamada - é muito legal! E, como nossa nova Lista é um tipo completamente universal, agora podemos usá-la sempre que precisarmos armazenar novamente valores sem um índice de maneira linear.
Conclusão
Apesar de as estruturas de dados serem tão fundamentais que podem ser encontradas em todos os tipos de linguagens de programação, a decisão sobre qual delas usar em cada situação específica ainda pode exigir uma quantidade significativa de pensamento, teste e experimentação, especialmente se queremos para que nosso código permaneça eficaz à medida que o conjunto de dados cresce.
Também é muito provável que a estrutura de dados apropriada para cada situação específica possa mudar ao longo do tempo à medida que nossos requisitos mudam, e às vezes o uso de uma combinação de várias estruturas de dados, e não apenas uma, pode ser uma maneira de atingir as características de desempenho necessárias.
Continuaremos a explorar o mundo das estruturas de dados nos seguintes artigos, focando naqueles que ainda não foram implementados na biblioteca padrão. Como em muitas outras coisas, às vezes precisamos expandir nosso pensamento além do Swift para escolher a estrutura de dados correta para cada situação.
Você pode me encontrar
no Twitter ou me enviar um e-mail se tiver alguma dúvida, comentário ou feedback.
Obrigado pela atenção!