[Python] Assegnamento e liste

[enrico franchi]

2012/1/18 Giuseppe Amato <giuamato a gmail.com>:

>> Sempre tenendo in considerazione il costo computazione di rimuovere
>> elementi in mezzo o in testa ad una lista python ordinaria.
>>
>
> Quindi c'è differenza in termini di costo computazione tra:
>
> lista=lista[:-1]
> e
> lista.pop()
>
> ?
> Non mi ero mai posto il problema, ma immaginavo che le due istruzioni
> fossero equivalenti.
> A meno che il pop oltre la riassegnazione della lista effettui anche
> l'eliminazione e lo spostamento degli altri elementi.
> Mi sai dare qualche risorsa?

Ho detto una cosa diversa, io. Ho detto che rimuovere in testa o in
mezzo costa di piu' che rimuovere in coda. Sia con lo slicing che con
pop puoi fare tutte e tre le cose. pop prende un "indice" che consente
di rimuovere un elemento diverso dall'ultimo.

Comunque si, il costo e' diverso.

In [26]: np.average(timeit.repeat(setup='l = range(1000000)',
stmt='l.pop()', repeat=10, number=10000))

Out[26]: 0.0021610975265502928

In [27]: np.average(timeit.repeat(setup='l = range(1000000)',
stmt='del l[-1]', repeat=10, number=10000))
Out[27]: 0.00093293190002441406

In [33]: np.average(timeit.repeat(setup='l = range(1000000)', stmt='l
= l[:-1]', repeat=10, number=10000))

... sta ancora calcolando ...


D'altra parte sono tre operazioni diverse. Anche dal punto di vista della vm.
Il problema di l = l[:-1] e' che crei tutte le volte una nuova lista e
che di conseguenza *ovviamente* paghi il costo.  Per dire... e' ordini
di grandezza piu' lento (in particolare e' O(n)).


In [1]: from dis import dis

In [2]: def f1(lst): lst = lst[:-1]
   ...:

In [3]: def f2(lst): lst.pop()
   ...:

In [4]: def f3(lst): del lst[-1]
   ...:

In [5]: dis(f1)
  1           0 LOAD_FAST                0 (lst)
              3 LOAD_CONST               1 (-1)
              6 SLICE+2
              7 STORE_FAST               0 (lst)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

In [6]: dis(f2)
  1           0 LOAD_FAST                0 (lst)
              3 LOAD_ATTR                0 (pop)
              6 CALL_FUNCTION            0
              9 POP_TOP
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

In [7]: dis(f3)
  1           0 LOAD_FAST                0 (lst)
              3 LOAD_CONST               1 (-1)
              6 DELETE_SUBSCR
              7 LOAD_CONST               0 (None)
             10 RETURN_VALUE

Lasciando perdere il caso f1 (dove essenzialmente il tutto e'
asintoticamente diverso), per f2 e per f3 "essenzialmente" il codice
generato e' "simile".

  1           0 LOAD_FAST                0 (lst)
              3 LOAD_ATTR                0 (pop)
              6 CALL_FUNCTION            0

  1           0 LOAD_FAST                0 (lst)
              3 LOAD_CONST               1 (-1)
              6 DELETE_SUBSCR

Una chiamata di funzione e' un pochetto piu' lenta (visto che deve
istituire uno stack frame, ritornare, etc etc etc) di chiamare
direttamente un opcode. Ha senso. Suppongo (ma non sono un'esperto
degli internals che invece LOAD_ATTR e LOAD_CONST siano "grosso modo"
equivalenti -- ma sempre scommettendo, direi che LOAD_CONST e' piu'
veloce).

Comunque come vedi uno dei due e' il doppio piu' veloce, ma su
quantita' di tempo irrisorie. Direi che la cosa e' irrilevante in
generale.

Beh... senti, il terzo benchmark non ha ancora finito nel tempo che io
ho scritto questo post... diciamo che e' un sacco piu' lento e
basta... ;)

-- 
.
..: -enrico-