Почему я не могу хранить строковые ключи в ассоциативном массиве? - PullRequest
16 голосов
/ 06 января 2011

Я новичок в языке программирования D, только начал читать книгу "Язык программирования D".

Я сталкиваюсь с ошибкой при попытке попробовать один пример кода ассоциативного массива

#!/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 показывает это сообщение об ошибке:

. / Vocab.d (11): Ошибка: ассоциативным массивам можно присваивать значения только с неизменяемыми ключами, но не с символом []

Я использую DMD-компиляцию 2.051

Я догадывался, что правила для ассоциативных массивов изменились со времен книги TDPL.

Как использовать ассоциативные массивы со строковыми ключами?

Спасибо.

Обновление:

Я нашел решение в следующих частях книги.

используйте string.idup для создания дублируемого неизменяемого значения перед помещением в массив.

так

dict[word.idup] = newId;

сделает работу.

Но так ли это эффективно?

Ответы [ 2 ]

25 голосов
/ 06 января 2011

Ассоциативные массивы требуют, чтобы их ключи были неизменными. Это имеет смысл, когда вы думаете о том, что если он не является неизменяемым, то он может измениться, что означает, что его хеш-код изменяется, а это означает, что когда вы снова получите значение, компьютер его не найдет. И если вы замените его, вы получите еще одно значение, добавленное к ассоциативному массиву (поэтому у вас будет одно с правильным хешем и одно с неправильным хешем). Однако, если ключ является неизменяемым, он не может измениться, и поэтому такой проблемы нет.

До dmd 2.051, пример работал (который был ошибка ). Теперь это было исправлено, поэтому пример в TDPL больше не верен. Тем не менее, дело не столько в том, что правила для ассоциативных массивов изменились, сколько в том, что в них была ошибка, которая не была обнаружена. Пример скомпилирован, когда его не должно было быть, и Андрей пропустил его. Он указан в официальных исправлениях для TDPL и должен быть исправлен в будущих печатных изданиях.

Исправленный код должен использовать dictionary[word.idup] или dictionary[to!string(word)]. word.idup создает дубликат word, который является неизменным. to!string(word), с другой стороны, преобразует word в string наиболее подходящим способом. Поскольку word является char[] в этом случае, это будет использовать idup. Однако, если бы word уже было string, он просто вернул бы переданное значение и не стал бы его копировать без необходимости. Таким образом, в общем случае to!string(word) является лучшим выбором (особенно в шаблонных функциях), но в этом случае любой из них работает просто отлично (to!() находится в std.conv).

Технически возможно привести char[] к string, но обычно это плохая идея. Если вы знаете , что char[] никогда не изменится, то вы можете сойти с рук, но в общем случае вы рискуете проблемами, так как компилятор тогда предположит, что полученный string никогда не может измениться, и это может генерировать код, который является неправильным. Это может даже сегфо. Так что не делайте этого, пока профилирование не покажет, что вам действительно нужна дополнительная эффективность, чтобы избежать копирования, иначе вы не сможете избежать копирования, выполнив что-то вроде простого использования string во-первых (так что преобразование не будет необходимо), и вы знаете , что string никогда не изменится.

В общем, я бы не слишком беспокоился об эффективности копирования строк. Как правило, вы должны использовать string вместо char[], чтобы вы могли копировать их (то есть копировать их ссылки (например, str1 = str2;), а не копировать все их содержимое, как dup и idup do) не беспокоясь о том, что это особенно неэффективно. Проблема с примером заключается в том, что stdin.byLine() возвращает char[], а не string (предположительно, чтобы избежать копирования данных, если в этом нет необходимости). Так, splitter() возвращает char[], и поэтому word - это char[] вместо string. Теперь вы можете сделать splitter(strip(line.idup)) или splitter(strip(line).idup) вместо idup с ключом. Таким образом, splitter() вернет string, а не char[], но это, вероятно, так же эффективно, как idup ing word. В любом случае, из-за того, откуда исходил текст, это char[] вместо string, что заставляет вас idup где-то вдоль строки, если вы собираетесь использовать его в качестве ключа в ассоциативном массиве. Однако в общем случае лучше использовать string, а не char[]. Тогда вам не нужно idup ничего.

EDIT:
На самом деле, даже если вы обнаружите ситуацию, когда приведение от char[] до string кажется безопасным и необходимым, рассмотрите возможность использования std.exception.assumeUnique() ( документация ).По сути, это предпочтительный способ преобразования изменяемого массива в неизменяемый, когда вам нужно знать об этом.Обычно это делается в тех случаях, когда вы создали массив, который нельзя было сделать неизменным, потому что вам приходилось делать это по частям, но у которого нет других ссылок, и вы не хотите создавать его глубокую копию.Это не будет полезно в ситуациях, подобных примеру, о котором вы спрашиваете, поскольку вам действительно нужно скопировать массив.

1 голос
/ 06 января 2011

Нет, это не эффективно, так как очевидно, что дублирует строку.Если вы можете гарантировать , что создаваемая вами строка не будет никогда изменяться в памяти, не стесняйтесь явно использовать приведение cast(immutable)str к ней вместо ее дублирования.

(хотя я заметил, что сборщик мусора работает хорошо, поэтому я советую вам на самом деле не пробовать это, пока не увидите узкое место, так как вы можете решить изменить строку позже. Просто поместите комментарий в свой код, чтобыпомочь вам найти узкое место позже, если оно существует.)

...