In che modo sono implementati elenchi misti e senza dimensioni in lingue di livello superiore?

Gli array, come tutte le strutture dati, scambiano un tipo di efficienza per un altro.

L'efficienza di cui un array è specializzato è quella di cercare rapidamente un elemento tramite il suo indice. Lo fa, non cercando nella matrice l'elemento corretto, ma eseguendo un calcolo matematico. Se un array ha elementi di dimensione 8 byte e si desidera cercare l'ennesimo elemento, esso si troverà nella posizione di memoria che è 8 * n byte dall'inizio della matrice.

Se vuoi aggiungere m elementi alla fine di un array, puoi farlo semplicemente assegnando la memoria aggiuntiva alla fine dell'array, se è gratuito. Se quella memoria è non libero, devi creare un nuovo array e copiare i vecchi dati su di esso.

Le liste funzionano diversamente dagli array. Le liste sono strutture dati che collegano un elemento al successivo con una sorta di puntatore. Ogni elemento può essere memorizzato ovunque nella memoria, quindi non è più possibile cercare rapidamente un indice per indice. Devi attraversare la lista, saltando da elemento a elemento attraverso i collegamenti, fino a trovare l'elemento che desideri. Alcuni elenchi hanno indici come b-tree o hash che rendono questo processo di ricerca molto più veloce, ma non è ancora così veloce come calcolare una posizione di indice in un array.

Immagino che il tipo di "liste" che avevi in mente non fossero le "liste collegate" menzionate da Robert Harvey, ma il tipo di matrici che sono chiamate list in Python, List o ArrayList in C # , ArrayList in Java o std::vector in C ++. Un altro termine popolare per questo tipo di struttura dati è "array dinamico" .

Questi sono effettivamente implementati internamente esattamente come lo hai abbozzato: ognuno di essi ha una capacità massima, e quando viene raggiunto quel limite, assegna automaticamente un nuovo blocco di memoria e copia il contenuto in quel nuovo blocco. Una strategia di riallocazione popolare e generalizzata è quella di ingrandire il blocco con un fattore costante compreso tra 1 e 2. Per la maggior parte dei programmi del mondo reale, questo funziona sorprendentemente efficiente, e se si ha un caso in cui non è abbastanza efficiente, spesso è possibile controllare la capacità manualmente.

E sì, questi elenchi in genere supportano solo elementi dello stesso tipo di dati. Ma in Java e C #, tutti i tipi di dati sono derivati (o almeno possono essere derivati) da un "oggetto" di classe base comune. Ciò consente al tipo di dati di array dinamico di memorizzare internamente un riferimento al contenuto, che consente valori di contenuto di tipi diversi (i riferimenti, tuttavia, sono tutti della stessa dimensione, indipendentemente dal tipo di contenuto) . Sebbene non sia un esperto di Python, sono abbastanza sicuro che l'implementazione di list funzionerà internamente in modo simile.

Da quando hai scritto, hai usato solo C ++: un std::vector in C ++ è associato a un certo tipo, ma usando void * o un puntatore a un tipo base di una struttura di ereditarietà, si può aggirare questa limitazione . Quest'ultimo può gestire il tipo dei diversi elementi del vettore con un meccanismo chiamato RTTI per te, per usare il in precedenza devi gestire in qualche modo le informazioni sul tipo.

The closest thing I managed to write was a class in C++ which allocated a certain amount of memory and, when its size was filled, allocated a longer block of memory, copied the elements in that block and freed the first one, but that doesn't seem efficient at all and anyway only allows to add one specific type of item and only in a stack-like way (where you can only push or pop, not allocate an item at a random index).

Prima di tutto, fa bene a te per aver fatto questo esercizio. È altamente istruttivo cercare di capire come queste strutture di dati di livello superiore siano implementate in un linguaggio di basso livello. Lascia che ti dia qualche riflessione in più su questo.

• Prova ad andare più in basso . Per esempio, noto che si dà per scontato che esiste un allocatore di memoria e che ti restituisce un blocco delle dimensioni che desideri e puoi liberarlo quando hai finito. C'era un giorno in cui quelle funzioni non esistevano . Qualcuno ha dovuto scriverle per te. Supponiamo che tu abbia funzioni che potrebbero allocare e liberare memoria, ma solo in blocchi di 4k. Come scriverebbe malloc e gratis, dato solo quelle funzioni? Questo è un esercizio altamente educativo.

