Publié · en amélioration
Algorithm
Comprendre les tableaux, listes chaînées, piles, files et tables de hachage, le coût de chaque opération et comment choisir la bonne structure.
Une structure de données est une manière d'organiser des données en mémoire, accompagnée des opérations peu coûteuses sur cette organisation. Ce thème couvre les cinq structures sur lesquelles repose presque tout programme : tableaux et tableaux dynamiques, listes chaînées, piles, files et deques, et tables de hachage. Il explique aussi la mémoire contiguë face à la mémoire chaînée, les fonctions de hachage, les collisions et le facteur de charge.
La structure choisie détermine si une opération coûte O(1) ou O(n). Construire une file en retirant les éléments au début d'une liste, ou tester l'appartenance dans une liste, ralentit fortement un programme dès que les données grossissent. Savoir ce que sont vraiment list, deque, dict et set en Python, vector, deque et unordered_map en C++, ArrayList, ArrayDeque et HashMap en Java, ainsi qu'Array, Map et Set en TypeScript permet d'éviter ces pièges, et c'est la première chose que vérifient les entretiens techniques.
Commencez par dérouler chaque structure à la main sur un petit exemple pour voir ce qui bouge en mémoire. Implémentez ensuite une pile, une file en tampon circulaire et une table de hachage à chaînage séparé, résumez les coûts dans un tableau et mesurez-les avec un chronomètre. Terminez par des exercices où la compétence principale consiste à choisir la bonne structure.
Les tableaux offrent un accès O(1) par indice et une bonne utilisation du cache ; les listes chaînées permettent d'insérer et de supprimer en O(1) à côté d'un nœud déjà connu.
Un tableau dynamique grandit d'un facteur constant et recopie ses éléments, si bien que les ajouts coûteux occasionnels restent en moyenne O(1).
Une pile retire l'élément le plus récent, une file le plus ancien. Les deques et les tampons circulaires rendent O(1) les opérations aux deux extrémités.
Une table de hachage associe les clés à des alvéoles pour une recherche en O(1) en moyenne, résout les collisions par exemple par chaînage et s'agrandit quand le facteur de charge dépasse un seuil.
Une table de hachage à chaînage séparé : le hachage de la clé modulo le nombre d'alvéoles choisit l'alvéole, une clé existante voit seulement sa valeur remplacée, et dès que le facteur de charge dépasse 0,75 les alvéoles doublent et toutes les paires sont réinsérées. Le script montre aussi une liste utilisée comme pile et un deque utilisé comme file.
data_structures.py
from collections import deque
class HashMap:
"""Separate chaining: each bucket is a list of (key, value) pairs."""
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size > 0.75 * len(self.buckets): # load factor limit
old = self.buckets
self.buckets = [[] for _ in range(2 * len(old))]
for pairs in old:
for k, v in pairs:
self._bucket(k).append((k, v))
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
stack = [1, 2, 3]
stack.append(4)
print("stack pop:", stack.pop()) # 4 (LIFO)
queue = deque([1, 2, 3])
queue.append(4)
print("queue popleft:", queue.popleft()) # 1 (FIFO)
ages = HashMap()
for name, age in [("ada", 36), ("alan", 41), ("grace", 85)]:
ages.put(name, age)
ages.put("ada", 37)
print("ada:", ages.get("ada"), "size:", ages.size) # ada: 37 size: 3
python data_structures.pySix chapitres pour aller de l'installation aux notions essentielles de Structures de données de base.
Posez vos questions, partagez votre expérience et échangez vos avis sur Structures de données de base.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.