Scelta tra Liste ed Alberi

di
fra95ncy
il
10 risposte
F
fra95ncy
Pochi posts
Iscritto da
mag, 2015
Messaggi:
9

Scelta tra Liste ed Alberi

Salve, ho da poco completato il codice di un "database" scritto in linguaggio C che gestisce con la struttura dati Lista l'inserimento, la rimozione, la ricerca, l'ordinamento e la stampa degli elementi della lista stessa. A questo punto vorrei considerare la complessità asintotica del codice rispetto a quella che avrebbe avuto utilizzando alberi binari rosso-neri.
La complessità asintotica di inserimento(in coda), cancellazione e ricerca su liste è la seguente: O(1), O(n), O(n);
se avessi usato alberi binari rossi-neri sarebbe stata O(log n) per ognuna delle tre operazioni suddette.
La mia domanda è la seguente: oltre al fatto che gli alberi rosso-neri sono più "difficili" da implementare e gestire, c'è qualche altra ragione che giustificherebbe l'uso delle liste rispetto agli alberi binari, nonostante l'esecuzione sia più lenta [O(n) > O(log n)]?

10 Risposte

  • +m+
    +m+
    Molto attivo
    Iscritto da
    gen, 2016
    Messaggi:
    712

    Re: Scelta tra Liste ed Alberi

    Certo, e sono i k, cioè i moltiplicatori della complessità.
    Se supponi n sufficientemente piccolo vedrai che la velocità delle liste è di gran lunga superiore a quella degli alberi, perchè la valutazione asintotica è sinonimo di "sufficientemente grande".
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Scelta tra Liste ed Alberi

    fra95ncy ha scritto:

    La mia domanda è la seguente: oltre al fatto che gli alberi rosso-neri sono più "difficili" da implementare e gestire, c'è qualche altra ragione che giustificherebbe l'uso delle liste rispetto agli alberi binari, nonostante l'esecuzione sia più lenta [O(n) > O(log n)]?
    In qualsiasi lavoro di tipo progettuale non esiste il concetto di migliore, inteso come valore assoluto. Per cui la risposta a questa domanda è: dipende da che cosa vuoi realizzare! Ad ogni modo, sì, ci sono ragioni che giustificano l'uso della lista rispetto agli alberi binari.

    L'uso delle liste è molto più economico da un punto di vista implementativo e computazionale per svariati usi, ad esempio per gestire semplice coda, uno stack, ecc... è assolutamente svantaggioso per esempio per le ricerche. Quindi l'uso delle liste è giustificato in alcuni ambiti e ingiustificato in altri.

    Per farti comprendere bene qual è la differenza tra O(n) e O(log n), prova a disegnare con il computer e sovrapporre i grafici delle due funzioni:
    y=x, e y=ln x,
    ti renderai conto subito che se i tuoi dati si allontanano dall'origine degli assi verso numeri grandi il differenziale tra due funzioni è molto grande, ciò rende inutile una lista per alcune operazioni.
  • +m+
    +m+
    Molto attivo
    Iscritto da
    gen, 2016
    Messaggi:
    712

    Re: Scelta tra Liste ed Alberi

    La spiegazione non mi pare un granchè centrata.
    Il punto, come già scritto, che il concetto di complessità ASINTOTICA significa "per n grandi", e che si tratta di O, non della formula precisa.

    Per capirci supponiamo l'algoritmo 1 ha complessità effettiva (cioè non "ordine di") 3*n (quindi O(n)), e l'algoritmo 2 ha complessita 1000*log(n), quindi O(log(n)), allora l'algoritmo 1 è PIU' VELOCE dell'algoritmo 2 per n<1000.

    Se il dominio del mio problema è tale per cui SO GIA' che n varrà, poniamo, al massimo 500, allora l'algoritmo 1 è meglio.

    Come vedi occorre ragionare un pochino, ma tipicamente è colpa di chi insegna questi argomenti basilari raffazzonatamente, senza far ragionare gli studenti.

    PS
    Ovviamente non mi sto preoccupando di definire cosa significhi "complessità" e "più veloce", uso termini terra-terra.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5884

    Re: Scelta tra Liste ed Alberi

    fra95ncy ha scritto:

    ...
    La complessità asintotica di inserimento(in coda), cancellazione e ricerca su liste è la seguente: O(1), O(n), O(n);
    ..
    Ni, la complessita' assintontica per l'inserimento in coda dipende dall'implementazione della lista: se e' una lista semplice (solo il puntatore in avanti) e' O(n), anzi, proprio 'n'!

    Ora, le considerazioni su quale algoritmo usare si fa con n GRANDE, non con n piccolo: 100, 1000, 1.000.000.

    Ad esempio, considera la differenza tra 1.000.000 e 13 (list, albero bilanciato): mi sembra evidente quale algoritmo conviene usare, anche se e' piu' complesso da implementare.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5884

    Re: Scelta tra Liste ed Alberi

    wrugg25 ha scritto:

    Questo è un dettaglio che va sempre evidenziato:

    migliorabile ha scritto:

    Ora, le considerazioni su quale algoritmo usare si fa con n GRANDE, non con n piccolo: 100, 1000, 1.000.000.
    Considerando piccolo il parametro caratteristico dell'ordine di complessità, di fatto qualsiasi valutazione ha poco senso: esclusi casi particolari, praticamente ogni macchina sarà in grado di eseguire qualsiasi algoritmo con scarti di prestazione tutto sommato trascurabili.

    Aggiungo inoltre un dettaglio che, a mio avviso, non va mai dimenticato: la valutazione della classe di complessità è, per definizione, asintotica e basata sul caso peggiore, e tali sono anche le varie notazioni (O-grande, Omega, Theta...).
    Questo vuol dire che, se si intende valutare la complessità computazionale per valori ridotti del parametro N e/o valutare le prestazioni dell'algoritmo in condizioni specifiche diverse da quelle di caso peggiore, non è opportuno avvalersi di tali approssimazioni (anzi, nel primo dei casi che ho citato è proprio scorretto): occorre calcolare esattamente la complessità dell'algoritmo.
    @wrugg25: esattamente.
    Questo richiede una conoscenza NON solo della complessita' del caso peggiore, ma anche della complessita nel caso GENERALE/MEDIO.

    Esistono diversi algoritmi che hanno una complessita' pessima nel caso peggiore, ma ragionevole nel caso medio. Il primo che mi viene in mente e' l'algoritmo del Simplesso.

    Oppure, un'altra alternativa, e' usare algoritmi APPROSSIMATI che non forniscono il risultato MIGLIORE, ma un BUON risultato com complessita' ragionevole.

    Comunque, questi sono dettagli che si apprezzano quando si e' ben digerito la differenza tra una ricerca lineare ed una ricerca su un albero bilanciato.

    Senza contare che si puo' fare di meglio, A CERTE CONDIZIONI:

    usare una hash table!

    Complessita': O(1)
  • F
    fra95ncy
    Pochi posts
    Iscritto da
    mag, 2015
    Messaggi:
    9

    Re: Scelta tra Liste ed Alberi

    Innanzitutto, ho esplicitamente usato la notazione di limite asintotico superiore (O(...)), proprio per riferirmi ad un numero di dati sufficientemente grande, visto che, come scritto nella domanda, si tratta della scrittura di un database. Detto questo, praticamente, per un numero sufficientemente grande di dati, le liste risultano avere generalmente una complessità minore per quanto riguarda alcune operazioni (per esempio l'inserimento di un elemento in coda), e maggiore per quanto riguarda altre (ricerca di un elemento...). Come scritto da qualcuno come risposta alla mia domanda, quindi, ipotizzo che si debba ragionare pensando a quale operazione un ipotetico utente, userà maggiormente, in modo da "guadagnare tempo" su queste operazioni, a scapito di altre che si useranno meno. Giusto?
  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Scelta tra Liste ed Alberi

    Come ti dicevo in un post prima, non c'è una struttura dati più valida dell'altra, tra le due proposte; io direi non esiste una struttura dati migliore di un'altra in generale, quello che si fa quando si progetta è capire l'uso che si deve fare di quella struttura. Se qualcuno deve fare delle ricerche meglio gli alberi, o altre strutture più adatte a ciò, se devi gestire una coda allora inserisci in testa, estrai in coda con un costo computazionale O(1) (ovviamente con un puntatore alla testa e un puntatore alla coda), ciò fa si che la struttura a lista è di gran lunga la migliore in questo caso.
  • +m+
    +m+
    Molto attivo
    Iscritto da
    gen, 2016
    Messaggi:
    712

    Re: Scelta tra Liste ed Alberi

    fra95ncy ha scritto:

    ...Detto questo, praticamente, per un numero sufficientemente grande di dati...
    Come ti ho spiegato e dimostrato, è il "sufficientemente grande" da dover essere conosciuto, o almeno stimato
    ... le liste risultano avere generalmente una complessità minore per quanto riguarda alcune operazioni (per esempio l'inserimento di un elemento in coda)... ipotizzo che si debba ragionare pensando a quale operazione un ipotetico utente, userà maggiormente...Giusto?
    Giustissimo.
    Supponi, ad esempio, che la funzione di ricerca non sia MAI usata (perche ad esempio devi memorizzare dati bulk o un log o cose del genere).

    Inoltre, se proprio vogliamo inquadrare il problema professionalmente, non è solo la complessità intesa come tempo di esecuzione da dover essere considerata, bensì anche tutte le condizioni al contorno, che son tante e richiedono conoscenze sempre più approfondite.

    La prima è l'occupazione di memoria: il tradeoff tra strutture "veloci" ma grandi e "lente" ma piccole va tenuto in considerazione, soprattutto quando i dati sono davvero tanti (il che significa più della dimensione della RAM fisica del calcolatore), questo è normalissimo nell'ambito dei database (stutture indiciali compatte per poter risiedere in memoria).

    Poi, sempre andando verso lo specialistico, c'è la località degli accessi e la relativa modalità. L'hardware dell'elaboratore accede ai dati in RAM tipicamente mediante strati successivi di cache (* dipende dall'architettura della CPU) e mediante sistemi (* quasi sempre presenti) di paginazione per la virtualizzazione della memoria (* sia su RAM che su filesystem che perfino su disco oggi con i settoroni da 4k).

    Algoritmi apparentemente buoni (tipo hash) determinano tipicamente grande scattering nell'accesso alla RAM, quindi caricamento nella cache di pagine separate, discard dei dati interni, problemi coi TLB e così via
    Algoritmi apparentemente cattivi (di elaborazione sequenziale) invece possono spesso beneficiare del pre-caricamento sia delle pagine (dal pool virtuale o fisico della memoria) sia soprattutto con la cache di primo livello, ottenendo prestazioni di gran lunga superiori.

    Poi c'è tutto il discorso relativo all'implementazione, ovvero alla disponibilità per certe CPU di particolari estensioni (o istruzioni) che consentono di implementare efficientemente certi algoritmi, piuttosto che altri.

    In sostanza la complessità di un algoritmo "pensato ad alto livello" non è affatto pari a quella dell'algoritmo "concretamente" eseguito dal calcolatore.
  • +m+
    +m+
    Molto attivo
    Iscritto da
    gen, 2016
    Messaggi:
    712

    Re: Scelta tra Liste ed Alberi

    migliorabile ha scritto:

    Senza contare che si puo' fare di meglio, A CERTE CONDIZIONI:

    usare una hash table!

    Complessita': O(1)
    magari (vedi pippone precedente)
  • F
    fra95ncy
    Pochi posts
    Iscritto da
    mag, 2015
    Messaggi:
    9

    Re: Scelta tra Liste ed Alberi

    Ci tengo a ringraziare tutti per le risposte alla mia domanda ! Mi avete aiutato molto, dandomi risposte addirittura più complete di quelle che mi aspettavo. Grazie 1000 a tutti! Il miglior forum
Devi accedere o registrarti per scrivere nel forum
10 risposte