Ricordo di aver letto che non esistono strutture dati esistenti che consentano l'accesso casuale a una codifica a lunghezza variabile, come UTF-8, senza richiedere tabelle di ricerca aggiuntive.
La domanda principale che ho è, questa è anche una proprietà utile? Voglio dire, cercare e sostituire i singoli codepoints casuali in tempo O (1).
Darei la risposta tradizionale, e davvero piuttosto noiosa di dipende .
L'accesso casuale ai singoli caratteri (glifi) in una stringa è una proprietà utile? Sì, sicuramente .
Hai bisogno di accedere ai singoli punti di codice? Immagino che potrebbe essere utile in determinate situazioni che non sono troppo elaborate se si sta facendo una vasta gestione dei dati di testo, come ad esempio l'elaborazione di testi o il rendering del testo. La normalizzazione dei dati (codifica del testo) è un altro possibile caso d'uso a cui posso pensare. Sono sicuro che ci sono anche altri buoni usi.
Deve essere in O (1) tempo? In realtà, con poche eccezioni che è improbabile che si applichino nel caso generale, non necessariamente . Se O (1) l'accesso temporale è un requisito, è probabilmente più semplice usare una codifica a lunghezza fissa come UTF-32. (E si tratterà ancora di errori di cache e di spazio di scambio, quindi per stringhe sufficientemente lunghe non sarà comunque O (1) ...:))
La libreria standard Swift ha aggirato questo problema. È possibile accedere al primo, al secondo, al terzo elemento di una stringa, ma richiede tempo lineare.
Ma è piuttosto raro che ciò sia necessario. Lavorate con gli indici, che rappresentano le posizioni all'interno di una stringa. Se chiedi "dov'è la posizione di quest'ultima z in questa stringa, la risposta non è" 6 ° carattere "ma" indice 9 ".
PS Gli indici sembrano essere indici di parole UTF-16 (o byte se una stringa è semplice ASCII), ma questo è un dettaglio di implementazione. Le unità possono essere byte UTF-8, parole UTF-16, punti codice o caratteri = grapheme cluster.
Fuori dalla mia testa:
Poiché la maggior parte dei punti di codice dalla prospettiva eurocentrica sono single-byte, forse sarebbe utile una buona O (1) per questi casi e O (N) per i caratteri più lunghi. Forse si memorizza il byte principale del punto di codice nell'array principale a lunghezza fissa, ma se il byte indica un char esteso (1 nel IIRC del primo bit per utf-8), allora dice all'algoritmo che i caratteri estesi sono in un secondario array di archiviazione che non ha una lunghezza uniforme.
Questo array di archiviazione secondario tiene traccia dei byte estesi e dell'indice nell'array a byte fisso primario in cui è apparso il carattere. Per una ricerca a freddo, avresti O (N) dove N è il numero di byte extra personaggi. Se si stava eseguendo l'iterazione attraverso l'array, si potrebbe avere un puntatore seguente nell'archiviazione dei caratteri estesa e non avere alcun impatto reale sui caratteri byte aggiuntivi. Le linee della cache non dovrebbero essere orribili dal momento che sono entrambe le matrici.
Leggi altre domande sui tag unicode complexity