Le temps de la complexité de l'accès à un Python dict

Voir Le Temps De La Complexité. Le python dict est une table de hachage, son pire des cas est donc O(n) si la fonction de hachage est mauvais et les résultats dans un grand nombre de collisions. Cependant c'est un cas très rare où chaque élément ajouté est le même hachage et est donc ajouté à la même chaîne qui, pour un grand Python la mise en œuvre serait extrêmement peu probable. La durée moyenne de la complexité est bien sûr O(1).

La meilleure méthode serait de vérifier et de prendre un regard sur les hashs des objets que vous utilisez. Le Disponible Dict utilise int PyObject_Hash (PyObject *o) qui est l'équivalent de hash(o).

Après une vérification rapide, je n'ai pas encore réussi à trouver deux tuples de hachage à la même valeur, ce qui pourrait indiquer que la recherche est O(1)

l = []
for x in range(0, 50):
    for y in range(0, 50):
        if hash((x,y)) in l:
            print "Fail: ", (x,y)
        l.append(hash((x,y)))
print "Test Finished"

CodePad (Disponible pour 24 heures)

Il serait plus facile de faire des suggestions si vous avez fourni un exemple de code et de données.

Accès au dictionnaire est peu probable d'être un problème tant que l'opération est O(1) en moyenne, et O(N) amorti pire des cas. Il est possible que le construit-dans les fonctions de hachage rencontrez des collisions pour vos données. Si vous rencontrez des problèmes avec la a la fonction de hachage, vous pouvez fournir votre propre.

Python le dictionnaire de la mise en œuvre
réduit la complexité moyenne de
dictionnaire des recherches à O(1) par
en exigeant que les principaux objets de fournir un
"hachage" de la fonction. Exemple d'une fonction de hachage
prend les informations dans un objet clé
et les utilise pour produire un nombre entier,
appelé une valeur de hachage. Cette valeur de hachage
est ensuite utilisé pour déterminer qui
"seau" ce (clé, valeur) la paire devrait
être placé dans.

Vous pouvez remplacer le __hash__ méthode dans votre classe pour mettre en œuvre une coutume fonction de hachage comme ceci:

def __hash__(self):    
    return hash(str(self))

En fonction de votre apparence, vous pourriez être en mesure de venir avec un plus rapide fonction de hachage qui a moins de collisions que la fonction standard. Il est toutefois peu probable. Voir la Python page Wiki sur les Clés de Dictionnaire pour plus d'informations.

Pour répondre à vos questions:

T1: """Suis-je correct que python dicts souffrent de linéaire temps d'accès à de telles données?"""

A1: Si vous voulez dire que la moyenne de recherche en temps est O(N) où N est le nombre d'entrées dans le dict, il est très probable que vous avez tort. Si vous avez raison, la communauté Python voudrais bien savoir dans quelles circonstances vous sont correctes, de sorte que le problème peut être atténué ou au moins averti. Ni "exemple de code", ni "simplifiée" code sont utiles. Veuillez montrer le code et les données permettant de reproduire le problème. Le code doit être instrumentée avec des choses comme le nombre de dict éléments et le nombre de dict accès pour chaque P, où P est le nombre de points à la clé (2 <= P <= 5)

T2: """autant Que je sache, les jeux ont garanti logarithmique temps d'accès.
Comment puis-je simuler des dicts à l'aide des ensembles(ou quelque chose de similaire) en Python?"""

A2: les Jeux ont garanti logarithmique temps d'accès dans quel contexte? Il n'y a aucune garantie pour les implémentations de Python. Récente Disponible versions en fait, l'utilisation d'un coupe-bas dict mise en œuvre (touches, pas de valeurs), de sorte que l'attente est en moyenne de O(1) comportement. Comment pouvez-vous simuler dicts avec des décors ou quelque chose de similaire dans n'importe quelle langue? Réponse courte: avec une extrême difficulté, si vous voulez une fonctionnalité au-delà de dict.has_key(key).