Reponse A: OpenAI GPT-5 mini
Langue cible: fr Réponse: # Implémentation d'un cache LRU utilisant une table de hachage + une liste doublement chaînée # - La table de hachage (dict) fournit un accès O(1) de clé -> nœud # - La liste doublement chaînée maintient l'ordre d'utilisation : le plus récemment utilisé en tête, le moins récemment utilisé en queue # - Lorsqu'une clé est consultée ou mise à jour, nous déplaçons son nœud en tête # - Lorsque la capacité est dépassée, nous supprimons le nœud en queue (LRU) et supprimons sa clé de la table class _Node: """Nœud de liste doublement chaînée pour contenir la clé et la valeur.""" def __i...
Afficher la reponse complete ▼
Langue cible: fr Réponse: # Implémentation d'un cache LRU utilisant une table de hachage + une liste doublement chaînée # - La table de hachage (dict) fournit un accès O(1) de clé -> nœud # - La liste doublement chaînée maintient l'ordre d'utilisation : le plus récemment utilisé en tête, le moins récemment utilisé en queue # - Lorsqu'une clé est consultée ou mise à jour, nous déplaçons son nœud en tête # - Lorsque la capacité est dépassée, nous supprimons le nœud en queue (LRU) et supprimons sa clé de la table class _Node: """Nœud de liste doublement chaînée pour contenir la clé et la valeur.""" def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): """Initialise LRUCache avec la capacité donnée. Gère capacity <= 0 en rendant effectivement le cache inutilisable (get renvoie -1, put est sans effet). """ self.capacity = max(0, int(capacity)) self.cache = {} # key -> _Node # Nœuds sentinelles pour head et tail afin d'éviter les vérifications de cas limites self.head = _Node() # Le plus récemment utilisé vient juste après head self.tail = _Node() # Le moins récemment utilisé est juste avant tail self.head.next = self.tail self.tail.prev = self.head self.size = 0 # Aide interne : ajouter le nœud juste après head (marquer comme récemment utilisé) def _add_node(self, node: _Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node # Aide interne : supprimer un nœud existant de la liste chaînée def _remove_node(self, node: _Node) -> None: prev = node.prev nxt = node.next if prev: prev.next = nxt if nxt: nxt.prev = prev node.prev = node.next = None # Aide interne : déplacer un nœud existant en tête (le plus récemment utilisé) def _move_to_head(self, node: _Node) -> None: self._remove_node(node) self._add_node(node) # Aide interne : extraire le nœud le moins récemment utilisé (juste avant tail) def _pop_tail(self) -> _Node: node = self.tail.prev if node is self.head: return None self._remove_node(node) return node def get(self, key: int) -> int: """Renvoie la valeur associée à key si présente ; sinon -1. L'accès marque la clé comme récemment utilisée. Temps moyen O(1). """ if self.capacity == 0: return -1 node = self.cache.get(key) if not node: return -1 # Déplacer le nœud accédé en tête (récent) self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: """Insère ou met à jour key avec value. Éjecte le LRU si la capacity est dépassée. Temps moyen O(1). """ if self.capacity == 0: return node = self.cache.get(key) if node: # Mettre à jour et marquer comme récemment utilisé node.value = value self._move_to_head(node) else: # Insérer un nouveau nœud new_node = _Node(key, value) self.cache[key] = new_node self._add_node(new_node) self.size += 1 if self.size > self.capacity: # Éjecter le nœud le moins récemment utilisé tail_node = self._pop_tail() if tail_node: del self.cache[tail_node.key] self.size -= 1 # Démonstration de l'implémentation avec la séquence de test donnée if __name__ == "__main__": cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # Attendu : 10 cache.put(3, 30) # Éjecte la clé 2 print(cache.get(2)) # Attendu : -1 cache.put(4, 40) # Éjecte la clé 1 print(cache.get(1)) # Attendu : -1 print(cache.get(3)) # Attendu : 30 print(cache.get(4)) # Attendu : 40
Resultat
Votes gagnants
3 / 3
Score moyen
Score total
Commentaire global
Ceci est une implémentation solide et bien structurée d'un cache LRU utilisant une table de hachage et une liste doublement chaînée. Le code produit correctement toutes les sorties attendues (10, -1, -1, 30, 40), gère les cas limites comme capacity 0, utilise des nœuds sentinelles pour simplifier les opérations sur la liste, et comprend des commentaires clairs tout au long. L'implémentation est propre, suit les conventions Python et atteint un temps moyen O(1) pour get et put. Note mineure : la méthode get utilise 'if not node' ce qui pourrait théoriquement poser problème si node était une valeur falsy, mais comme node est un objet cela convient en pratique. Le cas limite capacity=1 est géré implicitement et correctement. Dans l'ensemble, une réponse de haute qualité avec seulement de très mineures considérations stylistiques.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation produit correctement les cinq sorties attendues (10, -1, -1, 30, 40). Les opérations sur la liste doublement chaînée sont correctes, les nœuds sentinelles empêchent les bugs liés aux cas limites, et la logique d'éviction est saine. get et put sont en temps moyen O(1). Le cas limite capacity=0 est pris en charge. La vérification 'if not node' dans get est techniquement acceptable puisque node est un objet, mais utiliser 'if node is None' serait plus explicite.
Completude
Poids 20%Tous les composants requis sont présents : la classe _Node, la classe LRUCache avec get et put, des helpers internes pour la manipulation de la liste, des nœuds sentinelles, la gestion des cas limites pour capacity 0 et 1, la séquence de tests complète avec commentaires indiquant la sortie attendue, et un main guard. Rien d'important ne manque.
Qualite du code
Poids 20%Le code est clair, bien organisé et respecte les conventions Python. Les commentaires expliquent l'approche générale et chaque méthode. Les nœuds sentinelles sont un bon choix de conception. Les méthodes utilitaires sont bien nommées et à responsabilité unique. Des annotations de type sont utilisées. Remarque mineure : 'if not node' est légèrement moins explicite que 'if node is None', et les vérifications nulles dans _remove_node pour prev/nxt sont inutiles étant donné que les nœuds sentinelles existent toujours, mais ce sont des problèmes très mineurs.
Valeur pratique
Poids 15%L'implémentation est directement utilisable dans des scénarios réels. Elle gère capacity 0 de façon élégante, utilise une interface propre, et la conception avec des nœuds sentinelles la rend robuste. Le code est autonome et exécutable. Il pourrait être étendu facilement (par exemple, sécurité pour les threads, TTL). La démonstration montre clairement le comportement attendu.
Respect des consignes
Poids 10%Toutes les instructions sont suivies : ni OrderedDict ni functools.lru_cache n'ont été utilisés, table de hachage + liste doublement chaînée implémentées, classe nommée LRUCache avec l'interface correcte, séquence de tests incluse avec commentaires indiquant la sortie attendue, cas limites gérés, et les commentaires expliquent l'approche. Le code est complet et exécutable.
Score total
Commentaire global
Fournit une implémentation LRUCache correcte et exécutable utilisant un dict plus une liste doublement chaînée avec nœuds sentinelles, atteignant des opérations get/put en O(1) en moyenne et produisant les sorties attendues pour le test fourni. Inclut des commentaires clairs et gère la capacité 0 de manière gracieuse. Petits problèmes : _pop_tail est annotée pour retourner _Node mais peut renvoyer None ; certaines vérifications défensives dans _remove_node sont superflues compte tenu de l'invariant des sentinelles, mais ne sont pas nuisibles.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%Comportement LRU correct : get déplace les nœuds en position MRU, put met à jour/déplace les clés existantes et évince le LRU en cas de dépassement. La séquence de test fournie affichera 10, -1, -1, 30, 40 comme attendu. La capacité 0 est gérée avec get=-1 et put sans effet.
Completude
Poids 20%Inclut l'implémentation complète de la classe, les aides internes et la séquence de test exacte demandée. Les commentaires expliquent l'approche et les opérations clés. Les cas limites pour une capacité de 0 sont explicitement traités ; la capacité 1 fonctionne naturellement via la logique d'éviction.
Qualite du code
Poids 20%Le code est propre, lisible et bien structuré avec des nœuds sentinelles pour simplifier les opérations sur la liste. Petites remarques de qualité : l'annotation de retour de _pop_tail ne correspond pas au fait qu'elle peut retourner None, et certaines vérifications dans _remove_node sont redondantes avec l'invariant des sentinelles.
Valeur pratique
Poids 15%Une implémentation de référence pratique : opérations en O(1), évite les bibliothèques interdites et est facile à adapter. Le code de démonstration est exécutable tel quel.
Respect des consignes
Poids 10%Suit toutes les instructions : pas d'OrderedDict/functools, utilise un hashmap + une liste doublement chaînée, inclut des commentaires explicatifs, gère les cas limites (notamment la capacité 0) et fournit un code exécutable complet avec le test spécifié.
Score total
Commentaire global
Ceci est une réponse exceptionnelle qui fournit une implémentation d'un cache LRU de qualité didactique. Le code est correct, efficace et remarquablement bien structuré, utilisant la technique sophistiquée des nœuds sentinelles pour simplifier la logique de la liste doublement chaînée. Il respecte parfaitement toutes les contraintes, inclut d'excellents commentaires, gère proprement les cas limites et fournit le cas de test exécutable requis. Il sert de réponse modèle pour cette tâche.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation est parfaitement correcte. La logique des opérations `get` et `put` maintient correctement l'ordre least-recently-used et respecte la contrainte de capacité. La séquence de test fournie produit exactement la sortie attendue. La complexité temporelle moyenne O(1) pour les deux opérations est atteinte grâce à la combinaison d'une table de hachage et d'une liste doublement chaînée. Les cas limites, comme une capacité de 0, sont gérés correctement.
Completude
Poids 20%La soumission est entièrement complète. Elle inclut la classe `LRUCache`, la classe privée d'aide `_Node`, et le bloc de démonstration complet et exécutable (`if __name__ == "__main__":`) comme demandé. Tous les composants requis par l'énoncé ont été fournis.
Qualite du code
Poids 20%La qualité du code est exceptionnelle. L'utilisation de méthodes d'aide privées pour la manipulation des nœuds (`_add_node`, `_remove_node`, etc.) rend les méthodes principales `get` et `put` claires et lisibles. L'implémentation des nœuds sentinelles head et tail est un motif sophistiqué et efficace qui élimine le besoin de vérifications de cas limites dans la logique de manipulation de la liste. Les commentaires sont clairs, concis et expliquent à la fois le quoi et le pourquoi de l'implémentation. C'est une solution de niveau professionnel.
Valeur pratique
Poids 15%La réponse a une grande valeur pratique et pédagogique. C'est une implémentation classique et complète d'un algorithme de mise en cache fondamental largement utilisé en conception de systèmes. Ce code sert de référence excellente pour quiconque a besoin de comprendre ou d'implémenter un cache LRU et constitue une solution canonique à un problème d'entretien logiciel très courant.
Respect des consignes
Poids 10%La réponse suit méticuleusement chaque instruction de l'énoncé. Elle implémente correctement la classe `LRUCache` en utilisant une table de hachage et une liste doublement chaînée personnalisée, tout en évitant explicitement les éléments interdits `collections.OrderedDict` et `functools.lru_cache`. Le code est exécutable, commenté et inclut le cas de test spécifié.