[Python] Dubbio sull'uso delle liste...

[Enrico Franchi]

On Jun 22, 2013, at 11:42 AM, Nadir Sampaoli <nadirsampaoli a gmail.com> wrote:
> 
> A questo punto ho un po' di domande.
>  - La complessità non dipende dall'implementazione piuttosto che dall'interfaccia?

Si. Ovviamente dipende dall'implementazione.
Il problema e' che "list" e' sia una struttura dati astratta, sia, soprattutto, una famiglia di implementazioni.
Praticamente tutto il mondo funzionale quando gli dici "lista" ha in mente una cosa ben precisa
(ovvero una lista concatenata). 

Ovviamente chiamarla list non e' scorretto. Semplicemente un bel po' di persone si aspetteranno
una cosa che non e' quella ottengono.


>  - Il concetto di lista di per sè non è limitato ad una struttura che espone una sequenza ordinata di elementi?

Si, ma e' anche il nome di una popolarissima struttura dati concreta. Un po' di ambiguita' c'e'.

>  - Che (tanto per dire) rimuovere un elemento abbia complessità media O(N) invece che O(1) perchè incapsula
> un'array invece di una linked list non dovrebbe essere disgiunto dall'«interfaccia» lista?

Questa e' una questione (relativamente) complessa. Metti conto che il concetto di "interfaccia" viene dopo
quello di abstract data type. Mentre un'interfaccia non necessariamente si porta dietro il concetto di costo
computazionale, un abstract data type in generale si.

Per esempio mi verrebbe molto strano pensare ad uno stack che mi fa il pop in O(n). Anche perche' quando poi
ragiono su un'algoritmo, se non avessi idea sulle complessita' tipiche degli abstract data type che uso, farei fatica
anche a calcolare il costo dell'algoritmo. O meglio, calcolarlo, potrei esprimerlo in termini di costo astratto – per 
esempio se parli di heap, l'efficienza puo' variare parecchio a seconda dell'implementazione, ma grosso modo
sai almeno quali operazioni sono sublineari e quali no –. Ma comunque sarebbe scomodo.


Aggiungo che tutta questa recente mania della programmazione ad oggetti ha veramente complicato un sacco
di cose...

-- 
Dr. Enrico Franchi

Università di Parma - Dipartimento di Ingegneria dell'Informazione
Via G.P. Usberti 181/a I-43124 Parma ITALY