Données File Implémentation

Identification

Infoforall

17 - Pile et File facilement

⏪

⏬

⏩

1 - Pile (list)

2 - File (deque)

3 - comparaison

4 - Exercices

5 - FAQ

1 - Pile muable avec un modèle list

⇩ ⇧ ⤊

Python ne possède pas de type natif Pile, ou Stack.

Pourtant, s'agissant d'une structure courante, on a parfois besoin d'en créer une rapidement. Comment faire ?

1.1 Schéma de principe avec la list Python

Pour obtenir des primitives à coût CONSTANT, il faut placer le SOMMET de notre Pile du côté de la Fin du tableau dynamique.

En effet :

  • Les méthodes append(elt) et pop() sont à coût constant.
  • Les méthodes insert(elt, 0) et pop(0) sont à coût linéaire.
  • La fonction len(lst) est à coût constant.
graph LR A("[0]") --- B("[1]") --- C("[2]") -.- D("[n-2]") --- E("[n-1]
Sommet de Pile
Fin de tableau") -. empilement -.- I(("ENTREE")) E -. dépilement -.- F(("SORTIE")) style A fill:#99f,stroke:#333,stroke-width:2px style E fill:#ff9,stroke:#333,stroke-width:2px style B fill:#99f,stroke:#333,stroke-width:2px style C fill:#99f,stroke:#333,stroke-width:2px style D fill:#99f,stroke:#333,stroke-width:2px
1.2 Pile sous forme de list Python

A - Les primitives désirées pour la Pile MUABLE
  1. nouvelle_pile() -> 'Pile VIDE'
  2. est_pile_vide(p:'Pile') -> bool
  3. empiler(elt:'Elt', p:'Pile') -> None
  4. depiler(p:'Pile NON VIDE') -> 'Elt'
  5. lire_sommet(p:'Pile NON VIDE') -> 'Elt'
  6. taille(p:'Pile') -> int
B - Implémentation avec le type list
  1. nouvelle_pile() -> 'Pile VIDE'

    2. Deux versions possibles.

    >>> p = list()
    >>> p = []

    Coût CONSTANT dans les deux cas.

  2. est_pile_vide(p:'Pile') -> bool
    3. >>> p == [] True

    Coût CONSTANT.

  3. empiler(elt:'Elt', p:'Pile') -> None
    4. >>> p.append(50) # on place 50 au sommet >>> p == [] False >>> p.append(20) # on place 20 au sommet >>> p.append(10) # on place 10 au sommet

    Le sommet contient donc 10, et on trouvera 20 et 50 en dessous.

    Nous avons vu que, dans le cas du tableau dynamique, le coût amorti est CONSTANT.

  4. depiler(p:'Pile NON VIDE') -> 'Elt'
    5. >>> p.pop() # on dépile le sommet 10

    On récupère la valeur de l'ancien sommet. Le sommet est maintenant le 20.

    Nous avons vu que, dans le cas du tableau dynamique, le coût est CONSTANT.

  5. lire_sommet(p:'Pile NON VIDE') -> 'Elt'

    6. On sait que le sommet est à la fin de notre tableau dynamique. Deux versions pour lire ce que contient la dernière case du tableau.

    >>> p[len(p)-1] 20
    >>> p[-1] 20

    Le coût est CONSTANT.

  6. taille(p:'Pile') -> int
    7. >>> len(p) 2

    Le pile contient bien le sommet 20 suivi d'un 50. Deux éléments.

    Le coût est CONSTANT car le nombre d'éléments est stocké directement dans l'objet.

C - Erreurs classiques sur les mutables

La pile est modifiée en place. N'écrivez donc JAMAIS ceci avec une pile mutable :

>>> p = p.append(50) # p contient maintenant None, bravo... >>> p = p.pop() # p n'est plus une pile mais un élément, bravo...
1.3 Copie de list Python

A - Un alias n'est pas une copie

Créons une première ligne par ajouts successifs :

>>> t = list() >>> t.append(50) >>> t.append(20) >>> t [50, 20] >>> id(t) 139770911569472

Avec les types mutables, les affectations ne créent que des alias.

>>> t2 = t >>> id(t2) 139770911569472 # t2 et t pointent vers la même zone mémoire >>> t2.append(10) >>> t2 [50, 20, 10] >>> t [50, 20, 10] # modifier t2 modifie donc t, et inversement

L'opérateur == teste le contenu alors que is teste l'adresse. Ici, puisque les deux pointent la même zone mémoire, les deux opérateurs donnent la même réponse :

>>> t == t2 # même contenu ? True >>> t is t2 # même adresse ? True
B - Copie rapide

Pour faire une copie rapide d'un tableau, plusieurs solutions.

Utilisation du constructeur de list

>>> t3 = list(t) # Constructeur de list >>> t3 [50, 20, 10]

Utilisation de la fonction copy() du module copy

>>> import copy >>> t4 = copy.copy(t) >>> t4 [50, 20, 10]

Par compréhension

>>> t5 = [v for v in t] >>> t5 [50, 20, 10]

Même contenu, mais adresses mémoires différentes : ce sont des copies, pas des alias.

>>> id(t) 139770911569472 >>> id(t3) 139770911571648 >>> id(t4) 139770911537344 >>> id(t5) 139770930199104
>>> t3 is t False >>> t3 == p True
C - Limites de la copie rapide

Les copies précédentes ne sont pas de vraies copies indépendantes si les éléments contenus sont mutables.

Voici un exemple où on voit que les tableaux t et t2 bien deux structures différentes qui stockent des éléments identiques.

>>> t = [ [5, 2, 10], [7, 9, 3] ] >>> import copy >>> t2 = copy.copy(t) >>> t == t2 True >>> t is t2 False # t2 est bien une copie et pas un alias

Pourtant, si on modifie l'élément 0 du premier, on modifie également l'élément 0 du second !

>>> t[0][0] = 50 # on modifie le 5 de t en 50 >>> t [[50, 2, 10], [7, 9, 3]] >>> t2 [[50, 2, 10], [7, 9, 3]] # l'élément 0 de t2 a été modifié aussi !
D - Copie profonde

Si le tableau de base contient des éléments mutables, il faut réaliser des copies des éléments également.

Il faut alors utiliser la fonction deepcopy() du module copy.

>>> t = [ [5, 2, 10], [7, 9, 3] ] >>> import copy >>> t3 = copy.deepcopy(t) >>> t3 is t False >>> t3[0] is t[0] False >>> t3[0] == t[0] True

2 - File muable avec deque

⇩ ⇧ ⤊

Python ne possède pas de type natif File, ou Queue.

Pourtant, s'agissant d'une structure courante, on a parfois besoin d'en créer une rapidement. Comment faire ?

Nous avons vu qu'on peut faire cela avec une liste chaînée : on insère en Fin et on supprime en Tête.

Mais il n'en existe pas nativement en Python. Il va falloir utiliser un module particulier.

2.1 File sous forme de deque Python

A - Les primitives voulues pour la File
  1. nouvelle_file() -> 'File VIDE'
  2. est_file_vide(f:'File') -> bool
  3. enfiler(elt:'Elt', f:'File') -> None
  4. defiler(f:'File NON VIDE') -> 'Elt'
  5. lire_avant(f:'File NON VIDE') -> 'Elt'
  6. taille(f:'File') -> int
Structure deque

Utilisons le module collections qui rajoute quelques nouveaux types construits en plus des types natifs list dict tuple.

La structure deque signfie double-ended queue en anglais, file à deux entrées-sorties en français.

Il s'agit d'une structure qui permet d'insérer et de supprimer à coût CONSTANT sur chacune des deux extrémités. C'est ce que nous voulions faire avec notre liste avant de nous rendre compte que ce n'était pas si facile que cela ! Il s'agit certainement à l'interne d'une liste doublement chaînée.

>>> import collections >>> f = collections.deque() >>> f deque([]) >>> f.append(10) >>> f deque([10]) >>> f.append(20) >>> f deque([10, 20]) >>> f.appendleft(50) >>> f deque([50, 10, 20]) >>> f.appendleft(100) >>> f deque([100, 50, 10, 20]) >>> f.pop() 20 >>> f deque([100, 50, 10]) >>> f.popleft() 100 >>> f deque([50, 10])
C - Les primitives désirées pour la File MUTABLE
  1. nouvelle_file() -> 'File VIDE'
    2. >>> import collections >>> f = collections.deque() >>> f deque([])

    Coût CONSTANT.

  2. est_file_vide(f:'File') -> bool
    3. >>> f == collections.deque() True

    Coût CONSTANT.

  3. enfiler(elt:'Elt', f:'File') -> None
    4. >>> f.append(10) >>> f deque([10]) >>> f.append(20) >>> f deque([10, 20]) >>> f.append(50) >>> f deque([10, 20, 50])

    L'avant est le 10, et l'arrière le 50.

    Coût CONSTANT.

  4. defiler(p:'File NON VIDE') -> 'Elt'
    5. >>> f.popleft() # on dépile l'avant 10 >>> f deque([20, 50])

    L'avant est maintenant le 20.

    Coût CONSTANT.

  5. lire_avant(f:'File NON VIDE') -> 'Elt'
    6. >>> f[0] 20

    C'est un raccourci de la séquence suivante :

    >>> x = f.popleft() >>> f.appendleft(x) >>> x 20

    Le coût est CONSTANT puisque ces trois instructions sont à coût CONSTANT.

  6. taille(p:'File') -> int
    7. >>> f deque([20, 50]) >>> len(f) 2

    Coût CONSTANT.

D - Erreurs classiques sur les mutables

La file est modifiée en place.

N'écrivez donc JAMAIS ceci avec une file muable :

>>> f = f.append(50) # f contient maintenant None, bravo... >>> f = f.popleft() # f n'est plus une file mais un élément, bravo...

Même remarque que pour les piles pour nos files deque muable.

copy() pour les copies rapides si le deque ne contient pas de types muables.

deepcopy() si notre deque contient des éléments muables.

2.2 File du pauvre sous forme de list Python

⚠⚠⚠ mauvaise implémentaiton ⚠⚠⚠

C'est une mauvaise implémentation de file si les données sont vraiment nombreuses.

Le défilement est à coût LINEAIRE !

Mais on l'utilise parfois sur un prototype, juste pour tester un truc : défiler est à coût LINEAIRE. Pas terrible.

Les primitives désirées pour la File MUABLE de mauvaise qualité
  1. nouvelle_file() -> 'File VIDE'
    2. >>> f = list() >>> f []

    Coût CONSTANT.

  2. est_file_vide(f:'File') -> bool
    3. >>> f == [] True

    Coût CONSTANT.

  3. enfiler(elt:'Elt', f:'File') -> None
    4. >>> f.append(10) >>> f [10] >>> f.append(20) >>> f [10, 20] >>> f.append(50) >>> f [10, 20, 50]

    L'avant est le 10, et l'arrière le 50.

    Coût CONSTANT.

  4. defiler(p:'File NON VIDE') -> 'Elt'
    5. >>> f.pop(0) # on dépile l'avant 10 >>> f [20, 50]

    L'avant est maintenant le 20.

    Coût LINEAIRE, attention.

  5. lire_avant(f:'File NON VIDE') -> 'Elt'
    6. >>> f[0] 20

    Coût CONSTANT.

  6. taille(p:'File') -> int
    7. >>> f [20, 50] >>> len(f) 2

    Coût CONSTANT.

3 - Comparaison expérimentale

⇩ ⇧ ⤊

01 ✔° Utiliser ce programme qui va vous permettre de constater que l'enfilement et le défilement se fait bien à coût constant dans notre Pile implémentée par une list-Python (qui n'est pas une liste chaînée mais un tableau dynamique) :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
import time import random import collections def estimer_temps_empilement(n:int) -> float: """Renvoie le temps pour empiler un élément dans une pile de n éléments""" p = list() elts = [random.randint(0,1000) for _ in range(n)] elt = random.randint(0,1000) for k in range(n): p.append(elts[k]) ti = time.time() p.append(elt) tf = time.time() return tf - ti def estimer_temps_depilement(n:int) -> float: """Renvoie le temps pour dépiler un élément dans une pile de n éléments""" p = list() elts = [random.randint(0,1000) for _ in range(n)] for k in range(n): p.append(elts[k]) ti = time.time() p.pop() tf = time.time() return tf - ti def tester_empiler(n:int) -> None: """Affiche le temps pour empiler dans une pile de n éléments""" print(f"{n} éléments : {estimer_temps_empilement(n)}") def tester_depiler(n:int) -> None: """Affiche le temps pour dépiler dans une pile de n éléments""" print(f"{n} éléments : {estimer_temps_depilement(n)}") tests = [10**x for x in range(1, 7)] print("Temps pour empiler dans une pile de") for test in tests: tester_empiler(test) print("\nTemps pour dépiler dans une file de") for test in tests: tester_depiler(test)

