La condivisione strutturale in Scala List è semplice e di facile comprensione. Ma Scala Vector è una struttura dati più complicata di una lista. Come viene raggiunta la condivisione strutturale in Scala Vector?Condivisione strutturale nel vettore Scala
Il vettore è fondamentalmente un albero (trie) con una ramificazione di 32 livelli ad ogni livello. Se si dispone di un vettore di, ad esempio, 3000 elementi e si desidera indicizzare l'elemento 2045, ad esempio, che converte in 100000010101 in binario, lo decomporrà in blocchi da 5 bit da utilizzare come indici nell'albero: 10 (ovvero 2) nel primo ramo quindi 00000 (ovvero 0) nel successivo e infine (ovvero 21) nel ramo terminale, quindi i dati.
Data questa struttura, è facile vedere come condividere strutturalmente le cose: è possibile condividere qualsiasi sottoalbero che non viene modificato. Quindi, se crei un nuovo vettore con un elemento diverso 2045, devi modificare non tutti i 3000 elementi ma ricreare "solo" tre matrici di dimensione 32: quella terminale viene sostituita da una copia con l'elemento 21 aggiornato; allora il suo genitore deve essere sostituito da una copia con questo nuovo figlio nell'indice 0; quindi il genitore deve essere sostituito con la sottostruttura corretta nell'indice 2.
Ora, questo fornisce parecchia condivisione strutturale purché si disponga di più di 32 elementi nel vettore, ma è comunque un grande overhead . Per questo motivo, le aggiunte alla fine del vettore sono speciali in modo che tu possa semplicemente aggiungere alla matrice esistente. I vecchi Vettori puntano ancora a quell'array, ma pensano che la fine sia precedente (e quella parte è rimasta invariata) quindi funziona bene.
C'è uno schema più complesso ma simile per consentire l'aggiunta nella parte anteriore di un vettore in modo simile (fondamentalmente, lasciando lo spazio davanti e tenendo traccia di dove puntare tramite indici e offset oltre allo schema di indicizzazione).
Il trucco come implementato non funziona per consentire l'aggiunta alternata sia davanti che dietro, tuttavia, così da ricostruire efficacemente gli alberi ogni aggiunta. Creare una versione con una condivisione strutturale ancora migliore sarebbe possibile, ma probabilmente sarebbe un po 'più lento accedere.
Ottima domanda! –