Rimuovere multipli di 3 da una lista

Question

Rimuovere gli elementi da una lista che sono multipli di 3 senza creare una nuova lista. La soluzione sembra banale: controllare ogni elemento della lista e se elemento%3 è uguale a zero allora lo si toglie dalla lista con l'apposito metodo remove(elemento). Il problema è che quando do in input alcune liste, la funzione non riesce a togliere tutti i multipli di 3, ma solo alcuni, cosa sto sbagliando?

Answer 1

Come suggerisce il professore il problema è che stai effettuando contemporaneamente operazioni di lettura e di scrittura su una stessa lista, portandoti ad ottenere dei risultati sbagliati.

Ogni volta che utilizzi la funzione delete (del <elemento>) su una lista, Python procede eliminando il riferimento all'elemento specificato ed aggiornando tutti gli indici in modo tale da non avere "buchi" da qualche parte.

Ti faccio un esempio al volo: nella lista L = [10, 20, 30, 40] l'indice dell'elemento 30 è 2 (ricordati di iniziare a contare da zero), ovvero L[2] → 30; tuttavia se elimini il primo elemento della lista tutti gli indici dei valori successivi verranno aggiornati in modo tale che non vi siano celle vuote all'interno della lista. Se adesso andiamo a stampare il valore con indice 2 non sarà più 30 come prima ma L[2] → 40 [tutti gli indici sono slittati di -1].

Questo è probabilmente il problema del tuo algoritmo: se dall'interno di un ciclo for (o iterando in altro modo) vai a rimuovere un elemento dalla stessa lista che stai leggendo otterrai che per ogni rimozione il ciclo ignorerà un valore della lista in quanto non è consapevole che i suoi indici sono stati aggiornati per far fronte all'eliminazione di un valore (ci sono anche buone probabilità che venga generato un IndexError). In altre parole ti perdi dei pezzi per la via.

Per risolvere il problema senza creare una nuova lista dovresti creare un algoritmo che sappia adattarsi ad eventuali rimozioni effettuate sulla lista. Tuttavia questo metodo presenta alcuni problemi:

• è controintuitivo (e poco pythonico);
• aggiunge complessità al programma;
• rende più facile la comparsa involontaria di errori e bug.

Per non complicarti inutilmente la vita ti consiglio di crearti una nuova lista (magari utilizzando una list comprehension) dove inserire unicamente i valori validi piuttosto che essere taccagni con la memoria. Al momento non ci dobbiamo preoccupare troppo della complessità spaziale dei nostri programmini, quindi tanto vale scrivere del codice chiaro e semplice (anche se leggermente più costoso) per risolvere i nostri problemi.

Spero di esserti stato d'aiuto!   

Answer 2

immagino che tu stia modificando direttamente la lista su cui iteri .... ahia ahia ahia!!!

Answer 3

Non hai specificato in che modo quest'operazione deve essere effettuata... for.. while.. io ti indico quella che secondo me è la più adatta per la situazione. Spiegarlo è più difficile che farlo, quindi ti aiuto con dello pseudocodice.

indice = 0

finché indice < len(lista)
    if lista[indice] % 3 == 0:
         lista.remove(lista[indice]) # oppure: del lista[indice]
   else:
         incremento indice di 1

Ti spiego brevemento come funziona: itero la lista dal primo all'ultimo elemento. Se mi trovo nel caso in cui ho un elemento divisibile per 3, lo elimino dalla lista ma LASCIO INALTERATO l'indice, altrimenti lo incremento di uno. Perché questo? Perché se io elimino l'elemento ed incremento lo stesso l'indice ricavo che ho l'indice che è superiore alla lunghezza della lista e questo, banalmente, mi genera un errore di overflow.

Comments

Insisto, non scrivete codice ma solo pseudocodice, plis

Answer 4

Suggerimento
Ogni volta che elimini un elemento i seguenti si muovono ed è complicato andarci sopra... Quali NON si muovono?

Comments

risposta ... i primi
potresti quindi andare a ritroso ...

Answer 5

Questo problema si verifica in quanto tenti di iterare  per un certo numero K  di volte che, dal momento in cui viene eliminato almeno un elemento, risulta maggiore della lunghezza della lista. K  viene dichiarato all'inizio del ciclo e non cambia valore durante le iterazioni! Nel momento in cui viene eliminato un elemento, la capienza della lista si riduce, ma  K  resta fisso. Con il programma che hai creato, tenti di "ciclare" su elementi che non ci sono più ed è inevitabile che ti compaia un messaggio del tipo "list index out of range".

Per non creare una nuova lista e non avere quel tipo di problemi dovresti iterare "a rovescio", partendo cioè dall'ultimo elemento della lista. 

Answer 6

Breve panoramica:

Potresti inserire una 'funzione anonima' come argomento della funzione 'filter'  specificando che l'elemento deve avere un resto diverso da 0 quando diviso per 3. Il tutto trasformato in lista da un costruttore di sequenza.

Spiegazione:

La funzione filter ha come primo parametro una funzione (che è appunto il criterio usato per il filtro) e come secondo parametro l'oggetto iterabile (come ad esempio la lista da processare).
Soffermandoci sul primo parametro, potresti usare la funzione anonima (parola chiave 'lambda' per intenderci) nella quale specifichi che ogni elemento della lista processata, diviso per 3 deve avere resto diverso da 0. In questo modo otterrai direttamente gli elementi della lista che non sono divisibili per  3.

Considerazioni:
CASO 1: Ora, Se ti è stato chiesto di modificare la lista originale:
  potresti creare una funzione avente come unico parametro l'iterabile da processare e,
  nel corpo della funzione, poni l'uguaglianza tra l'iterabile processato e il filtro di cui sopra. (iterabile = filtro applicato alla lista)
  ritorni l'iterabile così modificato.

CASO 2:Se ti è stato chiesto di NON modificare la lista originale:
  potresti creare una funzione avente come unico parametro l'iterabile da processare e,
  ritorni direttamente il filtro applicato all'iterabile (inserito in un costruttore di sequenza 'list')

Comments

ho integrato la risposta precedente per maggiore comprensione.