[Swift, Avancé] Comment contrôler le passage par valeur d'une Struct
Pyroh
Membre
Bonjour à tous,
Pour mes besoins j'ai codé une linked list en Swift, elle est conforme CollectionType et fonctionne plutôt pas mal vu que j'économise près de 30~40% de temps processeur si je l'utilise comme une stack au lieu d'utiliser un Array à la place. (L'économie se situe au niveau des operations de stack, bien entendu).
Je compte open-sourcer le code mais j'ai encore besoin de tester pas mal et de finir l'implémentation. Et ça coince un peu.
Pour la liste j'ai quelque chose comme ça :
public struct LinkedList<T> {
private let id: NSTimeInterval
private var head: ListNode<T>?
private var tail: ListNode<T>?
{ quelques centaines de ligne... }
}
L'ID est encore assez faible, j'en conviens, mais c'est de l'alpha.
Voilà le code de l'index:
public struct LinkedListIndex<T>: ForwardIndexType {
private let id: NSTimeInterval
private weak var node: ListNode<T>?
private init(node: ListNode<T>?, id: NSTimeInterval) {
self.node = node
self.id = id
}
public func successor() -> LinkedListIndex<T> {
precondition(node != nil, "This index has no successor")
return LinkedListIndex<T>(node: node?.next, id: id)
}
}
Je dois garder un ID pour la simple et bonne raison qu'un index issu d'une liste l1 n'est, par design, pas compatible avec une liste l2. Je n'ai pas trouvé de solution autre, du moins aucune qui me ne m'explosait pas les perfs...
Tout le problème est là , si je copie une LinkedList la copie va avoir exactement les mêmes caractéristiques donc le meme ID et surtout les mêmes pointeurs vers les mêmes objets. Dans le comportement c'est identique à une référence.
Comment je pourrai faire pour qu'à chaque copie ou passage par valeur l'ID soit changé et les elements copiés ? J'ai cherché par mal mais là j'arrive à une limite (la mienne, certainement, ou celle du langage, tristement...).
J'ai pensé que ce code serait appelé automatiquement mais non :
public init<T>(list: LinkedList<T>) {
self.init()
// Code de copie
}
Si quelqu'un a une idée, un début d'idée ou une piste je l'en remercierai éternellement.
Réponses
Alors je vais poser une question :
En quoi une liste L1 est-elle différente d'une liste L2 qui n'est rien d'autre que la première passée par valeur dans un appel de fonction, en terme de contenu ?
La réponse est : Il n'y a aucune différence tant que L2 n'est pas modifiée à l'intérieur de la fonction.
Conclusion : Il est inutile (et couteux, car il faut copier tous les noeuds) de vouloir différencier les 2 listes tant qu'elle sont fonctionnellement identiques.
La bonne façon de faire : N'effectuer la copie des noeuds (et le changement d'ID, bien que je trouve cette solution dangereuse et que je ne vois pas le besoin dans l'exemple que tu donnes) que lors de la première modification, et seulement si les références (head & tail) sont partagées. Ca s'appelle "copy on write". En pratique les Arrays & Dictionnaires Swift fonctionnent sur ce principe (et c'est pourquoi ça ne coute rien de les passer par valeur, tant qu'on ne les modifie pas, évidemment).
La solution : Apple a bien voulu mettre à notre disposition l'API isUniquelyReferenced qui permet d'implémenter le copy on write. A ce sujet , mike ash a comme toujours un excellent article à ce sujet sur son blog (où il réimplémente les arrays swift) : https://www.mikeash.com/pyblog/friday-qa-2015-04-17-lets-build-swiftarray.html
Merci beaucoup !
C'est exactement ce que je cherchais, c'est une mine d'infos ce blog !
Comme je suis pas pro je me permet de fonctionner en vase clos et trouver des infos quasiment qu'en lisant doc et header et en faisant un peu de rétro-ingénierie. Pas l'idéal, je sais, mais étend étudiant ça m'en apprend beaucoup !
Pour ce qui est de l'index, si tu regarde le code tu vois que je fais reference au noeud et que je ne me sers quasi que de ça. Je ne voyais pas trop comment faire d'autre... D'autant que dans l'absolu un index à lui seul pourrait donner la valeur par le biais de :
Je ne sais vraiment pas si c'est la bonne chose à faire mais je ne voyais pas d'autre moyens de le faire ou alors ils impliquaient l'utilisation d'un tableau d'index et je perdais tout ce que j'avais gagné niveau perfs...
Quoi qu'il en soit tu m'as vraiment bien aidé, merci !
Ceci dit en passant, avec Swift 2 il y a d'autres astuces pour implémenter une liste chaà®née, genre avec les nouveaux "indirect enums" de Swift 2 : http://airspeedvelocity.net/2015/07/26/linked-lists-enums-value-types-and-identity/(bon ok dans cet exemple elle est simplement-chaà®née, mais la lecture est intéressante quand même, notamment sur les impacts de Reference vs Value type, sur l'espace mémoire pris par les slices de ta liste chaà®née si tu ne conserves que l'implémentation par défaut de CollectionType, etc)
Concernant Swift avancé, comme Ali je recommande tout particulièrement http://airspeedvelocity.net/