Dictionnaires - Exercices

NoteFonctionalitées avancées des dictionnaires

Les exercices ci-dessous présentent des fonctionnalités avancées des dictionnaires en Python. Afin de bien les comprendre, vous devrez concevoir et analyser les algorithmes qui se cachent derrière ces fonctionnalités en utilisant uniquement les notions fondamentales et les fonctions de base des listes et des dictionnaires vues jusqu’à présent.

1 Parcourir les clés d’un dictionnaire avec une boucle (for loop)

Python permet de parcourir les clés directement à l’aide d’une boucle \(for\), sans avoir besoin de récupérer la liste des clés du dictionnaire au préalable.

1.1 Syntaxe

# exercice: show
# default_start
# Parcourir une liste avec une boucle for
for key in dictName:
    # faire quelque chose avec item
# default_end

1.2 Exemple

# exercice: demo
# default_start
pairs = {"a": 1, "b": 2, "c": 3}
print("pairs:", pairs)
# Parcourir les clés du dictionnaire et afficher les paires clé-valeur
for key in pairs:
    value = pairs[key]
    print("key:", key, "value:", value)
# default_end

1.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(pairs, threshold):
    count = 0
    for key in pairs:
        value = pairs[key]
        if value > threshold:
            count = count + 1
    return count
# default_end
# test_start
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 3))
print("C683AKRMaR")
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 5))
print("C683AKRMaR")
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 0))
# test_end

# default_start
def mystere(pairs, threshold):      # pairs = {"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, threshold = 3
    count = 0                       # count = 0
    for key in pairs:               # key = "a"         key = "b"       key = "c"       key = "d"       key = "e"
        value = pairs[key]          # value = 1         value = 2       value = 3       value = 4       value = 5
        if value > threshold:       # 1 > 3 ? False     2 > 3 ? False   3 > 3 ? False   4 > 3 ? True    5 > 3 ? True
            count = count + 1       #                                                   count = 1       count = 2
    return count                    # return 2
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 3))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la boucle \(for\) en utilisant uniquement les fondamentaux et les fonctions de base des listes et des dictionnaires que nous avons vus jusqu’à présent.

Récrire la fonction mystere ci-dessus mais en utilisant une boucle \(while\) au lieu d’une boucle \(for\).

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def mystere(pairs, threshold):
    return None
