Ottimizzazione del calcolo di c(AB) e c(BA)

Question

Ciao ragazzi. Premesso che supero agevolmente i test e che il programma ha una buona complessità media, l'efficienza è abbassata, non eccessivamente, ma fastidiosamente,
proprio dal calcolo di c(BA) e c(AB), che secondo i test di profilazione mi portano via la maggior parte del tempo.

i problemi sono due:
    -innanzitutto, nonostante abbia sentito parlare di un calcolo unitario di c(BA) e c(AB) (effettivamente devono essere sommati, quindi andrebbe bene), non saprei come farlo.
    
    -il mio metodo è probabilmente lento: chiamo due volte la funzione, prima su A e B, poi su B e A.

Passiamo a quello che effettivamente faccio per calcolare c(AB)

passo alla funzione la riga della matrice (A), l'altra riga (B) e tau
inizializzo un contatore
scorro A
    se trovo in A[i] un '1' (devo controllare se, nella sottosequenza che va da B[i] fino a B[i-tau] incontro un '1')
        inizializzo un indice j= i
        con un ciclo while, pongo come condizione che j sia >= 0 (cioè che la slice non "sbordi" fuori dalla riga, altrimenti la slice sarà vuota di default) e che i-j <= tau (cioè che la slice sia lunga al massimo tau)
            se c'è un '1' nella slice di B che va da j a i+1
                aumenta il contatore
                esco dal while e vado al prossimo elemento di A
            altrimenti riduco di 1 l'indice j
    dopo aver controllato tutta la riga A, ritorno il contatore (cioè c(AB))

Qualcuno mi da una dritta?

Answer 1

C'è un modo che ti permette di essere sicuro di non ottenere lista vuota nonostante sbordi dalla lista.Applicando un metodo delle liste(banale,visto sin dalle prime lezioni) sulle liste ti permetterebbe, con le dovute accortezze , di semplificare le operazioni con le slice. Come sai, anche se hai una lista di 5 elementi, se chiami la slice da 4 a 1000 ti ritorna cmq solo l'ultimo elemento.

Comments

grazie, tempo ridotto del 25% :D

---

Grande!mi fa piacere esserti stato d'aiuto :D