[Generale] Curiosità banalissima sulle strutture dati

[Gremo]

Ciao a tutti. Posto una domanda banale di cui intuisco già la risposta

Studiamo strutture dati come gli alberi che consentono di effettuare una ricerca con un costo proporzionale all'altezza nel caso dell'albero.

I linguaggi di alto livello utilizzano tali strutture per gestire ad esempio un semplice array e la funziona find()? Nel caso avessi tantissimi elementi in un array e la necessità di utilizzare find(), converrebbe implementare una struttura stile albero fatta a oggetti?

Si, no, perché?

[DanieleC88]

Originariamente inviato da Gremo

Nel caso avessi tantissimi elementi in un array e la necessità di utilizzare find(), converrebbe implementare una struttura stile albero fatta a oggetti?

[Gremo]

Immagina di avere in C# un array con 1 milione di numeri interi. Quale differenza in termini di prestazione si otterrebbe utilizzando find() su quell'array, oppure se implementassi un B-tree con semplici oggettini (con relative funzioni di inserimento, cancellazione e ricerca)? Che sappiamo avere mediamente un costo O(log(n))?

[cionci]

Originariamente inviato da Gremo

I linguaggi di alto livello utilizzano tali strutture per gestire ad esempio un semplice array e la funziona find()? Nel caso avessi tantissimi elementi in un array e la necessità di utilizzare find(), converrebbe implementare una struttura stile albero fatta a oggetti?

Dipende dal linguaggio, dipende dalla struttura dati che usi. Insomma dipende da molte cose.
Se hai necessità di fare molte find, la struttura dati ideale è una hash table.

[cionci]

Originariamente inviato da Gremo

Immagina di avere in C# un array con 1 milione di numeri interi. Quale differenza in termini di prestazione si otterrebbe utilizzando find() su quell'array, oppure se implementassi un B-tree con semplici oggettini (con relative funzioni di inserimento, cancellazione e ricerca)? Che sappiamo avere mediamente un costo O(log(n))?

Dipende se il costo di inserimento è superiore al costo di ricerca.
Bene o male prendere un array ed inserirlo in un B-tree ti costa O(n). Quindi dipende da quante ricerche devi fare.

[Gremo]

Originariamente inviato da cionci

Dipende dal linguaggio, dipende dalla struttura dati che usi. Insomma dipende da molte cose.
Se hai necessità di fare molte find, la struttura dati ideale è una hash map.

Almeno tu hai capito cosa intendo meno male Comunque la mia era curiosità, non devo implementare nulla. Però mi domando perché, se più efficienti, queste strutture (alberi) non sono implementate di default. Una tabella di hash è più veloce di un albero? Non mi ricordo bene...

[cionci]

La ricerca della presenza di una chiave in una tabella hash è generalmente costante.

Certo che sono implementate, ma dipende dalla struttura dati che usi. Comunque ogni struttura dati ha i suoi pro e i suoi contro. E' inutile cercare le prestazioni di ricerca in un array, quando in un array l'accesso è la maggior parte delle volte sequenziale.
Diversi linguaggi di alto livello hanno TreeMap e HashMap, che sono rispettivamente implementati con un red-balck tree e con un hash table.
Chiaramente ci sono altri problemi anche con questi, ad esempio nell'HashMap non c'è un ordinamento per chiave, nel TreeMap c'è, ma inserimento, rimozione e ricerca costano O(log n).
Ogni struttura dati ha i suoi vantaggi e i suoi svantaggi.

[pabloski]

quoto cionci e aggiungo che la ragione del perchè esistono ancora in tutti i linguaggi strutture "semplici" come gli array è che in informatica non esiste il migliore in assoluto ma bisogna sempre cercare di salvare cavolo e capra, valutando a seconda del problema da risolvere quali caratteristiche sono quelle più importanti e di conseguenza scegliere le strutture dati più opportune

[fero86]

Originariamente inviato da cionci

Bene o male prendere un array ed inserirlo in un B-tree ti costa O(n). Quindi dipende da quante ricerche devi fare.

si, ma inserire gli N elementi in un array puó costare molto di piu se l'array non é preallocato e comunque costa ugualmente O(N) se l'array é preallocato.

[cionci]

Originariamente inviato da fero86

si, ma inserire gli N elementi in un array puó costare molto di piu se l'array non é preallocato e comunque costa ugualmente O(N) se l'array é preallocato.

Se vuole trasferire gli elementi da un array ad un albero si suppone che siano già all'interno dell'array, no ?