Pourquoi exactement .values() et .keys() sont-ils considérés comme O(1) ?

Question

Je n'ai pas pu trouver un raisonnement assez solide pour expliquer pourquoi les fonctions du dictionnaire telles que .values() y .keys() sont considérés comme O(1) en notation grand O. (je ne sais pas si .items() est également considéré comme O(1) )

Answer 1

Je ne suis pas versé dans le python, mais j'ai trouvé ceci :

Objets de la vue du dictionnaire

Les objets renvoyés par dict.keys() , dict.values() et dict.items() sont des objets de vue. Ils fournissent une vue dynamique sur le entrées du dictionnaire, ce qui signifie que lorsque le dictionnaire change, la vue reflète ces changements.

Les vues du dictionnaire peuvent être itérées pour produire leurs données respectives, [...]

Ce qui signifie que dict.keys() et autres ne retournent pas un nouvel objet, mais juste une enveloppe fine qui peut itérer sur le dictionnaire. Donc, pour obtenir ceci voir est O(1) . L'itération sur des éléments ne l'est pas.

Answer 2

Il est probable que la référence que vous avez trouvée à .keys() y .values() (et .items() ) étant O(1) a mis l'accent sur les performances car il s'agit d'un contraste avec Python 2, où ces fonctions retournaient des listes et nécessitaient un temps O(N) pour copier les références à tous les objets pertinents hors du dictionnaire.

L'itération sur les objets de vue renvoyés par ces méthodes en Python 3 prendra toujours un temps O(N), car il n'y a aucun moyen d'éviter de visiter chaque élément, puisque c'est là tout l'intérêt de l'itération. Le site keys y items Les vues offrent des tests d'appartenance O(1) (par ex. (somekey, somevalue) in somedict.items() ), ce qui est beaucoup plus efficace que la recherche d'un élément dans une liste.

Answer 3

Cette réponse concerne uniquement Python 3.

Comme d'autres l'ont noté .values() , .items() y .keys() retourner les vues dans un dictionnaire. En fait, il ouvre une fenêtre pour voir le contenu interne. Si vous voulez l'utiliser comme un list , tuple ou un autre objet, vous devrez effectuer une itération manuelle sur celui-ci, ce qui donne un résultat de O(n) :

d = {i: i for i in range(100)} # Just creating a random dictionary
values = d.values() # This will get the view (O(1))
values = list(values) # Turn values to a list (O(n))
print(values[5]) # Print element 6 of the list.

Il n'y a pas beaucoup de documentation sur l'implémentation et donc la complexité temporelle des vues de dictionnaire (bien que j'ai fait quelques commentaires sur le code source ci-dessous). Si vous voulez la liste des éléments, des valeurs, ou des clés, alors il faudra être O(n) parce qu'il faut itérer sur tous les éléments pour obtenir la liste ; cependant, avec quelques tests, vous pouvez voir que les vues supportent certaines choses en temps O(1) comme la vérification des membres :

import timeit 

# code snippet to be executed only once 
small_dict = "test_dict_1 = {i: i for i in range(100)}"
large_dict = "test_dict_1 = {i: i for i in range(1000000)}"

# code snippet whose execution time is to be measured 
view_code = ''' 
values_view = test_dict_1.values()
5 in values_view
'''

# timeit statement 
print(timeit.timeit(setup=small_dict, stmt=view_code, number=100000)) # 0.08737383900006535
print(timeit.timeit(setup=large_dict, stmt=view_code, number=100000)) # 0.05472081500192871

Ainsi, les vues supportent certaines opérations en O(1), ce qui pose la question. Que peut faire une vue ?

Ce qui suit est spécifique à CPython :

TLDR : Une vue de dictionnaire peut supporter une logique de base qu'une vue de dictionnaire typique peut supporter. set peuvent effectuer des opérations telles que contains, or, xor, and... (et probablement plus de logique dans le futur en se basant sur les commentaires du code source).

La beauté de python est qu'il est open source. Avec un peu de motivation, vous pouvez tout simplement vous plonger dans le code source du dictionnaire .

Si vous commencez à plonger dans le code du dictionnaire, vous remarquerez que les deux keys y values des dictionnaires sont stockés ; cependant, cela n'aide pas beaucoup à expliquer le fonctionnement des vues de dictionnaire.

À partir de la ligne 3950, on trouve ce merveilleux commentaire :

/***********************************************/
/* View objects for keys(), items(), values(). */
/***********************************************/

A partir de là, vous pouvez commencer à voir que les vues sont traitées plus ou moins comme des sets et permettent plusieurs opérations sur les ensembles O(1), notamment les opérations sur les sous-ensembles et la vérification de l'appartenance.

Les opérations suivantes sont prises en charge : and, xor, or, in.

Vérification des sous-ensembles de vues :

/* Return 1 if self is a subset of other, iterating over self;
   0 if not; -1 if an error occurred. */
static int
all_contained_in(PyObject *self, PyObject *other)
...

Vue de l'intersection (ligne 4173) :

PyObject*
_PyDictView_Intersect(PyObject* self, PyObject *other)

Vue disjointe (Ligne 4252) :

static PyObject*
dictviews_isdisjoint(PyObject *self, PyObject *other)
{

Il y a beaucoup d'autres informations mais cela devrait être un bon point de départ. Si quelqu'un d'autre peut élaborer davantage, j'aimerais avoir plus d'informations sur ce sujet. N'hésitez pas à modifier ma réponse pour l'ajouter, la modifier, la supprimer ou la reformuler.