02 ✔° Utiliser ce programme qui va vous permettre de constater que l'enfilement et le défilement se fait bien à coût constant dans notre File implémentée par une deque :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
import time import random import collections def estimer_temps_enfilement(n:int) -> float: """Renvoie le temps pour enfiler un élément dans une file de n éléments""" f = collections.deque() elts = [random.randint(0,1000) for _ in range(n)] elt = random.randint(0,1000) for k in range(n): f.append(elts[k]) ti = time.time() f.append(elt) tf = time.time() return tf - ti def estimer_temps_defilement(n:int) -> float: """Renvoie le temps moyen pour dépiler un élément dans une pile de n éléments""" f = collections.deque() elts = [random.randint(0,1000) for _ in range(n)] for k in range(n): f.append(elts[k]) ti = time.time() f.popleft() tf = time.time() return tf - ti def tester_enfiler(n:int) -> None: """Affiche le temps pour enfiler dans une file de n éléments""" print(f"{n} éléments : {estimer_temps_enfilement(n)}") def tester_defiler(n:int) -> None: """Affiche le temps pour défiler dans une file de n éléments""" print(f"{n} éléments : {estimer_temps_defilement(n)}") tests = [10**x for x in range(1, 7)] print("Temps pour enfiler dans une pile de") for test in tests: tester_enfiler(test) print("\nTemps pour défiler dans une file de") for test in tests: tester_defiler(test)

