Programme Leçon 55 sur 148 · La vitesse sans le cache
La vitesse sans le cache

Deux pointeurs, pas de table

Pourquoi c'est important « Trouve deux choses dont la somme fait X » a une réponse célèbre : mets tout dans un set et cherche le partenaire. C'est rapide, et ça demande une copie de toutes les données. Quand les données sont triées, tu n'as besoin de presque aucune mémoire.

Un service de cadeaux vend des lots de deux produits différents à un prix de lot fixe. La liste des prix des produits est triée, n'a pas de répétitions, et se trouve sur un appareil embarqué avec très peu de mémoire libre. Pour un prix de lot, il te faut le nombre de paires de produits dont les prix font exactement ce prix.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
À ton tour

Écris count_pairs(tape, target). tape est une Tape de prix entiers, triés par ordre croissant, sans répétitions. Renvoie combien de paires de deux éléments différents font exactement target (chaque paire comptée une fois). Budgets : pour 20 000 éléments, lis au plus 60 000 valeurs, et utilise au plus 16 000 octets de mémoire de travail pendant l'exécution de ta fonction (mesurés avec tracemalloc ; un set ou une liste des 20 000 prix dépasse 150 000 octets). 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.