# default_end
# test_start
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 3))
print("C683AKRMaR")
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 5))
print("C683AKRMaR")
print(mystere({"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}, 0))
# test_end
# solution_start
def mystere(pairs, threshold):
    count = 0
    keys = pairs.keys() 
    i = 0
    while i < len(keys):
        key = keys[i]
        value = pairs[key]
        if value > threshold:
            count = count + 1
        i = i + 1
    return count
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def mystere(pairs, threshold):
    count = 0                       # 1 affectation
    keys = pairs.keys()             # récupérer la liste des clés du dictionnaire -> O(n)
    i = 0                           # 1 affectation
    # Parcourir la liste des clés du dictionnaire -> O(n)
    while i < len(keys):            # 1 comparaison + 1 longueur
        key = keys[i]               # 1 accès
        value = pairs[key]          # 1 accès
        if value > threshold:       # 1 comparaison
            count = count + 1       # 1 addition + 1 affectation
        i = i + 1                   # 1 addition + 1 affectation
    return count                    # 1 retour
# n = len(pairs)
# T(n) = 1 + n + 1 + n * (2 + 1 + 1 + 1 + 2 + 2) + 1 
#      = 9n + 4
#      = O(n)
# default_end

2 Vérifier si une clé existe dans un dictionnaire (in operator)

Python permet de vérifier si une clé existe dans un dictionnaire en utilisant l’opérateur in. Cet opérateur retourne True si la clé est présente dans le dictionnaire, et False sinon.

2.1 Syntaxe

# exercice: show
# default_start
# Vérifier si un élément est présent dans une liste
isPresent = key in dictName
# default_end

2.2 Exemple

# exercice: demo
# default_start
# création d'un dictionnaire
pairs = {"a": 1, "b": 2, "c": 3}
print("pairs:", pairs)

# vérifier si la clé "a" existe dans le dictionnaire
existsA = "a" in pairs
print("existsA:", existsA)

# vérifier si la clé "d" existe dans le dictionnaire
existsD = "d" in pairs
print("existsD:", existsD)
# default_end

2.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(listOfDicts, key):
    result = True
    for pairs in listOfDicts:
        if key not in pairs:
            result = False
    return result
# default_end
# test_start
print(mystere([{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}], "a"))
print("C683AKRMaR")
print(mystere([{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}], "b"))
# test_end

# default_start
def mystere(listOfDicts, key):  # listOfDicts = [{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}], key = "a"
    result = True               # result = True
    for pairs in listOfDicts:   # pairs = {"a": 1, "b": 2}               pairs = {"b": 3, "c": 4}               pairs = {"a": 5, "c": 6}
        if key not in pairs:    # "a" not in {"a": 1, "b": 2} ? False    "a" not in {"b": 3, "c": 4} ? True     "a" not in {"a": 5, "c": 6} ? False  
            result = False      #                                        result = False                         
    return result               # return False
print(mystere([{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}], "a"))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière l’opérateur de dictionnaire in en utilisant uniquement les fondamentaux et les fonctions de base des dictionnaires que nous avons vus jusqu’à présent.

Écrire une fonction \(myIn(pairs, key)\) qui prend en entrée un dictionnaire \(pairs\) et une clé \(key\), et qui retourne True si la clé existe dans le dictionnaire, et False sinon.

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myIn(pairs, key):
    return None
# default_end
# test_start
print(myIn({"a": 1, "b": 2, "c": 3}, "b"))
print("C683AKRMaR")
print(myIn({"a": 1, "b": 2, "c": 3}, "d"))
# test_end
# solution_start
def myIn(pairs, key):
    keys = pairs.keys() 
    i = 0
    found = False
    while not found and i < len(keys):
        if keys[i] == key:
            found = True
        i = i + 1
    return found
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de l’opérateur de dictionnaire in ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def myIn(pairs, key):
    keys = pairs.keys()                 # O(n)
    i = 0                               # 1 affectation
    found = False                       # 1 affectation
    # len(keys) itérations dans le pire des cas
    while not found and i < len(keys):  # 1 comparaison + 1 comparaison + 1 longueur
        if keys[i] == key:              # 1 comparaison
            found = True                # 1 affectation
        i = i + 1                       # 1 addition + 1 affectation
    return found                        # 1 retour
# n = len(pairs)
# T(n) = n + 1 + 1 + n * (2 + 1 + 2) + 1
#      = 6n + 3
#      = O(n)
# default_end

3 Fusionner deux dictionnaires (| operator)

Python permet de fusionner deux dictionnaires en utilisant l’opérateur |. Cet opérateur retourne un nouveau dictionnaire qui contient toutes les paires clé-valeur des deux dictionnaires fusionnés. En cas de clés en commun, les valeurs du second dictionnaire écrasent celles du premier.

3.1 Syntaxe

# exercice: show
# default_start
# Fusionner deux dictionnaires
newDict = dict1 | dict2
# default_end

3.2 Exemple

# exercice: demo
# default_start
# création de deux dictionnaires
dict1 = {"a": 1, "b": 2}
dict2 = {"b": 3, "c": 4}
print("dict1:", dict1)
print("dict2:", dict2)
# étendre dict1 avec dict2
newDict = dict1 | dict2
print("newDict:", newDict)
# default_end

3.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(dicts):
    result = {}
    for d in dicts:
        result = result | d
    return result
# default_end
# test_start
print(mystere([{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}]))
print("C683AKRMaR")
print(mystere([{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}]))
# test_end

# default_start
def mystere(dicts):            # dicts = [{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}]
    result = {}                # result = {}
    for d in dicts:            # d = {"a": 1, "b": 2}               d = {"b": 3, "c": 4}                             d = {"a": 5, "c": 6}
        result = result | d    # result = {} + {"a": 1, "b": 2}     result = {"a": 1, "b": 2} + {"b": 3, "c": 4}     result = {"a": 1, "b": 3, "c": 4} + {"a": 5, "c": 6}
    return result              # return {"a": 5, "b": 3, "c": 6}
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière l’opérateur de dictionnaire | en utilisant uniquement les fondamentaux et les fonctions de base des dictionnaires que nous avons vus jusqu’à présent.

Écrire une fonction \(myOr(dict1, dict2)\) qui prend en entrée deux dictionnaires \(dict1\) et \(dict2\), et qui retourne un nouveau dictionnaire qui contient toutes les paires clé-valeur des deux dictionnaires fusionnés. En cas de clés en commun, les valeurs du second dictionnaire écrasent celles du premier.

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myOr(dict1, dict2):
    return None
# default_end
# test_start
print(myOr({"a": 1, "b": 2}, {"b": 3, "c": 4}))
print("C683AKRMaR")
print(myOr({"x": 5, "y": 6}, {"y": 7, "z": 8}))
# test_end
# solution_start
def myOr(dict1, dict2):
    result = {}
    keys1 = dict1.keys()
    keys2 = dict2.keys()
    i = 0
    while i < len(keys1):
        key = keys1[i]
        value = dict1[key]
        result[key] = value
        i = i + 1
    j = 0
    while j < len(keys2):
        key = keys2[j]
        value = dict2[key]
        result[key] = value
        j = j + 1
    return result
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de l’opérateur de dictionnaire | ?

• \(O(1)\) - Constante
• \(O(log(n + m))\) - Logarithmique
• \(O(n + m)\) - Linéaire
• \(O((n + m)log(n + m))\) - Log Linéaire
• \(O((n + m)^2)\) - Quadratique
• \(O((n + m)^3)\) - Cubique
• \(O(2^{(n + m)})\) - Exponentielle
• \(O((n + m)!)\) - Factorielle

# default_start
def myOr(dict1, dict2):
    result = {}                        # 1 affectation
    keys1 = dict1.keys()               # O(n)
    keys2 = dict2.keys()               # O(m)
    i = 0                               # 1 affectation
    while i < len(keys1):              # n itérations dans le pire des cas
        key = keys1[i]                 # 1 accès
        value = dict1[key]            # 1 accès
        result[key] = value           # 1 affectation
        i = i + 1                       # 1 addition + 1 affectation
    j = 0                               # 1 affectation
    while j < len(keys2):              # m itérations dans le pire des cas
        key = keys2[j]                 # 1 accès
        value = dict2[key]            # 1 accès
        result[key] = value           # 1 affectation
        j = j + 1                       # 1 addition + 1 affectation
    return result                      # 1 retour
# n = len(dict1), m = len(dict2)
# T(n, m) = 1 + n + m + 1 + n * (1 + 1 + 1) + 1 + m * (1 + 1 + 1) + 1
#          = 3n + 3m + 5
#          = O(n + m)
# default_end

4 Récupérer la liste des valeurs d’un dictionnaire (values() method)

Python permet de récupérer la liste des valeurs d’un dictionnaire à l’aide de la méthode values().

4.1 Syntaxe

# default_start
# Récupérer la liste des valeurs d'un dictionnaire
values = dictName.values()
# default_end

4.2 Exemple

# default_start
pairs = {"a": 1, "b": 2, "c": 3}
print("pairs:", pairs)
values= pairs.values()
print("values:", values)
# default_end

4.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(pairs1, pairs2):
    values1 = pairs1.values()
    values2 = pairs2.values()
    results = []
    for value1 in values1:
        if value1 in values2:
            results.append(value1)
    return results
# default_end
# test_start
print(mystere({"a": 1, "b": 2, "c": 3}, {"d": 2, "e": 3, "f": 4}))
print("C683AKRMaR")
print(mystere({"a": 1, "b": 2, "c": 3}, {"d": 4, "e": 5, "f": 6}))
# test_end

# default_start
def mystere(pairs1, pairs2):        # pairs1 = {"a": 1, "b": 2, "c": 3}, pairs2 = {"d": 2, "e": 3, "f": 4}
    values1 = pairs1.values()       # values1 = [1, 2, 3]
    values2 = pairs2.values()       # values2 = [2, 3, 4]
    results = []                    # results = []
    for value1 in values1:          # value1 = 1                value1 = 2              value1 = 3
        if value1 in values2:       # 1 in [2, 3, 4] ? False    2 in [2, 3, 4] ? True   3 in [2, 3, 4] ? True
            results.append(value1)  #                           results = [2]           results = [2, 3]
    return results                  # return [2, 3]
print(mystere({"a": 1, "b": 2, "c": 3}, {"d": 2, "e": 3, "f": 4}))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de dictionnaire values() en utilisant uniquement les fondamentaux et les fonctions de base des dictionnaires que nous avons vus jusqu’à présent.

Écrire une fonction myValues(pairs) qui prend en entrée un dictionnaire pairs et qui retourne la liste des valeurs du dictionnaire.

# exercice: show
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myValues(pairs):
    return None
# default_end
# test_start
print(myValues({"a": 1, "b": 2, "c": 3}))
print("C683AKRMaR")
print(myValues({"x": 10, "y": 20}))
print("C683AKRMaR")
print(myValues({}))
# test_end
# solution_start
def myValues(pairs):
    values = [0] * len(pairs)
    keys = pairs.keys()
    i = 0
    while i < len(keys):
        values[i] = pairs[keys[i]]
        i = i + 1
    return values
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de dictionnaire values() ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def myValues(pairs):
    keys = pairs.keys()                 # O(n)
    values = [0] * len(keys)            # O(n)
    i = 0                               # 1 affectation
    while i < len(keys):                # 1 comparaison + 1 longueur
        values[i] = pairs[keys[i]]      # 1 accès + 1 affectation + 1 accès + 1 accès
        i = i + 1                       # 1 addition + 1 affectation
    return values                       # 1 retour
# n = len(pairs.keys())
# T(n) = n + n + 1 + n * (2 + 4 + 2) + 1
#      = 9n + 2
#      = O(n)
# default_end

5 Récupérer la liste des paires clé-valeur d’un dictionnaire (items() method)

Python permet de récupérer la liste des paires clé-valeur d’un dictionnaire à l’aide de la méthode items(). Cette méthode retourne une liste de tuples, où chaque tuple contient une paire clé-valeur du dictionnaire. Un tuple est une structure de données immuable (c’est à dire qu’on ne peut pas la modifier après l’avoir créée). Pour créer un tuple, il suffit de mettre les éléments entre parenthèses () plutôt que des crochets [] utilisés pour les listes.

5.1 Syntaxe

# default_start
# Récupérer la liste des paires clé-valeur d'un dictionnaire
items = dictName.items()
# default_end

5.2 Exemple

# default_start
pairs = {"a": 1, "b": 2, "c": 3}
print("pairs:", pairs)
items = pairs.items()
print("items:", items)
# default_end

5.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(pairs1, pairs2):
    items1 = pairs1.items()
    items2 = pairs2.items()
    results = items1 + items2
    return results
# default_end
# test_start
print(mystere({"a": 1, "b": 2}, {"c": 3, "d": 4}))
print("C683AKRMaR")
print(mystere({"e": 5, "f": 6, "g":7}, {"h": 8}))
# test_end

# default_start
def mystere(pairs1, pairs2):      # pairs1 = {"a": 1, "b": 2}, pairs2 = {"c": 3, "d": 4}
    items1 = pairs1.items()       # items1 = [("a", 1), ("b", 2)]
    items2 = pairs2.items()       # items2 = [("c", 3), ("d", 4)]
    results = items1 + items2     # results = [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
    return results                # return [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
print(mystere({"a": 1, "b": 2}, {"c": 3, "d": 4}))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de dictionnaire items() en utilisant uniquement les fondamentaux et les fonctions de base des dictionnaires que nous avons vus jusqu’à présent.

Écrire une fonction myItems(pairs) qui prend en entrée un dictionnaire pairs et qui retourne la liste des paires clé-valeur du dictionnaire sous la forme de tuples (key, value).

Par rapport aux listes, les tuples sont des structures de données immuables (c’est à dire qu’on ne peut pas les modifier après les avoir créés). Pour créer un tuple, il suffit de mettre les éléments entre parenthèses () plutôt que des crochets [] utilisés pour les listes.

# exercice: show
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myItems(pairs):
    return None
# default_end
# test_start
print(myItems({"a": 1, "b": 2, "c": 3}))
print("C683AKRMaR")
print(myItems({"x": 10, "y": 20}))
print("C683AKRMaR")
print(myItems({}))
# test_end
# solution_start
def myItems(pairs):
    items = [0] * len(pairs)
    keys = pairs.keys()
    i = 0
    while i < len(keys):
        items[i] = (keys[i], pairs[keys[i]])
        i = i + 1
    return items
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de dictionnaire items() ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def myItems(pairs):
    keys = pairs.keys()                         # O(n)
    items = [0] * len(keys)                     # O(n)
    i = 0                                       # 1 affectation
    # len(keys) itérations
    while i < len(keys):                        # 1 comparaison + 1 longueur
        items[i] = (keys[i], pairs[keys[i]])    # 1 accès + 1 accès + 1 tuple + 1 affectation
        i = i + 1                               # 1 addition + 1 affectation
    return items                                # 1 retour
# n = len(pairs.keys())
# T(n) = n + n + 1 + n * (2 + 4 + 2) + 1
#      = 9n + 2
#      = O(n)
# default_end

6 Supprimer une paire clé-valeur d’un dictionnaire à partir de sa clé (pop() method)

Python permet de supprimer une paire clé-valeur d’un dictionnaire à partir de sa clé en utilisant la méthode pop(). Cette méthode prend en argument la clé de la paire à supprimer, et retourne la valeur associée à cette clé dans le dictionnaire d’origine (ou None si la clé n’existe pas dans le dictionnaire).

6.1 Syntaxe

# default_start
# Supprimer une paire clé-valeur d'un dictionnaire à partir de sa clé
value = dictName.pop(key)
# default_end

6.2 Exemple

# default_start
pairs = {"a": 1, "b": 2, "c": 3}
print("pairs:", pairs)
# Supprimer la paire clé-valeur associée à la clé "b"
poppedValue = pairs.pop("b")
print("poppedValue:", poppedValue)
print("pairs", pairs)
# default_end

6.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(pairs, keys):
    results = 0
    for key in keys:
        results = results + pairs.pop(key)
    return (pairs, results)
# default_end
# test_start
print(mystere({"a": 1, "b": 2, "c": 3}, ["a", "b"]))
print("C683AKRMaR")
print(mystere({"a": 1, "b": 2, "c": 3}, ["b", "c"]))
# test_end

# default_start
def mystere(pairs, keys):                   # pairs = {"a": 1, "b": 2, "c": 3}, keys = ["a", "b"]
    results = 0                             # results = 0
    for key in keys:                        # key = "a"                     key = "b"
        results = results + pairs.pop(key)  # results = 0 + 1 = 1           results = 1 + 2 = 3
                                            # pairs = {"b": 2, "c": 3}      pairs = {"c": 3}
    return (pairs, results)                 # return ({"c": 3}, 3)
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de dictionnaire pop() en utilisant uniquement les fondamentaux et les fonctions de base des dictionnaires que nous avons vus jusqu’à présent.

Écrire une fonction myPop(pairs, key) qui prend en entrée un dictionnaire pairs et une clé key, qui retourne un tuple contenant le dictionnaire pairs privé de la paire clé-valeur associée à la clé key, et la valeur associée à cette clé dans le dictionnaire d’origine (ou None si la clé n’existe pas dans le dictionnaire).

# exercice: show
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myPop(pairs, key):
    return None
# default_end
# test_start
print(myPop({"a": 1, "b": 2, "c": 3}, "b"))
print("C683AKRMaR")
print(myPop({"a": 1, "b": 2, "c": 3}, "d"))
# test_end
# solution_start
def myPop(pairs, key):
    poppedValue = None
    keys = pairs.keys()
    i = 0
    while i < len(keys):
        if keys[i] == key:
            poppedValue = pairs[keys[i]]
            del pairs[keys[i]]
        i = i + 1
    return (pairs, poppedValue)
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de dictionnaire pop() ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def myPop(pairs, key):
    newPairs = {}                     # 1 affectation
    keys = pairs.keys()               # O(len(pairs))
    i = 0                             # 1 affectation
    # len(pairs) itérations
    while i < len(keys):              # 1 comparaison + 1 longueur
        if keys[i] != key:            # 1 comparaison
            newPairs[keys[i]] = pairs[keys[i]] # 1 accès + 1 accès + 1 affectation + 1 accès + 1 accès
        i = i + 1                     # 1 addition + 1 affectation
    return (newPairs, poppedValue)    # 1 retour
# n = len(pairs)
# T(n) = 1 + n + 1 + n * (2 + 1 + 5 + 2) + 1
#      = 11n + 3
#      = O(n)
# default_end

7 Mettre à jour les paires clé-valeur d’un dictionnaire (update() method)

Python permet de mettre à jour les paires clé-valeur d’un dictionnaire à l’aide de la méthode update(). Cette méthode prend en argument un autre dictionnaire, et ajoute les paires clé-valeur de ce dictionnaire au dictionnaire d’origine. Si une clé du dictionnaire d’argument existe déjà dans le dictionnaire d’origine, alors la valeur associée à cette clé dans le dictionnaire d’origine est remplacée par la valeur associée à cette clé dans le dictionnaire d’argument.

7.1 Syntaxe

# default_start
# Mettre à jour les paires clé-valeur d'un dictionnaire
dictName.update(otherDict)
# default_end

7.2 Exemple

# default_start
pairs1 = {"a": 1, "b": 2, "c": 3}
pairs2 = {"b": 4, "d": 5}
print("pairs1:", pairs1)
print("pairs2:", pairs2)
pairs1.update(pairs2)
print("pairs1 après update:", pairs1)
# default_end

7.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(dicts):
    newDict = {}
    for d in dicts:
        newDict.update(d)
    return newDict
# default_end
# test_start
print(mystere([{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}]))
print("C683AKRMaR")
print(mystere([{"x": 10}, {"y": 20}, {"z": 30}]))
# test_end

# default_start
def mystere(dicts):        # dicts = [{"a": 1, "b": 2}, {"b": 3, "c": 4}, {"a": 5, "c": 6}]
    newDict = {}           # newDict = {}
    for d in dicts:        # d = {"a": 1, "b": 2}               d = {"b": 3, "c": 4}                    d = {"a": 5, "c": 6}
        newDict.update(d)  # newDict = {"a": 1, "b": 2}         newDict = {"a": 1, "b": 3, "c": 4}      newDict = {"a": 5, "b": 3, "c": 6}
    return newDict         # return {"a": 5, "b": 3, "c": 6}
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de dictionnaire update() en utilisant uniquement les fondamentaux et les fonctions de base des dictionnaires que nous avons vus jusqu’à présent.

Écrire une fonction myUpdate(dict1, dict2) qui prend en entrée deux dictionnaires dict1 et dict2, et qui retourne le dictionnaire dict1 mis à jour avec les paires clé-valeur de dict2 (c’est à dire que les paires clé-valeur de dict2 sont ajoutées à dict1, et si une clé de dict2 existe déjà dans dict1, alors la valeur associée à cette clé dans dict1 est remplacée par la valeur associée à cette clé dans dict2).

# exercice: show
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myUpdate(dict1, dict2):
    return None
# default_end
# test_start
print(myUpdate({"a": 1, "b": 2, "c": 3}, {"b": 4, "d": 5}))
print("C683AKRMaR")
print(myUpdate({"x": 10, "y": 20}, {"y": 30, "z": 40}))
# test_end
# solution_start
def myUpdate(dict1, dict2):
    keys2 = dict2.keys()
    i = 0
    while i < len(keys2):
        key = keys2[i]
        value = dict2[key]
        dict1[key] = value
        i = i + 1
    return dict1
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de dictionnaire update() ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def myUpdate(dict1, dict2):
    keys2 = dict2.keys()              # O(len(dict2))
    i = 0                             # 1 affectation
    # len(dict2) itérations
    while i < len(keys2):             # 1 comparaison + 1 longueur
        key = keys2[i]                # 1 accès + 1 affectation
        value = dict2[key]            # 1 accès + 1 affectation
        dict1[key] = value            # 1 accès + 1 affectation + 1 accès + 1 accès
        i = i + 1                     # 1 addition + 1 affectation
    return dict1                      # 1 retour
# n = len(dict2)
# T(n) = n + 1 + n * (2 + 2 + 2 + 4 + 2) + 1
#      = 13n + 2
#      = O(n)
# default_end