Perché non posso memorizzare le chiavi di stringa in una matrice associativa?

Question

Sono un neofita del linguaggio di programmazione D, ho appena iniziato a leggere il libro di D Programming Language.

mi imbatto in errore quando prova un array associativo codice di esempio

#!/usr/bin/rdmd 
import std.stdio, std.string; 

void main() { 
    uint[string] dict; 
    foreach (line; stdin.byLine()) { 
     foreach (word; splitter(strip(line))) { 
      if (word in dict) continue; 
      auto newId = dict.length; 
      dict[word] = newId; 
      writeln(newId, '\t', word); 
     } 
    } 
} 

DMD mostra questo messaggio di errore:

./vocab.d(11): Error: associative arrays can only be assigned values with immutable keys, not char[]

sto usando DMD compilare 2.051

stavo indovinando il le regole per gli array associativi sono cambiate dal libro TDPL.

Come devo utilizzare gli array associativi con chiavi stringa?

Grazie.

Aggiornamento:

ho trovato la soluzione in parti successive del libro.

utilizzare string.idup per creare un valore immutabile duplicato prima di inserirlo nell'array.

così

dict[word.idup] = newId; 

sarebbe fare il lavoro.

Ma è efficiente?

Answer 1

Gli array associativi richiedono che le loro chiavi siano immutabili. Ha senso quando si pensa al fatto che se non è immutabile, allora potrebbe cambiare, il che significa che il suo hash cambia, il che significa che quando si va a recuperare il valore, il computer non lo troverà. E se vai a sostituirlo, finirai con un altro valore aggiunto all'array associativo (quindi, ne avrai uno con l'hash corretto e uno con un hash errato). Tuttavia, se la chiave è immutabile, non può cambiare e quindi non esiste un problema di questo tipo.

Prima di dmd 2.051, l'esempio funzionava (che era un bug). Ora è stato risolto, quindi l'esempio in TDPL non è più corretto. Tuttavia, non è tanto il caso che le regole per gli array associativi siano cambiate in quanto vi è stato un bug in esse che non è stato catturato. L'esempio è compilato quando non dovrebbe avere, e Andrei lo ha perso. È elencato nel official errata for TDPL e dovrebbe essere corretto nelle stampe future.

Il codice corretto deve utilizzare dictionary[word.idup] o dictionary[to!string(word)]. word.idup crea un duplicato di word che è immutabile. to!string(word), d'altra parte converte word in un string nel modo più appropriato.Come word è un char[] in questo caso, che sarebbe quello di utilizzare idup. Tuttavia, se word fosse già un string, restituirebbe semplicemente il valore passato e non copiarlo inutilmente. Quindi, nel caso generale, to!string(word) è la scelta migliore (in particolare nelle funzioni basate su modelli), ma in questo caso, funziona perfettamente (to!() è in std.conv).

È tecnicamente possibile trasmettere un char[] a string, ma in genere è una cattiva idea. Se tu rispondi allo che il char[] non cambierà mai, allora puoi farla franca, ma nel caso generale, stai rischiando problemi, dal momento che il compilatore supporterà che lo string risultante non possa mai cambiare, e potrebbe generare codice che non è corretto. Potrebbe persino segfault. Quindi, non farlo a meno che la profilatura dimostri che hai davvero bisogno dell'efficienza extra di evitare la copia, altrimenti non puoi evitare la copia facendo qualcosa come semplicemente usando uno string in primo luogo (quindi non sarebbe necessaria alcuna conversione) e tu sai che il string non sarà mai cambiato.

In generale, non mi preoccuperei troppo dell'efficienza della copia delle stringhe. In genere, dovresti utilizzare anziché char[], quindi puoi copiarli (ovvero copiare il loro riferimento in giro (ad esempio str1 = str2;) anziché copiare l'intero contenuto come dup e idup do) senza preoccuparti che sia particolarmente inefficiente. Il problema con l'esempio è che stdin.byLine() restituisce uno char[] anziché uno string (presumibilmente per evitare di copiare i dati se non è necessario). Quindi, splitter() restituisce un char[] e così word è un char[] anziché uno string. Ora, è possibile eseguire splitter(strip(line.idup)) o splitter(strip(line).idup) anziché idup. In questo modo, splitter() restituirebbe uno string anziché char[], ma probabilmente è altrettanto efficiente quanto idup in word. A prescindere, a causa di dove il testo proviene originariamente, è uno char[] invece di uno string, che obbliga a idup da qualche parte lungo la linea se si intende utilizzarlo come chiave in un array associativo. Nel caso generale, tuttavia, è meglio usare solo string e non char[]. Quindi non è necessario per nulla idup.

EDIT:
In realtà, anche se si trova una situazione in cui la fusione char[]-string sembra sia sicuro e necessario, considerare l'utilizzo di std.exception.assumeUnique() (documentation). È essenzialmente il modo preferito di convertire un array mutabile in uno immutabile quando è necessario e sapere che è possibile. Normalmente si farebbe nei casi in cui hai costruito un array che non potresti rendere immutabile perché dovevi farlo a pezzi ma che non ha altri riferimenti e non vuoi crearne una copia profonda. Non sarebbe utile in situazioni come l'esempio che stai chiedendo, dato che hai davvero bisogno di copiare l'array.

Answer 2

No, non è efficiente, poiché ovviamente duplica la stringa. Se è possibile garantire la stringa che si crea sarà mai essere modificato in memoria, non esitate a utilizzare esplicitamente un cast cast(immutable)str su di esso, invece di duplicarlo.

(Anche se ho notato che il garbage collector funziona bene, quindi suggerisco di non provarlo a meno che non si veda un collo di bottiglia, dato che potresti decidere di cambiare la stringa in seguito. codice per aiutarti a trovare il collo di bottiglia più tardi, se esiste.)