Dizionario vs Lista

Question

Come da titolo, qual è più efficiente tra i due? Il contesto è il seguente :

cercare un valore dato una chiave, nel caso del dizionario, e un indice, nel caso della lista.

Mi chiedevo se entrambe le operazioni fossero in O(1) e soprattutto se il dizionario fosse più pesante da gestire e tenere in memoria.

Answer 1

Bhe in realtà sono uguali, la lista è praticamente un dizionario, solo che i keys sono sempre 0,1,2,3..... Quindi se già devi avere un dizionario con le chiavi così ti consiglio una lista, anche perchè provando un po' con %timeit mi sembra un po' più veloce la lista, ma veramente di pochi ns. Ma se ti serve trovare per esempio gli indici degli elementi di una lista, puoi fare il contrario nel dizionario, mettendo come chiavi gli elementi della lista e come valori gli indici.

Answer 2

Mi ero posto anche io questa domanda. Con dei test fatti con timeit ho riscontrato non ci siano differenze in termini di tempo tra i due casi.

Comments

Quindi con le liste passare tutte e 16 i test è possibile, ma bisogna fare un ottimo codice immagino

---

In realtà farlo usando solo liste è praticamente impossibile dato che già solo rimuovere i piloti dalla lista ti manderebbe in timeout sul test con tutte le eliminazioni.
(E in questo non sto considerando che il problema principale in realtà è la lentezza della ricerca della posizione del pilota nella lista)

---

Io l'ho fatto usando solo le liste e passa ne 15. l'unico che non riesco a passare è il test_1_esempio5 (istanza da 1500) perchè in questo test la lista degli eventi supera il milione, quindi anche utilizzando un algoritmo in O(n) devo comunque ciclare una lista da un milione.