Programme Leçon 14 sur 148 · Les règles du duel
Les règles du duel

Ton premier duel : le disque lent

Pourquoi c'est important La première réponse à « compter des choses dans un intervalle » est de regarder chaque chose. Ça va jusqu'à ce que les données soient grosses et que les lire coûte de l'argent ou du temps. Ici, c'est le cas.

Un capteur enregistre des événements sous forme d'horodatages en secondes entières, déjà triés. Le journal est sur un disque lent et facturé : chaque valeur que tu lis est payée. Des analystes t'envoient un lot de fenêtres de temps et veulent savoir combien d'événements tombent dans chacune.

Résous-le avant de chercher quoi que ce soit. Quand tu réussis, tu verras ce qu'un assistant IA aurait le plus probablement écrit, et le chemin d'un expert, côte à côte.

Les données

from creative.budget import Tape
tape = Tape([3, 7, 7, 12, 40])   # sorted timestamps, every read counted
queries = [(0, 8), (7, 13)]       # windows: start included, end excluded
# window_counts(tape, queries) -> [3, 3]
À ton tour

Écris window_counts(tape, queries). tape est une Tape d'horodatages entiers triés (répétitions possibles). queries est une liste de paires (start, end). Renvoie une liste avec, pour chaque fenêtre, combien d'horodatages t vérifient start <= t < end. Budget : avec 100 000 événements et 1 000 fenêtres, tu peux lire au plus 60 000 valeurs de la tape. len(tape) est gratuit.

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.