Choisir une structure de données
Le tableau des coûts des structures du parcours et la démarche qui part des opérations les plus fréquentes : diagnostiquer une lenteur, associer un besoin à une structure et lire le coût d'une opération.
- 36 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Les étapes
- Mises en situation
Quelques cartes du deck
Choix d'une structure de données : de quoi s'agit-il ?
Voir la réponse
Décision qui consiste à retenir l'organisation des données dont les opérations les plus fréquentes du programme coûtent le moins.
Aucune structure n'est la meilleure partout : la table de hachage cherche vite mais ne trie pas, le tableau accède vite mais insère mal. On choisit donc d'après les opérations, pas d'après l'habitude.
Qu'affiche ce programme ?
```python
from collections import deque
f = deque([1, 2, 3])
f.append(4)
print(f.popleft(), f)`1 deque([2, 3, 4])4 deque([1, 2, 3])1 deque([1, 2, 3, 4])1 deque([2, 3])
Voir la réponse
1 deque([2, 3, 4])appendajoute 4 à droite,popleftretire et rend le plus ancien, 1. C'est une file : premier arrivé, premier sorti, et chaque opération coûte O(1).Pour choisir une structure, on commence par lister les … les plus fréquentes du programme, puis on compare leur … dans chaque candidate.
Voir la réponse
Pour choisir une structure, on commence par lister les opérations les plus fréquentes du programme, puis on compare leur coût dans chaque candidate.
Optimiser une opération rare au prix d'une opération fréquente est la façon la plus courante de se tromper de structure.
File à double extrémité (deque) : de quoi s'agit-il ?
Voir la réponse
Suite où l'on ajoute et retire des éléments aux deux bouts en temps constant.
En Python,
collections.dequeoffreappend,appendleft,popetpopleften O(1), là oùliste.pop(0)décale tous les éléments et coûte O(n).