03 ✔° Utiliser ce programme qui va vous permettre de constater que l'enfilement se fait à coût CONSTANT mais le défilement se fait à coût LINEAIRE dans la File de mauvaise qualité implémentée par une list-Python :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
import time import random import collections def estimer_temps_enfilement(n:int) -> float: """Renvoie le temps pour enfiler un élément dans une file de n éléments""" f = list() elts = [random.randint(0,1000) for _ in range(n)] elt = random.randint(0,1000) for k in range(n): f.append(elts[k]) ti = time.time() f.append(elt) tf = time.time() return tf - ti def estimer_temps_defilement(n:int) -> float: """Renvoie le temps moyen pour dépiler un élément dans une pile de n éléments""" f = list() elts = [random.randint(0,1000) for _ in range(n)] for k in range(n): f.append(elts[k]) ti = time.time() f.pop(0) tf = time.time() return tf - ti def tester_enfiler(n:int) -> None: """Affiche le temps pour enfiler dans une file de n éléments""" print(f"{n} éléments : {estimer_temps_enfilement(n)}") def tester_defiler(n:int) -> None: """Affiche le temps pour défiler dans une file de n éléments""" print(f"{n} éléments : {estimer_temps_defilement(n)}") tests = [10**x for x in range(1, 7)] print("Temps pour enfiler dans une pile de") for test in tests: tester_enfiler(test) print("\nTemps pour défiler dans une file de") for test in tests: tester_defiler(test)

