Do you need any help?

Una lista come è rappresentata su disco? Con un indice all'inizio?

m
massimocoppola (950 points)
1 15 20
asked Nov 18, 2020 in Programmare in Python by massimocoppola (950 points)
edited Nov 19, 2020 by andrea.sterbini
a=["a"]*10000

aa=["aa"*10000]*10000

aaa=["a"*1000000]*10000

%timeit a.reverse()
4.39 µs ± 12.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit aa.reverse()
4.39 µs ± 23.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit aaa.reverse()
4.36 µs ± 85.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each

Quindi l'operazione di reverse interessa il solo indice?

EDIT: ho spostato il post nel forum italiano [Sterbini]
177 views

2 Answers

S
Silktrader (2550 points)
1 6 16
answered Nov 18, 2020 by Silktrader (2,550 points)
edited Nov 18, 2020 by Silktrader

Your three lists have exactly the same length. It's to be expected that reverse() takes the same amount of time. The strings within "aa" are longer than in "a", but the containing lists are all 10000.

I seem to remember that Professor Di Ciccio explained how most Python implementations handle lists as arrays of pointers (fixed length), expanding or contracting as needed.

You can check CPython's implementation of the "reverse" function, which illustrates how it's an O(n) operation, taking longer when lists are lengthier:

https://github.com/python/cpython/blob/5b96370030707b68e8a5b787e933654297ddbc98/Objects/listobject.c

/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
static void reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}
m
massimocoppola (950 points)
1 15 20
commented Nov 18, 2020 by massimocoppola (950 points)
grazie mille. ok quindi una lista è un indice (array of pointers si può tradurre con indice) ed i dati sono nei punti del disco indicati dall'indice. quello nel link (di cui non ho capito nulla) è il codice con cui è scritto python stesso?
S
Silktrader (2550 points)
1 6 16
commented Nov 18, 2020 by Silktrader (2,550 points)

Il link porta al codice relativo alle liste di CPython, una delle implementazioni di Python — la più comune, di riferimento, distribuita con Anaconda o su Python.org. Credo che Python, come linguaggio, esista a prescindere dalle sue implementazioni; C con CPython, Java con Jython, C# con IronPython, etc.. Insomma Python non è "scritto" in C.

Riguardo la terminologia esatta ("indice") dovresti attendere la smentita o conferma di una persona più competente di me. I puntatori quasi certamente non fanno riferimento a "punti del disco", ma ad indirizzi di memoria.

m
massimocoppola (950 points)
1 15 20
commented Nov 18, 2020 by massimocoppola (950 points)
si, hai ragione, è un indirizzo in memoria.

non mi sono accorto che sto scrivendo nel forum del corso in inglese. scusate, grazie mille
G
Giuseppe01 (1500 points)
0 0 10
answered Nov 19, 2020 by Giuseppe01 (1,500 points)
edited Nov 19, 2020 by Giuseppe01

Quando pensi ad oggetti all'interno del codice, che siano semplici variabili o liste etc, devi immaginarti che tutti questi oggetti vivono, e vengono manipolati, in memoria, non su disco.

Come è stato già detto nella risposta precedente, di solito una lista è organizzata come una sequenza di indirizzi di memoria (puntatori). Se volessimo trovare un paragone nella vita reale è come se gli elementi della lista fossero 100000 abitazioni e la lista in sé fosse semplicemente un'agenda contenente i 100000 indirizzi di queste abitazioni.

La funzione reverse non fa altro che invertire l'ordine degli indirizzi nella pagina dell'agenda, pertanto, dopo tale operazione, troverai in cima alla pagina l'indirizzo che prima era l'ultimo, come secondo quello che prima era il penultimo, e così via.

Quindi come puoi vedere non ha importanza che le abitazioni siano dei monolocali o delle ville, la tua lista (ammesso che sia stata allocata dinamicamente come nell'implementazione in CPython) è solo la lista di indirizzi.

Edit: mi scuso per aver dato una spiegazione superficiale (dovevo ancora svegliarmi), quello che ho scritto nelle due righe sopra non è accurato. Cerco di trovare il tempo per scrivere un commento corretto più tardi, nel frattempo sarò felice di leggere interventi altrui. :)

Quanto alla terminologia, c'è da stare attenti al tipo di contenitore utilizzato ma in generale credo sia più corretto dire che una sequenza ordinata di elementi può essere identificata con il puntatore (cioè l'indirizzo di memoria) del suo primo elemento. A questo punto diventa facile accedere via indice perché gli indirizzi sono comunque degli interi, quindi per trovare un determinato elemento ti basta fare 'indirizzo + indice'.
Es:

  • 1° elemento = indirizzo + 0
  • 2° elemento = indirizzo + 1
  • etc

Tale aritmetica viene ovviamente mascherata dagli operatori della lista, non facciamo questa operazione a mano in Python.