• Sii meno vago . Dici che la tua proposta "se non va bene, alloca un nuovo blocco e copia" la strategia è "inefficiente". L'efficienza è definita come il valore prodotto diviso per le risorse consumate. Indica il valore e le risorse che ti interessano e poi calcola l'efficienza numerica effettiva della tua implementazione .

• Implementa più funzioni . Dici che non puoi aggiungere un elemento nel mezzo di una lista di ridimensionamento al completo, ma perché no? Probabilmente puoi capire come farlo. Qual è l'efficienza di questa operazione? Che dire dell'eliminazione di un elemento dal centro di un elenco? La tua lista diventa più grande quando si riempie; diventa più piccolo quando diventa vuoto? Qual è l'efficienza di questo?

• Prova una struttura dati diversa . Puoi implementare un elenco collegato? Che dire di un albero binario? Che dire di un albero binario bilanciato? Puoi usarli come tipo di dati dell'elenco astratto? Elabora l'efficienza di ciascuna operazione in ciascuna di queste scelte di implementazione.

• abbraccia la genericità . Puoi utilizzare i modelli per creare elenchi astratti che contengono elementi di un particolare tipo?

Per rispondere alla tua domanda attuale:

Most higher level (or scripting) languages out there have data structures that can hold different types of data (like numbers, strings and even functions) in the same structure ... So how are these types of data structures found in higher level languages implemented in the lower level language they are written in?

Hai già dedotto come vengono implementati gli elenchi di dimensioni variabili: c'è un array da qualche parte, viene monitorato per la pienezza e riallocato quando è pieno. Ma per quanto riguarda la lista di elementi tutti di dimensioni diverse?

Posso sicuramente descrivere per voi come abbiamo implementato solo una tale struttura di dati nell'implementazione di JavaScript di metà degli anni '90 in Microsoft. La soluzione è molto semplice e chiara per lo sviluppatore C: abbiamo usato un'unione discriminata abbastanza grande da contenere una delle cose più importanti che sarebbero andate nella lista.

Per essere precisi, il tipo di unione discriminato era il tipo VARIANT di automazione OLE utilizzato da Visual Basic, che è descritto qui: link .

Poiché ogni VARIANT è di 16 byte, tutto ciò che devi fare è allocare array di strutture a 16 byte e raddoppiarli quando si riempie. Ciò significa che un array di mille interi a due byte richiede 16K, non 2K, ma a chi importa?

Purtroppo, questa soluzione è insufficiente; abbiamo un altro problema In JavaScript, gli array sono sparse e associativi . Cioè, gli array possono essere indicizzati 0, 1, 5, 1000, "giraffe", se ti piace. Quindi un array denso, con indice intero in stile C, non lo taglierà.

In effetti gli array JavaScript utilizzavano una tabella hash dinamicamente sviluppata per le ricerche e un elenco collegato associato per le enumerazioni. In questo modo le ricerche erano subliminali, ma le enumerazioni non cambiavano ordine quando venivano aggiunti articoli. L'indicizzazione è stata ottenuta convertendo gli indici in stringhe e poi eseguendo l'hashing della stringa. Per migliorare ulteriormente le prestazioni nei loop, i bucket hash erano elenchi collegati MRU .

L'implementazione di una tale struttura dati in C ++ è altamente educativa; dagli un colpo.

I tipi misti sono ospitati memorizzando puntatori su oggetti.

The closest thing I managed to write was a class in C++ which allocated a certain amount of memory and, when its size was filled, allocated a longer block of memory, copied the elements in that block and freed the first one, but that doesn't seem efficient at all

È abbastanza efficiente nel tempo. In genere la nuova dimensione è due volte la vecchia dimensione. Supponiamo quindi che la dimensione originale sia 128, quindi raddoppia a 256, quindi a 512, quindi a 1024. I primi 128 elementi vengono copiati tre volte, i successivi 128 vengono copiati due volte, i successivi 256 una volta. Il numero medio di copie è Sum (n / (2 ^ n)) = 2.