Complexité temporelle de l'accès à un dict Python
j'écris un programme Python simple.
mon programme semble souffrir d'un accès linéaire aux dictionnaires,
son exécution se développe de façon exponentielle, même si l'algorithme est quadratique.
J'utilise un dictionnaire pour mémoriser les valeurs. Ce qui semble être un goulot d'étranglement.
les valeurs que j'utilise sont des tuples de points.
Chaque point est: (x,y), 0 <= x,y < = 50
Chaque clé dans le dictionnaire est: un tuple de 2-5 points: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))
les touches sont lues plusieurs fois plus souvent qu'elles ne sont écrites.
ai-je raison que les dicts python souffrent de temps d'accès linéaire avec de telles entrées?
autant que je sache, les sets ont des temps d'accès logarithmique garantis.
Comment puis-je simuler des dicts en utilisant des sets(ou quelque chose de similaire) en Python?
modifier selon la demande, voici une version (simplifiée) de la memoization fonction:
def memoize(fun):
memoized = {}
def memo(*args):
key = args
if not key in memoized:
memoized[key] = fun(*args)
return memoized[key]
return memo
6 réponses
Voir Complexité Temporelle. Le python dict est un hashmap, son pire cas est donc O (n) si la fonction de hachage est mauvaise et entraîne beaucoup de collisions. Cependant, c'est un cas très rare où chaque élément ajouté a le même hachage et est donc ajouté à la même chaîne qui pour une implémentation Python majeure serait extrêmement peu probable. La complexité moyenne du temps est évidemment O (1).
la meilleure méthode serait de vérifier et de jeter un oeil aux hashs de les objets que vous utilisez. CPython Dictint 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 qui hachent à la même valeur, ce qui indiquerait 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 pendant 24 heures)
Vous n'avez pas raison. dict accès est peu probable que votre problème ici. Il est presque certainement O(1), sauf si vous avez une drôle d'entrées ou une très mauvaise fonction de hachage. Collez quelques exemples de code de votre application pour un meilleur diagnostic.
il serait plus facile de faire des suggestions si vous fournissiez un exemple de code et de données.
il est peu probable que L'accès au dictionnaire soit un problème puisque cette opération est O(1) en moyenne, et O (N) amorti dans le pire des cas. Il est possible que les fonctions de hachage intégrées connaissent des collisions pour vos données. Si vous avez des problèmes avec la fonction de hachage intégrée, vous pouvez fournir la vôtre.
Python le dictionnaire de la mise en œuvre réduit la complexité moyenne de dictionnaire des recherches à O(1) par exiger que les principaux objets fournissent "hachage" de la fonction. Une telle 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" cette paire (clé, valeur) devrait être placé dans.
Vous pouvez écraser la méthode__ hash _ _ dans votre classe pour implémenter une fonction de hash personnalisée comme ceci:
def __hash__(self):
return hash(str(self))
selon l'apparence de vos données, vous pourriez être en mesure de trouver une fonction de hachage plus rapide qui a moins de collisions que la fonction standard. Il est toutefois peu probable. Voir le page Wiki de Python sur les touches du dictionnaire pour plus d'informations.
comme d'autres l'ont fait remarquer, accéder aux dicts en Python est rapide. Ils constituent probablement la structure de données la mieux huilée de la Langue, Compte tenu de leur rôle central. Le problème se situe ailleurs.
combien de tuples vous rappelez? Avez-vous envisagé l'empreinte mémoire? Peut-être passez-vous tout votre temps dans l'allocateur de mémoire ou la mémoire de paging.
mon programme semble souffrir d'un accès linéaire aux dictionnaires, son exécution croît exponentiellement même si l'algorithme est quadratique.
j'utilise un dictionnaire pour memoize valeurs. Ce qui semble être un goulot d'étranglement.
C'est la preuve d'un bug dans votre memoization méthode.
pour répondre À vos questions:
Q1: "" " suis-je correct que les dicts python souffrent de temps d'accès linéaire avec de telles entrées?"""
A1: si vous voulez dire que le temps moyen de recherche est O(N) où N est le nombre d'entrées dans le dict, alors 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 le code " type "ou le code" simplifié " sont utiles. Veuillez montrer le code réel et les données qui reproduisent le problème. Le code doit être instrumenté avec des choses comme le nombre d'articles dict et le nombre d'accès dict pour chaque P où P est le nombre de points dans la clé (2 <= P <= 5)
Q2: """autant Que je sache, les jeux ont garanti logarithmique temps d'accès. Comment puis-je simuler des dicts en utilisant des sets(ou quelque chose de similaire) en Python?"""
A2: Les ensembles ont un accès logarithmique garanti fois dans quel contexte? Il n'existe aucune garantie de ce type pour les implémentations Python. Les versions récentes de CPython utilisent en fait une implémentation de dict réduite (clés seulement, aucune valeur), de sorte que l'attente est un comportement O(1) moyen. Comment Pouvez-vous simuler des dicts avec des sets 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).