Transformer une collection à moindre coût
laurris
Membre
Voici un petit problème d'Arrays spécial matheux.
Soit une collection1 d'une part et une collection2 d'autre part contenant un nombre indéterminé d'objets. Sachant qu'un objet peut se trouver dans les deux collections, le problème est: comment faire pour transformer collection1 en collection2 avec le minimum d'opérations d'insertion, de suppression ou de réagencement.
Voilà . Il y a des moyens "à la bourrin" de faire ça (ex: tout effacer puis tout insérer) que j'ai réussi à mettre en oeuvre sans difficultés
Mais comme il s'agit là d'un problème mathématique plus général, il existe certainement une solution élégante et efficace. Dans quelle direction chercher ? Y a-t'il un terme d'algèbre pour décrire cette manipulation ?
Merci d'avance.
Soit une collection1 d'une part et une collection2 d'autre part contenant un nombre indéterminé d'objets. Sachant qu'un objet peut se trouver dans les deux collections, le problème est: comment faire pour transformer collection1 en collection2 avec le minimum d'opérations d'insertion, de suppression ou de réagencement.
Voilà . Il y a des moyens "à la bourrin" de faire ça (ex: tout effacer puis tout insérer) que j'ai réussi à mettre en oeuvre sans difficultés
Mais comme il s'agit là d'un problème mathématique plus général, il existe certainement une solution élégante et efficace. Dans quelle direction chercher ? Y a-t'il un terme d'algèbre pour décrire cette manipulation ?
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
égalité en contenu ou égalité des objets (même adresse) ?
J'aurais un problème de ce type, j'essaierais d'utiliser NSSet (setByAddingObject, setByAddingObjectsFromArray/Set , CFBag (qui autorise les ensembles à répétition).
Si on tient à des NSArray , c'est plus facile si elle sont triées, alors on parcourt avec deux indices l'une et l'autre en remplissant une troisième NSMutableArray (les indices n'avancent pas simultanément, mais chacun leur tour, mais le temps d'exécution est linéaire)
SI ce ne sont pas des NSArray triées, le problème ne me semble pas se poser : on les ajoutent au bout.
En effet, réfléchissons un peu : (ici on se placera dans le cas le plus général possible, avec un langage de programmation abstrait - on ne triche pas en faisant appel aux classes du types NSArray ou NSSet )
Posons n1 et n2 le nombre d'objet respectif des collections 1 et 2. Supposons que l'on veuille écrire un algo efficace dans le cas général, c'est à dire sans que l'on n'ait d'information sur l'égalité, le triage,la disjonction ou l'inclusion des collection 1 et 2. On ne veut pas de doublons, donc si l'on utilise un algo "non bourrin", qui nécessite des insertions, il te faudra tester n1 éléments n2 fois dans le pire des cas (dans le cas ou les deux listes sont disjointes) pour s'assurer de ne pas ajouter plusieurs fois le même élément; sans oublier non plus les tests nécéssaires à la suppression des objets inutiles (dans le pire des cas - celui cité précedemment -, si on supprime en premier - on a d'abord n1*n2 tests puis 0 tests, la liste obtenue étant vide; si au contraire, la liste 1 est incluse dans la liste 2, on aura de nouveau n1*n2 tests mais ensuite on aura n1*n2 tests pour l'insertion ; de toutes manières on a en gros de l'ordre de n1*n2 tests à effectuer).
Ta méthode bourrin quand à elle, nécessite exactement n1 suppressions puis n2 insertions (et 0 tests), donc de l'ordre de n1+n2 opérations (oui, je sais, je dis qu'une comparaison et une insertions "coûtent" la même chose en termes d'opérations, ce qui est évidemment une approximation, mais ce qui n'est pas trop loin de la vérité en considérant par exemple une liste chaà®née ou bien une insertion dans un tableau de taille déjà fixée).
Convaincu ?
Evidemment, si tu as des infos plus précises sur tes collections (par exemple, ce que cite Philippe avec les tableaux triés) tu vas pouvoir gagner encore plus de temps. Pour les tableaux triés, tu ne devrais avoir besoin en tout que de l'ordre de n1+n2 tests mais moins d'insertions que dans la méthode "bourrin".
En éspérant avoir été utile (je suis loin d'être sûr sur ce coups là ... )
Mais, je m'intéresse surtout au nombre total d'opérations de type insert,del,move et pas (ou moins) au nombre de comparaisons sur les objets.
Dans mon cas, les objets représentent des vues. Un insert correspond à un addSubview: et un del à un removeFromSuperview. Supprimer tout puis rajouter tout n'est donc pas une option.
La priorité va donc au nombre minimum d'insert/delete puis, en second choix à la meilleure efficacité des algos destinés à trouver ces insert/delete.
Merci de vos réponses et désolé si je n'ai pas été assez clair des le début.
Parce que si oui, ça devient immédiat et très rapide