4 - Exercices à base de piles et de files

⇩ ⇧ ⤊

Nous allons voir deux applications possibles de Pile et File en utilisant le format de l'exercice 2 de l'épreuve pratique de programmation : le code à trous comportant des ...

04° Compléter le programme suivant pour qu'on parvienne à le faire fonctionner correctement. On doit pouvoir prédire si l'expression arithmétique fournie est correctement parenthésée, ou pas.

Les piles seront implémentées avec la structure list de Python.

On rappelle la signature de la méthode des strings str.replace(c1:str, c2:strr) -> str qui renvoie un string où les occurrences de c1 ont été remplacées par c1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def est_correctement_parenthesee(expression:str) -> bool: """Prédicat qui renvoie True si l'expression est bien parenthesée""" print(expression) supprime = "0123456789 +-/* abcdefghijklmnopqrstuvwxyz" # liste les caractères à supprimer for ... in ...: # pour chaque caractère à supprimer expression = ... # supprime ce caractère de l'expression print(expression) p = ... # crée une nouvelle Pile vide nommée p try: # tente de réaliser les actions suivantes for parenthese in expression: # pour chaque parenthèse dans l'expression if ... : # si c'est une parenthèse ouvrante ... # empile cette parenthèse elif parenthese == ')': # si c'est une parenthèse fermante ... # dépile la pile except: # et fait ceci si une exception survient return ... # Erreur dans le dépilement : trop de parenthèses fermantes return ... # on répond en testant si la pile est bien vide e = "(5+2) * ((2)) + 4)" print(est_correctement_parenthesee(e))

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def est_correctement_parenthesee(expression:str) -> bool: """Prédicat qui renvoie True si l'expression est bien parenthesée""" print(expression) supprime = "0123456789 +-/* abcdefghijklmnopqrstuvwxyz" # liste les caractères à supprimer for caractere in supprime: # pour chaque caractère à supprimer expression = expression.replace(caractere, "") # supprime ce caractère de l'expression print(expression) p = [] # crée une nouvelle Pile vide nommée p try: # tente de réaliser les actions suivantes for parenthese in expression: # pour chaque parenthèse dans l'expression if parenthese == '(': # si c'est une parenthèse ouvrante p.append( '(' ) # empile cette parenthèse elif parenthese == ')': # si c'est une parenthèse fermante p.pop() # dépile la pile except: # et fait ceci si une exception survient return False # Erreur dans le dépilement : trop de parenthèses fermantes return p == [] # on répond en testant si la pile est bien vide e = "(5+2) * ((2)) + 4)" print(est_correctement_parenthesee(e))

