Bonjour encore. Avant de partir pour le week-end, nous voulons partager avec vous une traduction de matériel qui a été préparé spécifiquement pour le cours de base «Développeur iOS» .
Décider de la structure de données à utiliser pour représenter un ensemble de valeurs donné est souvent beaucoup plus difficile qu'il n'y paraît. Étant donné que chaque type de structure de données est optimisé pour un certain nombre de cas d'utilisation, le choix du bon ajustement pour chaque ensemble de données peut souvent avoir un impact important sur les performances de notre code.
La bibliothèque Swift standard est livrée avec trois structures de données principales -
Array ,
Dictionary et
Set , chacune ayant son propre ensemble d'optimisations, avantages et inconvénients. Examinons certaines de leurs caractéristiques, ainsi que les cas où nous devrons peut-être aller au-delà de la bibliothèque standard pour trouver la bonne structure de données pour nos besoins.
Linéarité du tableau
Array est probablement l'une des structures de données les plus couramment utilisées dans Swift, et il y a de bonnes raisons à cela. Il stocke ses éléments de manière séquentielle, ils sont facilement triés de manière prévisible et toutes les valeurs peuvent y être stockées: des structures aux instances de classes et autres collections.
Par exemple, ici, nous utilisons un tableau pour stocker une collection de formes placées sur une
Canvas dans une application de dessin. Ensuite, lorsque nous devons rendre le canevas dans une image, nous
DrawingContext simplement le tableau pour dessiner chaque élément à l'aide de
DrawingContext - comme suit:
struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } }
En ce qui concerne le rendu séquentiel de toutes nos formes, comme nous l'avons fait ci-dessus, le tableau s'adapte parfaitement. Les tableaux stockent non seulement leurs éléments de manière très efficace, ils ont également un ordre de tri garanti, qui fournit un ordre de rendu prévisible sans avoir à faire de travail supplémentaire.
Cependant, comme toutes les autres structures de données, les tableaux ont leurs inconvénients. Dans notre cas, nous rencontrerons l'un de ses inconvénients lorsque nous voulons supprimer des formes du canevas. Étant donné que les éléments du tableau sont stockés par index, nous devons toujours trouver à quel index le chiffre est associé avant de pouvoir le supprimer:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } }
Au début, le code ci-dessus peut ne pas sembler si problématique, mais il peut devenir un goulot d'étranglement de performances pour tout canevas contenant un grand nombre de formes, car
firstIndex est linéaire (O (N)) en termes de
complexité temporelle .
Bien que nous puissions contourner cette limitation lorsque nous utilisons notre type de canevas. Par exemple, toujours se référer aux chiffres par index, et non par valeur ou ID - cela rendrait notre code plus complexe et plus fragile, car nous devrions toujours être sûrs que nos index n'expirent pas lorsque le canevas avec lequel nous travaillons va changer.
Ensembles de vitesse
À la place, voyons si nous pouvons optimiser le
Canvas lui-même en modifiant sa structure de données sous-jacente. Compte tenu du problème ci-dessus, l'une de nos premières idées pourrait être d'utiliser
Set (sets) au lieu de
Array . Comme nous l'avons déjà expliqué dans
La puissance des ensembles dans Swift , l'un des avantages importants des ensembles par rapport aux tableaux est que l'insertion et la suppression peuvent toujours être effectuées dans un temps constant (O (1)), puisque les éléments sont stockés par valeur de hachage, pas par index.
En mettant à jour
Canvas pour utiliser des ensembles, nous obtenons ce qui suit:
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) } }
Encore une fois, le code ci-dessus peut sembler correct et il se compile même sans problème. Cependant, bien que nous ayons résolu le problème de suppression, nous avons également perdu notre ordre de rendu stable - car, contrairement aux tableaux, les ensembles ne nous donnent pas un ordre de tri garanti - ce qui est une pierre d'achoppement dans cette situation, car il semble que nous allons dessiner des formes personnalisées dans au hasard.
Indexation des index
Continuons d'expérimenter. Voyons maintenant si nous pouvons optimiser le
Canvas en introduisant un
Dictionary , ce qui nous permet de rechercher l'index de n'importe quelle forme en fonction de son ID. Nous allons commencer par changer le niveau d'accès de notre tableau de
shapes en
private afin de pouvoir contrôler l'insertion des éléments à l'aide de la nouvelle méthode
add . Et chaque fois qu'une nouvelle figure est ajoutée, nous ajoutons également son index à notre dictionnaire:
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) } }
Puisque maintenant nous savons toujours à quel index une figure donnée est stockée, nous pouvons rapidement effectuer la suppression en temps constant, comme lors de l'utilisation d'un ensemble:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } }
Cependant, il y a un bug assez sérieux dans notre nouvelle implémentation de
Canvas . Chaque fois que nous supprimons une forme, nous invalidons en fait tous les index qui sont supérieurs à celui que nous venons de supprimer - puisque chacun de ces éléments se déplacera d'une étape au début du tableau. Nous pourrions résoudre ce problème en ajustant ces indices après chaque suppression, mais cela nous ramènerait à nouveau sur le territoire O (N), ce que nous avons essayé d'éviter dès le début.
Notre dernière mise en œuvre a ses mérites. En général, l'utilisation d'une combinaison de deux structures de données peut être une excellente idée dans de telles situations, car nous pouvons souvent utiliser les forces d'une structure de données pour compenser les lacunes de l'autre, et vice versa.
Réessayons donc avec une combinaison différente, mais cette fois commençons par considérer nos
besoins réels :
- Nous avons besoin d'insertions et de suppressions pour avoir une complexité temporelle constante, et il devrait être possible de supprimer la figure sans connaître son index de base.
- Nous avons besoin d'un ordre de tri garanti afin de pouvoir maintenir un ordre de rendu stable.
En regardant les exigences ci-dessus, il s'avère que bien que nous ayons besoin d'un ordre de tri stable, nous n'avons en fait pas besoin d'index. Cela rendrait la liste chaînée parfaite pour notre cas d'utilisation.
Les listes liées sont constituées de nœuds, où chaque nœud contient un lien (ou lien) vers le nœud suivant dans la liste, ce qui signifie qu'il peut être trié de manière prévisible - sans avoir besoin de mises à jour d'index lorsqu'un élément est supprimé. Cependant, la bibliothèque standard Swift (jusqu'à présent) ne contient pas de type de liste liée, donc si nous voulons l'utiliser, nous devons d'abord le créer.
Créer une liste chaînée
Commençons par déclarer une structure
List qui suivra les premier et dernier nœuds de notre liste. Nous allons rendre ces deux propriétés en lecture seule en dehors de notre type pour assurer la cohérence des données:
struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? }
Ensuite, créons notre type de nœud (nœud), que nous allons créer une classe, car nous voulons pouvoir faire référence aux nœuds
par référence, et non par valeur . Notre liste sera doublement connectée, ce qui signifie que chaque nœud contiendra un lien vers son prochain voisin et le précédent. Chaque nœud stockera également une valeur - comme ceci:
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 raison pour laquelle nous rendons la propriété précédente faible est d'éviter les boucles de rétention qui apparaîtraient si nous conservions des liens solides dans les deux sens. Pour en savoir plus sur la façon d'éviter les cycles de conservation, consultez l'article «Gestion de la mémoire» .
C'est en fait tout le code dont nous avons besoin pour que les valeurs puissent être stockées dans notre liste chaînée. Mais ce n'est que la première partie du puzzle, comme dans toute autre collection, nous voulons également pouvoir le parcourir et changer son contenu. Commençons par les itérations qui, grâce à la conception Swift très orientée protocole, peuvent être facilement implémentées en garantissant la conformité au protocole
Sequence et en implémentant la méthode
makeIterator :
extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator {
Étant donné que l'itération ci-dessus est très simple, nous utilisons la bibliothèque standard AnyIterator pour éviter d'avoir à implémenter un type d'itérateur personnalisé. Pour les scénarios plus complexes, il peut être implémenté en ajoutant une correspondance à IteratorProtocol .
Ensuite, ajoutons une API pour modifier notre liste de liens, en commençant par les insertions. Nous allons étendre la
List avec la méthode
append , qui ajoute un nouveau nœud pour la valeur insérée, puis retourne ce nœud - comme ceci:
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 } }
Ci-dessus, nous utilisons l'attribut @discardableResult , qui indique au compilateur de ne générer aucun avertissement si le résultat de l'appel de notre méthode n'a pas été utilisé, car nous ne sommes pas toujours intéressés par le nœud qui a été créé.
Étant donné que les listes liées ne sont pas basées sur des index, mais sur le maintien d'une chaîne de valeurs via des liens, l'implémentation des suppressions consiste simplement à mettre à jour les voisins suivants et précédents des nœuds distants afin qu'ils se pointent à la place:
extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous
Sur la base de ce qui précède, la version initiale de notre liste est terminée et nous sommes prêts à la vérifier en action. Mettons à jour le canevas pour utiliser notre nouvelle liste, ainsi qu'un dictionnaire qui nous permet de trouver rapidement quel nœud correspond à un ID de forme donné:
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) } }
Maintenant, nous avons à la fois des insertions et des suppressions rapides, et un ordre de tri prévisible, sans avoir besoin d'ajouter une complexité supplémentaire au processus d'appel - c'est plutôt cool! Et, puisque notre nouvelle liste est un type complètement universel, nous pouvons maintenant l'utiliser chaque fois que nous devons à nouveau stocker des valeurs sans index de manière linéaire.
Conclusion
Malgré le fait que les structures de données sont si fondamentales qu'elles peuvent être trouvées dans toutes sortes de langages de programmation, la décision quant à celui à utiliser dans chaque situation spécifique peut encore nécessiter une quantité importante de réflexion, de test et d'expérimentation, surtout si nous voulons afin que notre code reste efficace à mesure que l'ensemble de données se développe.
Il est également très probable que la structure de données appropriée pour chaque situation spécifique puisse changer au fil du temps à mesure que nos besoins changent, et parfois utiliser une combinaison de plusieurs structures de données, et pas seulement une, peut être un moyen d'atteindre les caractéristiques de performance requises.
Nous continuerons d'explorer le monde des structures de données dans les articles suivants, en nous concentrant sur celles qui ne sont pas encore implémentées dans la bibliothèque standard. Comme pour tant d'autres choses, nous devons parfois élargir notre réflexion au-delà de Swift pour choisir la bonne structure de données pour chaque situation.
Vous pouvez me trouver
sur Twitter ou m'envoyer un courriel si vous avez des questions, des commentaires ou des commentaires.
Merci de votre attention!