Comment la DICE est-elle implémentée exactement qu'elle a une recherche de temps linéaire pour les collisions? Je suppose que cela est mis en œuvre comme une haquetable soutenue par une liste. Je présumerais qu'une meilleure implémentation serait O (log (n)) pour diverses opérations, à l'aide d'un arbre pour soutenir la table. Y a-t-il une magie de la magie dans les coulisses pour garder les recherches de temps constantes vivantes aussi longtemps que possible?
Ma source pour cela, au fait, est-ce:
http://www.google.com/search? SecteurId = chrome & IE = UTF-8 & Q = Python + Complexité
5 Réponses :
dict est O (1) pour la plupart des opérations, à l'exception des opérations qui touchent tous les éléments, tels que l'itération et la copie (auquel cas, c'est évidemment O (n)).
Voir: http://wiki.python.org/moin/timecomplexity
Il a le pire des cas O (n), car vous pouvez toujours concevoir un exemple pathologique dans lequel toutes les touches ont la même valeur de hachage.
Bonne réponse. Il est important de garder à l'esprit que Big-o est une limite limitée supérieure - même si performances amorties est significativement meilleure. Malheureusement, la performance amortise est souvent prise comme la complexité.
considère même la meilleure fonction de hachage dans la galaxie. Il y a toujours une chance que vous puissiez marcher un jour avec une liste de valeurs dont la meilleure valeur de la fonction de hachage se trouve être toutes identiques. Si vous mettez ceux d'une dicte, le système n'a pas d'autre choix que d'effectuer des recherches linéaires.
L'utilisation d'un arbre équilibré garderait le plus grand temps à O (log n), mais les coûts de maintenance sont assez élevés. Habituellement, les tables de hachage sont très bien performantes.
Je présumerais qu'une meilleure implémentation serait O (log (n)) pour diverses opérations, à l'aide d'un arbre pour soutenir la table.
Les arbres et les tables de hachage ont des exigences très différentes et des caractéristiques de performance.
- Les arbres nécessitent un type commandé.
- Les arbres nécessitent des comparaisons d'ordre pour trouver l'objet. Pour certains objets, comme des chaînes, cela empêche certaines optimisations significatives: vous devez toujours effectuer une comparaison de chaîne, ce qui est non plus coûteux. Cela rend le facteur constant de O (log n) assez élevé.
- Tables de hachage nécessitent un type hachable et que vous pouvez tester pour l'égalité, mais ils ne nécessitent pas de type commandé.
- Les tests d'égalité peuvent être optimisés de manière significative. Si deux chaînes sont internées, vous pouvez tester s'ils sont égaux à O (1) en comparant leur pointeur, plutôt que O (n) en comparant toute la chaîne. Ceci est un optimisation massive : dans chaque
foo.bar de la recherche qui se traduit parfoo .__ dict __ ["bar"] ," bar " est une chaîne interne.- Les tables de hachage sont O (n) dans le pire des cas, mais examinent ce qui conduit à ce pire des cas: une très mauvaise implémentation de la table de hachage (par exemple, vous n'avez qu'un godet) ou une fonction de hachage brisée qui retourne toujours le même valeur. Lorsque vous avez une fonction de hachage appropriée et un algorithme de seau approprié, les recherches sont très bon marché - très souvent approchent de temps constant.
Les arbres ont des avantages significatifs:
- Ils ont tendance à avoir des exigences de mémoire inférieures, car elles n'ont pas à prélever des godets. Le plus petit arbre peut être de 12 octets (pointeur de nœud et deux pointeurs d'enfants), où une table de hachage a tendance à être 128 octets ou plus - Sys.getsizeof ({}) sur mon système est de 136.
- ils permettent une traversée ordonnée; Il est extrêmement utile de pouvoir parcourir [A, B) dans un ensemble commandé, quelles tables de hachage n'autorisent pas.
Je considère que je considère comme une faille que Python n'a pas de conteneur d'arbre binaire standard, mais pour les caractéristiques de performance nécessaires par le noyau Python, comme
__ dict __ , une table de hachage a plus de sens .
Le point de choisir une implémentation sur une autre n'est pas nécessairement quant à la Haute-liaison , Mais plutôt l'attente performances amorties . Alors que différents algorithmes peuvent ont des cas dégénèrent qu'il est généralement "mieux en pratique" que d'utiliser une approche avec une limite supérieure inférieure prouveuse. Dans certains cas, toutefois, les structures doivent être conçues pour se protéger contre les entrées pathologiquement mauvaises.
En outre, certaines langues / bibliothèques - pas sûr de Python - modifier en réalité la mise en œuvre sous-jacente, telle que lorsque le nombre d'éléments dépasse un faible n. Cela affecte les performances amortizées (dans certains cas), mais pas nécessairement le Big O .
et en conclusion: "Cela dépend".
codage heureux.
Sources d'informations fiables sur les fonctions de hachage et la stratégie de résolution de collision réellement utilisée incluent les commentaires du fichier source dictobject.c et l'ensemble du fichier dicnotes.txt
La complexité pire des cas n'est pas le seul facteur d'optimisation.
"Je présumerais qu'une meilleure implémentation serait O (log (n)) pour diverses opérations", pourquoi? Avez-vous vu des points de repère à ce sujet? Ma compréhension est "aléatoire" sondage est en fait la plus rapide en moyenne et conduit à O (n) comme un pire des cas. Que supposez-vous et quelles mesures avez-vous vues?
Je pense que Python dict utilise des touches 32 bits, ce qui signifie que vous avez besoin de 2 ** 31 31 ou près de 620000000000000 clés avant que vous vous attendiez une seule collision (à l'exclusion des objets dont la mise en œuvre de
__ hachage __ est vraiment mauvais, mais je préférerais voir cela comme un bug). Les collisions n'ont donc vraiment aucune incidence quotidienne et le temps consacré à l'optimisation d'eux est gaspillé.@Jochen, je pense que vous avez des attentes irréalistes d'une fonction de hachage. Celui qui vous donne une collision avant d'épuiser les godets est pas vraiment mauvais, c'est en fait assez courant. Voyez combien de personnes avec lesquelles vous pouvez passer avant d'avoir un affrontement d'anniversaire, il sera certainement pas 365. Vous pouvez avoir des fonctions de hachage parfait, mais seulement si vous comprenez les données en avance. Compte tenu d'une fonction de hachage à usage général, vous pouvez créer une collision avec seulement deux entrées si vous connaissez l'algorithme.
@Jochen: Bien sûr, ils ont des collisions; Une table de hachage n'a généralement pas 2 ^ 32 seaux. (En outre, 2 ^ 31 est juste 2147483648, pas 620000000000000 - et vous oubliez entièrement le problème d'anniversaire.)