Programma Lezione 55 di 148 · Velocità senza cache
Velocità senza cache

Due puntatori, nessuna tabella

Perché è importante "Trova due cose che sommate fanno X" ha una risposta famosa: metti tutto in un set e cerca il partner. È veloce, e richiede una copia di tutti i dati. Quando i dati sono ordinati, non ti serve quasi nessuna memoria.

Un servizio regali vende pacchetti di due prodotti diversi a un prezzo fisso del pacchetto. Il listino prezzi dei prodotti è ordinato, non ha ripetizioni, e sta su un dispositivo embedded con pochissima memoria libera. Per un prezzo del pacchetto, ti serve il numero di coppie di prodotti i cui prezzi sommati fanno esattamente quel prezzo.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Tocca a te

Scrivi count_pairs(tape, target). tape è un Tape di prezzi interi, in ordine crescente, senza ripetizioni. Restituisci quante coppie di due elementi diversi sommate fanno esattamente target (ogni coppia contata una volta). Budget: per 20,000 elementi leggi al massimo 60,000 valori, e usa al massimo 16,000 byte di memoria di lavoro mentre la tua funzione gira (misurati con tracemalloc; un set o una lista dei 20,000 prezzi supera i 150,000 byte). len(tape) è gratis.

Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione

Questo esercizio si apre presto

Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.