Efficacité des collections
Flo
Membre
Bonjour à tous,
J'aurais juste voulu savoir si Apple donnait certaines précisions quand à l'efficacité des méthode de recherche, tri, etc... des collections en standard sous cocoa (NSMutableArray, NSMutableDictionary, NSMutableSet etc...).
Genre la complexité de ces fonctions ou encore d'éventuel condition de tri (genre les clés d'un NSDictionary, ou une eventuelle optimisation pour comparer les références dans un NSArray etc...). Ou alors est-ce mieux d'implémenter sois-même certain algo (genre recherche dichotomique, ou tri par tas, fusion etc...) pour plus d'efficacité ?
Merci pour vos réponses !
J'aurais juste voulu savoir si Apple donnait certaines précisions quand à l'efficacité des méthode de recherche, tri, etc... des collections en standard sous cocoa (NSMutableArray, NSMutableDictionary, NSMutableSet etc...).
Genre la complexité de ces fonctions ou encore d'éventuel condition de tri (genre les clés d'un NSDictionary, ou une eventuelle optimisation pour comparer les références dans un NSArray etc...). Ou alors est-ce mieux d'implémenter sois-même certain algo (genre recherche dichotomique, ou tri par tas, fusion etc...) pour plus d'efficacité ?
Merci pour vos réponses !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Un peu de lecture donc qui devrait répondre à ton interrogation
PS (désolé pour le temps à répondre... problème de connexion internet)
- un NSMutableDictionary ?
- un NSMutableArray avec une méthode perso d'insertion/recherche/suppression dichotomique en O(log n) ?
Perso pour l'instant j'ai opté pour la deuxième solution ne connaissant pas l'efficacité des méthodes de la classe NSDictionary.
Justement, si je souhaite conserver l'ordre alphabétique tout en utilisant un NSDictionary, ça m'oblige à passer par un sortDescriptor sur le tableau des clé ce qui ne doit pas être super efficace non ?
Au contraire, c'est très efficace
Rien que pour une NSArray avec 30 000 dictionnaires, la clé "Name" a été triée en largement moins d'une seconde :
Par contre pour 3 millions de dictionnaires... ça prend 6 secondes quand meme, et surtout ça sert à rien
Pour 300 000 ça prend presque 1 seconde..
bref, c'est des trucs à tester soi-même quoi.. Mais pourquoi se servir d'autre chose alors que ce que propose Apple semble assez rapide
Je vois donc quand même un avantages à la solution 2 que j'avais proposé, les éléments sont toujours triés (pas besoin de faire une copie et de re-demander le tri à chaque fois)... non ?
Je comprend pas trop pourquoi tu as besoin de re-trier à chaque fois ? À quel moment exactement tu demandes le tri ? Pourquoi ne pas trier tout dès le départ ?
Les clés et les objets seront stockés dans un ordre déterminé par l'implémentation de la classe NSMutableDictionary. Maintenant imaginons, j'ai la méthode delegate :
Il faudrait relancer le tri de tout le dico à chaque ajout ?
Il faurait concerver une copie des clés triées par ordre alphabétique ?
Mhh, hachage, oui... mais à mon avis sur l'adresse et pas sur la chaà®ne. Sinon ça ne prendrait pas un "id" pour clé.
Donc chaà®ne ou autre pour les clés, peu importe je dirais.
Un NSDictionary n'est PAS trié. Les objets qu'il contient sont indexés par les clés, leur ordre n'importe pas (y compris pour le temps d'accès puisque c'est implémenté sous forme de table de hachage donc c'est un accès en O(1), à temps constant).
Ainsi les 2 dictionnaires suivants sont strictement équivalents, y compris en terme de rapidité d'accès des valeurs quand tu veux les récupérer : Un dictionnaire n'a pas d'ordre, (de même qu'un NSSet d'ailleurs).
OUI justement ! (je me suis mal exprimé, je voulais dire d'une manière et pas d'un ordre, en effet ça prêtait à confusion :P).
L'utilisation d'un NSDictionary oblige DONC de conserver une représentation triée lorsque l'on souhaite obtenir l'ordre alphabétique dans les méthodes du DataSource Protocol (on ne va pas redemander le trie des clé à chaque appel de outlineView:child:ofItem: quand même non ?!).
Cette contrainte me paraà®t désavantageuse par rapport à la solution que j'avais proposé (NSMutableArray + insertion dichotomique) qui ne nécessite pas de stocker une représentation triée à part ET qui n'oblige pas à relancer le trie sur toute la collection après insertion d'un nouvel objet.
C'était un peu ça le sens de ma question
Visiblement je dois pas m'exprimer de manière super clair... dsl ::)
J'ai pensé utiliser la méthode setSortDescriptor: de NSTableView (qui revient à déléguer le travail du tri alphabétique à la tableView en quelque sorte) ... dans ce cas il ne suffit plus que de trouver comment renvoyer l'item d'indice i en évitant la méthode allKeys: ou allValues:...
Le model pour des NSOutlineView c'est une arborescence. Chaque noe“ud possède une NSMutableArray de fils. C'est chercher les ennuis que de mettre un NSMutableDictionary, ou même un NSSet pour le champ children dans un arbre, cela empêche la réorganisation des éléments par drag.
En fait ma question est toujours valable mais j'aurai du la poser pour la méthode délégate tableView:objectValueForTableColumn:row:.
En fait il me faut un moyen d'afficher le contenu d'un NSDictionary dans une NSTableView via les méthodes delegate et sans passer par une copie mémoire.
Donc sans équivoque, il passe par une NSArray (que l'on peut trier) où chaque ligne est un NSDictionary dont les clés sont les identifier des colonnes.
Donc si je comprends bien, pas moyen de gérer une arborescence où les noeuds offrent l'efficacité d'un NSDictionary lors d'un recherche à partir d'une clé ?
Dans ce cas, ne vaut-il pas mieux implémenter sa propre méthode de recherche (dichotomique par exemple) que celle proposé par NSArray qui est en O(n log n) ?
Euh non c'est pas si simple, c'est pas classé par adresse, c'est classé grâce au hash des objets. Après tout la méthode -hash est définie dans le protocol NSObject ce qui la rend utilisable par tous les objets...
Mais en plus, il faut savoir que les clés sont copiés, donc si on veut être suffisamment précis, la méthode setObject:forKey: de NSMutableDictionary devrait être
Cependant, garder le typage dynamique total permet d'éviter d'avoir des warnings inutiles.
Comment fait-il pour connaà®tre un hash sur un objet perso si on ne l'a pas implémenté, même si celui-ci est <NSCoding> compliant ?
Je suppose que la méthode "hash" par défaut est basée sur l'adresse... Je ne vois pas sur quoi d'autre elle pourrait être basée.
Pour les NSString, c'est effectivement un peu plus compliqué, parce que un NSString doit avoir le même hash qu'un NSMutableString équivalent, donc ça ne peut être basé sur l'adresse.
C'est donc quand même particulièrement inadapté comme système. Surtout si les clés sont longues... Un hash sur un uint_32 / uint_64 c'est carrément plus rapide qu'un hash sur une chaà®ne (il suffit de prendre le uint_32 lui même en x86 et les 32 bits de poids faible du uint_64 en x64, puisque "hash" renvoie un NSUInteger, qui est toujours sur 32 bits).
Du coup, avec des clé NSString c'est sans doute justement moins optimisé.
Euh... J'espère quand même que tu as des notions d'héritage... La méthode -hash est définie dans le protocol NSObject...
De plus, dans le cas des NSString, qui sont non-modifiable, rien ne t'empêche de cacher la valeur du hash que tu as calculé la première fois.
Returns an integer that can be used as a table address in a hash table structure.
- Comment définiriez-vous ce hash ?
- Il y a codage des objets par un NSUInteger traduisant une position dans une arborescence plutôt que par un simple rang dans une liste ?
- Si chaque objet possède un hash, à quoi correspond-il si cet objet n'est pas dans une collection ?
Le deuxième c'est juste pour pouvoir mettre l'objet dans une collection de type hash table, comme c'est dit dans la doc.
Une hash table, fonctionne comme un simple tableau, cependant certaines cases peuvent être vides, et certaines cases peuvent avoir plusieurs valeurs, ce dernier point est résolu par des listes chaà®nées (une hash table est en général un tableau de listes chaà®nées), et ce dernier point est aussi dû au fait qu'il peut y avoir des collisions, c'est-à -dire deux objets différents donnent le même hash.
Dans le cas de -hash, chez Apple, les conditions sont assez simples, si deux objets sont égaux selon la méthode -isEqual: alors leurs -hash respectifs sont égaux. Donc quand tu as une hash table, tu vas d'abord récupérer l'index dans ton tableau via la méthode -hash, puis tu vas suivre la liste chaà®née correspondante jusqu'à trouver un objet qui, passé en paramètre du message -isEqual: envoyé à l'objet que tu recherches, indiquera si l'objet est égal à l'objet recherché.
Pour info, toutes les collections de Cocoa sont basés sur une table de hash, même NSArray.
Et petites anecdotes, le -hash de NSObject c'est l'adresse de l'objet et le -hash d'un NSArray c'est son nombre d'éléments. Pareil pour NSDictionary et NSSet.
En tout cas pour compléter ce que dit psychoh13, le hash est unique dans le sens où un objet avec une valeur donnée retourne toujours le même hash pour la même valeur. Par contre, si 2 objets retournants des hash différents sont forcément des objets différents (au sens de "isEqual:"), 2 objets différents peuvent éventuellement retourner le même hash. En fait 2 objets retournant le même hash ont juste une assez forte probabilité d'être égaux, c'est tout (cette "assez forte" probabilité dépendant du hash choisi), donc ça permet de réduire les champs de recherche et d'accélérer l'accès à un objet dans une table de hashage justement, en ne parcourant que les objets ayant le même hash pour trouver celui qui nous intéresse.
Cette méthode de hashage est aussi parfois utilisée dans certains algorithme pour des recherches genre d'une sous-chaà®ne dans une chaà®ne de caractères, et si le hash est bien choisi, ça peut drastiquement améliorer les perfs !
J'ai l'impression que tu ne lis pas (ou mal ?) ce que je dis... Tout mon post était basé sur la méthode "hash" de NSObjet et l'adresse mémoire ???
La question était ironique pour montrer que le "hash" par défaut était basé sur l'adresse de l'objet, chose que tu avais déjà mal comprise la première fois que je l'ai dite... ::)
Mettre en cache, c'est bien beau, mais pour les constantes, tu mets en cache aussi ? le hash de chaque chaà®ne que tu trouves ? Parce-que quand on appelle un "objectForKey", on utilise les constantes très souvent hein...
D'ailleurs, je tique là dessus... D'une part parce que c'est en partie ce que j'ai dit dans le post fustigé, et d'autre part parce que j'avais posé une réflexion sur 32/64 bits.
En compilation 64 bits, les pointeurs sont sur 64 bits il me semble, et "hash" renvoie un NSUInteger qui a été conçu pour rester sur 32 bits en compilation 64 (je me trompe ?).
Donc j'émets un doute sur ton anecdote en compilation 64 bits...
32 bits faibles de l'adresse ?
En réalité, en 32 bits il est défini comme ça:
typedef unsigned int NSUInteger;
Ce qui fait, sur les processeurs Intel et PPC utilisés par Apple, un NSUInteger de 32 bits.
En 64 bits il est défini comme ça:
typedef unsigned long NSUInteger;
Ce qui fait, toujours sur les mêmes processeurs, un NSUInteger de 64 bits.
Et il y a une troisième possibilité, quand tu utilises le #define NS_BUILD_32_LIKE_64, là , de la même manière, NSUInteger sera défini comme un unsigned long, mais comme l'architecture sera sur 32 bits, NSUInteger sera lui aussi sous 32 bits, car "unsigned long" ne fait que 32 bits, pour avoir des 64 bits en mode 32, il faut utiliser le type "unsigned long long" du C99.
Donc le problème se posait quand "hash" renvoyait un "int"... En 64 bits, ça ne pouvait être l'adresse.
Enfin... les choix technologiques...