05° Compléter le programme suivant pour qu'on parvienne savoir s'il existe une sortie dans ce labyrinthe. Vous allez voir qu'il est assez complexe car nous allons voir cette année comment traiter les graphes correctement. Pour l'instant, il faut y aller brutalement.

Les piles seront implémentées avec la structure list de Python.

Principe général

  • Empiler les coordonnées (ligne, colonne) de la case actuellement visitée.
  • Si c'est la sortie, on dit que c'est bon.
  • Si ce n'est pas la sortie, on tente d'explorer une case adjacente qui n'a pas encore été explorée en l'empilant à son tour.
  • S'il n'existe plus de cases adjacentes non explorées, on dépile cette case, ce qui permettra de "retourner en arrière", c'est à dire de retrouver la dernière case visitée juste avant.

Comment travailler ?

  1. Il faut commencer par comprendre le déroulé du programme.
  2. Compléter alors la première fonction (trajet_sortie()) qui va être lancée en ligne.
  3. Et poursuivre en lançant régulièrement une fois de temps en temps pour voir si cela commence à ressembler à quelque chose.

Encodage de la matrice :

Elle est indiquée ligne 103.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
# IMPORTATION ================================================================================ import copy # CONSTANTE ================================================================================== AFFICHAGE = {0:' ▅ ', 1:' . ', 2:' x ', 9:' ⎆ ', 'actuel':' ☺ '} # DECLARATION DE FONCTION ==================================================================== def affiche(m, d, itineraire): """Affichage de la position actuelle dans le labyrinthe""" print(itineraire) print(f"-- deplacement en ligne {d[0]},colonne {d[1]}--") for ligne in range(len(m)): # Attention, ligne est un indice for colonne in range(len(m[0])): # Attention, colonne est un indice case = m[ligne][colonne] if (ligne, colonne) == d: print(AFFICHAGE['actuel'], end='') else: print(AFFICHAGE[case], end='') print('') input("ENTREE pour la suite...") print("\n\n") def trajet_sortie(mat:'list[list]', depart:tuple) -> 'list[tuple]': """Renvoie la liste des (ligne, colonne) à suivre pour sortir du labyrinthe""" m = ... # m est une copie profonde de la matrice reçue itineraire = ... # on crée une Pile itineraire VIDE itineraire.append(depart) # on emplie les coordonnées de départ if cherche(m, itineraire): # si cherche() à trouver return itineraire # renvoie l'itinéraire else: # sinon return ... # renvoie un itinéaire vide compatible avec le prototype visible ligne 30 def inconnue_a_gauche(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case de gauche n'a pas encore été explorée""" return (colonne-1) >= 0 and m[ligne][colonne-1] in [1, 9] def inconnue_a_droite(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case de droite n'a pas encore été explorée""" return (colonne+1) < len(m[0]) and m[ligne][colonne+1] in [1, 9] def inconnue_au_dessus(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case au dessus n'a pas encore été explorée""" return ... def inconnue_en_dessous(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case en dessous n'a pas encore été explorée""" return ... def cherche(m:'list[list]', itineraire:'Pile[tuple]|PileVIDE') -> bool: """Fonction récursive qui modifie itineraire et prédit s'il existe une sortie, ou pas""" # Premier cas de base : la Pile itinéraire est vide : c'est fini if ...: # Si la Pile est vide return False # On signale qu'il n'y a pas de sortie ligne, colonne = itineraire[-1] # on lit les indices ligne et colonne du sommet affiche(m, (ligne,colonne), itineraire ) # on affiche le labyrinthe et on lance l'attente # Deuxième case de base : nous sommes sur la sortie : c'est fini. if m[ligne][colonne] == ...: # Si c'est la case de sortie return True # on signale que la sortie existe # Cas récursif else: ... = 2 # on marque à 2 la case actuelle if inconnue_a_gauche(ligne, colonne, m): # Si case gauche explorable et inconnue itineraire.append( (ligne, colonne-1) ) # on empile cette destination return cherche(m, itineraire) # on y cherche la sortie elif inconnue_a_droite(ligne, colonne, m): # Si case droite explorable et inconnue ... # on empile cette destination return cherche(m, itineraire) # on y cherche la sortie elif ... : # Si case au dessus explorable et inconnue ... # on empile cette destination ... # on y cherche la sortie elif .: # Si case en dessous explorable et inconnue ... # on empile cette destination ... # on y cherche la sortie else: # plus de cases explorables depuis ici ... # on dépile cette case pour repartir en arrière return cherche(m, itineraire) # on cherche depuis la nouvelle case # PROGRAMME PRINCIPAL =============================================================================== if __name__ == "__main__": # 0 pour mur, 1 pour couloir, 2 pour déjà visitée, 9 pour sortie matrice = [ [0, 1, 0, 1, 1], [0, 1, 1, 1, 1], [0, 1, 0, 1, 0], [0, 9, 0, 1, 0] ] ligne_depart = 0 colonne_depart = 1 depart = (ligne_depart, colonne_depart) # création du couple (ligne, colonne) du départ trajet = trajet_sortie(matrice, depart) # recherche du trajet possible, ou pas print(trajet)

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
# IMPORTATION ================================================================================ import copy # CONSTANTE ================================================================================== AFFICHAGE = {0:' ▅ ', 1:' . ', 2:' x ', 9:' ⎆ ', 'actuel':' ☺ '} # DECLARATION DE FONCTION ==================================================================== def affiche(m, d, itineraire): """Affichage de la position actuelle dans le labyrinthe""" print(itineraire) print(f"-- deplacement en ligne {d[0]},colonne {d[1]}--") for ligne in range(len(m)): # Attention, ligne est un indice for colonne in range(len(m[0])): # Attention, colonne est un indice case = m[ligne][colonne] if (ligne, colonne) == d: print(AFFICHAGE['actuel'], end='') else: print(AFFICHAGE[case], end='') print('') input("ENTREE pour la suite...") print("\n\n") def trajet_sortie(mat:'list[list]', depart:tuple) -> 'list[tuple]': """Renvoie la liste des (ligne, colonne) à suivre pour sortir du labyrinthe""" m = copy.deepcopy(mat) # m est une copie profonde de la matrice reçue itineraire = [] # on crée une Pile itineraire itineraire.append(depart) # on emplie les coordonnées d if cherche(m, itineraire): # si cherche() à trouver return itineraire # renvoie l'itinéraire else: # sinon return [()] # renvoie un itinéaire vide compatible avec le prototype def inconnue_a_gauche(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case de gauche n'a pas encore été explorée""" return (colonne-1) >= 0 and m[ligne][colonne-1] in [1, 9] def inconnue_a_droite(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case de droite n'a pas encore été explorée""" return (colonne+1) < len(m[0]) and m[ligne][colonne+1] in [1, 9] def inconnue_au_dessus(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case au dessus n'a pas encore été explorée""" return (ligne-1) >= 0 and m[ligne-1][colonne] in [1, 9] def inconnue_en_dessous(ligne:int, colonne:int, m:'list[list]') -> bool: """Prédicat qui renvoie True si la case en dessous n'a pas encore été explorée""" return (ligne+1) < len(m) and m[ligne+1][colonne] in [1, 9] def cherche(m:'list[list]', itineraire:'Pile[tuple]|PileVIDE') -> bool: """Fonction récursive qui modifie itineraire et prédit s'il existe une sortie, ou pas""" # Premier cas de base : la Pile itinéraire est vide : c'est fini... if len(itineraire) == 0: # Si la Pile est vide return False # On signale qu'il n'y a pas de sortie ligne, colonne = itineraire[-1] # on lit les indices ligne et colonne du sommet affiche(m, (ligne,colonne), itineraire ) # on affiche le labyrinthe et on lance l'attente # Deuxième case de base : nous sommes sur la sortie : c'est fini. if m[ligne][colonne] == 9: # Si c'est la case de sortie return True # on signale que la sortie existe # Cas récursif else: m[ligne][colonne] = 2 # on marque à 2 la case actuelle if inconnue_a_gauche(ligne, colonne, m): # Si case gauche explorable et inconnue itineraire.append( (ligne, colonne-1) ) # on empile cette destination return cherche(m, itineraire) # on y cherche la sortie elif inconnue_a_droite(ligne, colonne, m): # Si case droite explorable et inconnue itineraire.append( (ligne, colonne+1) ) # on empile cette destination return cherche(m, itineraire) # on y cherche la sortie elif inconnue_au_dessus(ligne, colonne, m): # Si case au dessus explorable et inconnue itineraire.append( (ligne-1, colonne) ) # on empile cette destination return cherche(m, itineraire) # on y cherche la sortie elif inconnue_en_dessous(ligne, colonne, m): # Si case en dessous explorable et inconnue itineraire.append( (ligne+1, colonne) ) # on empile cette destination return cherche(m, itineraire) # on y cherche la sortie else: # plus de cases explorables depuis ici itineraire.pop() # on dépile cette case pour repartir en arrière return cherche(m, itineraire) # on cherche depuis la nouvelle case # PROGRAMME PRINCIPAL =============================================================================== if __name__ == "__main__": # 0 pour mur, 1 pour couloir, 2 pour déjà visitée, 9 pour sortie matrice = [ [0, 1, 0, 1, 1], [0, 1, 1, 1, 1], [0, 1, 0, 1, 0], [0, 9, 0, 1, 0] ] ligne_depart = 0 colonne_depart = 1 depart = (ligne_depart, colonne_depart) # création du couple (ligne, colonne) du départ trajet = trajet_sortie(matrice, depart) # recherche du trajet possible, ou pas... print(trajet)

