[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]

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

:wtf:

[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]

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]

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]

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 :mbe: 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]

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]

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 ?