Programme Leçon 27 sur 148 · Utiliser l'IA pour comprendre
Utiliser l'IA pour comprendre

Jumeau sans IA : l'anneau de hachage

Pourquoi c'est important Le journal circulaire de La fixation sur toi-même avait une seule idée au cœur. La revoici, dans un système que tu pourrais vraiment construire, avec le tuteur éteint.

Le tuteur est éteint pour ce problème. Résous-le toi-même.

Un cluster de cache répartit les clés sur des serveurs par hachage cohérent. Chaque serveur possède des positions sur un anneau de nombres entiers allant de 0 à environ deux milliards. Une clé est hachée en un nombre, et elle appartient à la première position de nœud égale ou supérieure à ce nombre, en tournant autour de l'anneau : au-delà de la plus grande position, on repart à la plus petite.

Les positions des nœuds sont stockées triées dans une table partagée, mais la table est un tampon circulaire : elle commence là où le dernier écrivain s'est arrêté. Chaque lecture de la table est un aller-retour réseau, donc les lectures sont comptées.

Les données

from creative.budget import Tape
ring = Tape([700, 900, 100, 300])   # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]
À ton tour

Écris owners(ring, hashes). ring est une Tape de positions de nœuds distinctes, triées mais peut-être décalées (stockées à partir de n'importe quel point de départ, éventuellement 0). Elle contient au moins un nœud. Pour chaque hachage h, renvoie la plus petite position >= h ; s'il n'y en a aucune, renvoie la plus petite position de toutes. Budget : avec 100 000 nœuds et 200 hachages, tu peux lire au plus 20 000 valeurs. len(ring) est gratuit.

IA désactivée : pas de tuteur, d'indices ou de solution détaillée pour celui-ci. Ta propre réflexion uniquement.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.