Autre partie que nous allons traiter cette année : l'ordonnancement des tâches dans la vraie vie ou l'ordonnancement des processus dans un ordinateur.

06° Nous allons travailler sur la gestion de tâches ayant des priorités. Disons 1 pour les moins urgentes et 4 pour les plus urgentes.

La fonction creer_les_taches() va générer un tableau contenant plusieurs dictionnaires dont les clés représentent (voir ligne 17)

  • le nom de la tâche,
  • sa priorité entre 1 et 4 et
  • le nombre d'opérations nécessaires pour réaliser cette tâche.

La fonction trier() a pour but de créer un tableau contenant les 4 Files de priorité f1 f2 f3 f4 et de les remplir avec les tâches trouvées dans le tableau des tâches.

La fonction lancer() a pour but de simuler l'exécution progressive des tâches en simulant un tourniquet (round-robin en anglais) : on commence par les tâches les plus prioritaires mais en alternant entre elles. Ainsi si on doit exécuter A, B et C ayant la même priorité, on donne la main tour à tour à A, B, C, A, B, C, A, B, C... jusqu'à ce qu'une des tâches soit terminée.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
# Importations ======================================================================================== import random import collections # Déclaration des fonctions ========================================================================== def creer_les_taches(n:'int POSITIF') -> 'list[dict]': """Renvoie un tableau contenant des taches sous forme de dictionnaires""" taches = [] # création du tableau dynamique for k in range(1, n+1): # pour k variant de 1 à n nom = f"Tache n°{k}" # on gènère le nom priorite = random.randint(1,4) # on choisit la priorité nbr = random.randint(1,10) # on définit le nombre d'actions à réaliser tache = {'nom':nom, 'priorite': priorite, 'nbr':nbr} # on gènère la tache taches.append(tache) # on la rajoute dans le tableau dynamique return taches # on renvoie le tableau dynamique def trier(taches:'list[dict]') -> 'list[File]': """Renvoie un tableau contenant 4 files de tâches à réaliser, de la moins prioritaires à la plus prioritaires""" f1 = ... # création de la file de priorité 1, vide au départ f2 = ... # création de la file de priorité 2, vide au départ f3 = ... # création de la file de priorité 3, vide au départ f4 = ... # création de la file de priorité 4, vide au départ tf = ... # Création du tableau à remplir avec les files de priorité en ordre croissant for ... : # Pour chaque tâche à faire priorite = ... # on récupère sa priorité i = priorite - 1 # on détermine l'indice correspondant dans le tableau tf tf[i].append(...) # on rajoute cette tâche dans la bonne file du tableau tf return tf # on renvoie le tableau contenant les 4 files def lancer(taches:'list[dict]') -> None: """Fonction simulant le déroulé de ces tâches en utilisant un tourniquet et un simple print()""" files = trier(taches) # on gènère le tableau des files à partir des tâches reçues for i in range(len(files)-1, -1, -1): # pour chaque indice de files en commençant par la plus prioritaire file_en_cours = ... # on récupère la file voulue while ... : # Tant qu'elle n'est pas vide tache = ... # on défile la tâche suivante print(tache) # on affiche la tâche ... # on décrémente son nombre d'actions à réaliser if tache["nbr"] > 0: # s'il reste encore des actions à réaliser pour cette tâche ... # on l'enfile dans la file else: # sinon, c'est qu'elle est finie print(f'--> {tache["nom"]} TERMINEE') # juste un message signalant la fin de la tâche # Programme principal if __name__ == "__main__": les_taches = creer_les_taches(10) lancer(les_taches)

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
# Importations ======================================================================================== import random import collections # Déclaration des fonctions ========================================================================== def creer_les_taches(n:'int POSITIF') -> 'list[dict]': """Renvoie un tableau contenant des taches sous forme de dictionnaires""" taches = [] # création du tableau dynamique for k in range(1, n+1): # pour k variant de 1 à n nom = f"Tache n°{k}" # on gènère le nom priorite = random.randint(1,4) # on choisit la priorité nbr = random.randint(1,10) # on définit le nombre d'actions à réaliser tache = {'nom':nom, 'priorite': priorite, 'nbr':nbr} # on gènère la tache taches.append(tache) # on la rajoute dans le tableau dynamique return taches # on renvoie le tableau dynamique def trier(taches:'list[dict]') -> 'list[File]': """Renvoie un tableau contenant 4 files de tâches à réaliser, de la moins prioritaires à la plus prioritaires""" f1 = collections.deque() # création de la file de priorité 1 f2 = collections.deque() # création de la file de priorité 2 f3 = collections.deque() # création de la file de priorité 3 f4 = collections.deque() # création de la file de priorité 4 tf = [f1, f2, f3, f4] # Création du tableau des files de priorité en ordre croissant for tache in taches: # Pour chaque tâche à faire priorite = tache["priorite"] # on récupère sa priorité i = priorite - 1 # on détermine l'indice correspondant dans le tableau tf tf[i].append(tache) # on rajoute cette tâche dans la bonne file du tableau tf return tf # on renvoie le tableau contenant les 4 files def lancer(taches:'list[dict]') -> None: """Fonction simulant le déroulé de ces tâches en utilisant un tourniquet et un simple print()""" files = trier(taches) # on gènère le tableau des files à partir des tâches reçues for i in range(len(files)-1, -1, -1): # pour chaque indice de files en commençant par la plus prioritaire file_en_cours = files[i] # on récupère la file voulue while not file_en_cours == collections.deque(): # Tant qu'elle n'est pas vide tache = file_en_cours.popleft() # on défile la tâche suivante print(tache) # on affiche la tâche tache["nbr"] = tache["nbr"] - 1 # on décrémente son nombre d'actions à réaliser if tache["nbr"] > 0: # s'il reste encore des actions à réaliser pour cette tâche file_en_cours.append(tache) # on l'enfile dans la file else: # sinon, c'est qu'elle est finie print(f'--> {tache["nom"]} TERMINEE') # juste un message signalant la fin de la tâche # Programme principal if __name__ == "__main__": les_taches = creer_les_taches(10) lancer(les_taches)

L'ordonnancement se complique vite car les tâches peuvent être temporairement en pause (il pleut, le chantier est bloqué ou le programme est en attente d'une réponse) ou qu'une tâche vient d'apparaître.

Nous verrons comment gérer cela efficacement.

5 - FAQ

⇩ ⇧ ⤊

Rien pour l'instant

Les activités suivantes consisteront à implémenter à la main des piles et des files.

Activité publiée le 23 10 2020
Dernière modification : 10 12 2023
Auteur : ows. h.


⏪

⏫

⏩