Come migliorare l'efficienza

Question

definisco il metodo ricorsivo che genera i figli :
        inizializzo un primo indice = 0
        inizializzo un secondo indice = lunghezza del valore dell'oggetto - 1
        finché il valore del primo indice è minore della lunghezza del valore dell'oggetto-1 allora:
            se l'elemento alla posizione del primo indice è uguale all'elemento alla posizione del secondo indice allora:
                inizializzo una copia del valore dell'oggetto
                elimino l'elemento nella posizione del secondo indice
                elimino l'elemento nella posizione del primo indice
                creo un nuovo oggetto Tree avente valore la copia modificata del valore dell'oggetto che sto analizzando
                aggiungo questo nuovo oggetto ai figli dell'oggetto che sto analizzando
                chiamo ricorsivamente questo metodo sull'oggetto appena creato
            aggiorno il secondo indice sottraendogli 1
            se il secondo indice è uguale al primo allora:
                il secondo indice ritorna al valore iniziale, ovvero lunghezza del valore dell'oggetto - 1
                e aggiorno il primo indice sommandogli 1       

Salve, con questo metodo riesco a superare tutti i test tranne gli ultimi 4. Ho provato diverse soluzioni, non riesco a capire come renderlo più efficiente. Quello che vedete è il metodo con cui genero i risultati possibili della riduzione della stringa che viene passata in input nella funzione ex1(s), chiamo il metodo split() sulla stringa e poi la passo come valore di un nuovo oggetto Tree e da questo genero i risultati possibili della riduzione. Ogni oggetto Tree ha due attributi: self.value = #lista di caratteri e self.children = # lista dei figli. Il metodo AddChild() aggiunge un figlio all'oggetto sul quale è stato chiamato usando il metodo append().

Answer 1

Se parli dell'HW7, è abbastanza difficile passare gli ultimi test in tempo senza queste due accortezze:

• Ti puoi salvare gli stati già visti, che tanto portano alle stesse soluzioni
• Puoi eliminare fin da subito i numeri che appaiono un numero pari di volte

Comments

Grazie per aver risposto. Il primo punto non sarebbe considerato caching?

---

No, è ottimizzazione.

Quello che è proibito è fare caching x fregare il calcolo dei tempi di esecuzione (efficienza).