Programma Les 55 van 148 · Snelheid zonder de cache
Snelheid zonder de cache

Twee pointers, geen tabel

Waarom dit ertoe doet "Vind twee dingen die samen X vormen" heeft een bekend antwoord: zet alles in een set en zoek de partner op. Het is snel, en het heeft een kopie van alle data nodig. Als de data gesorteerd is, heb je bijna geen geheugen nodig.

A gift service verkoopt bundels van twee verschillende producten voor een vaste bundelprijs. De productprijslijst is gesorteerd, heeft geen herhalingen en staat op een ingebed apparaat met heel weinig vrij geheugen. Voor een bundelprijs heb je het aantal productparen nodig waarvan de prijzen precies optellen tot die prijs.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Jij bent aan de beurt

Schrijf count_pairs(tape, target). tape is een Tape van gehele prijzen, gesorteerd in oplopende volgorde, zonder herhalingen. Geef terug hoeveel paren van twee verschillende items precies optellen tot target (elk paar één keer geteld). Budgets: voor 20.000 items gelezen met maximaal 60.000 waarden, en gebruik maximaal 16.000 bytes aan werkgeheugen terwijl je functie draait (gemeten met tracemalloc; een set of lijst van de 20.000 prijzen is meer dan 150.000 bytes). len(tape) is gratis.

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.