Вся правда о символах

#ruby

В одном из тестов наткнулся на такой вопрос:


  Что из нижеследующего, сказанного о символах (symbols), является
  истиной?
  
  Выберите один или несколько вариантов:
  
  a. Несколько копий символа могут существовать одновременно
  
  b. Только одна копия любого символа может существовать в единицу
  времени. Таким образом экономится память.
  
  c. Символы -- неизменяемые объекты, т.е. они не может быть изменёны
  после создания.
  
  d. Символы-ключи быстрее строк-ключей


Согласно документации:


  Symbol objects represent names and some strings inside the Ruby
  interpreter. They are generated using the :name and :"string" literals
  syntax, and by the various to_sym methods. The same Symbol object will
  be created for a given name or string for the duration of a program's
  execution, regardless of the context or meaning of that name. Thus if
  Fred is a constant in one context, a method in another, and a class in
  a third, the Symbol :Fred will be the same object in all three
  contexts.

module One
  class Fred
  end
  $f1 = :Fred
end
module Two
  Fred = 1
  $f2 = :Fred
end
def Fred()
end
$f3 = :Fred
$f1.object_id   #=> 2514190
$f2.object_id   #=> 2514190
$f3.object_id   #=> 2514190



Т.е. символ всегда существует лишь в одной копии, и из набора ответов [a, b], правильным
является ответ b. Поправьте меня, если я ошибаюсь.

А вот что насчёт [c, d]?  Правильно ли я понимаю, что из b вытекает и c? Я бы хотел
увидеть развёрнутый ответ на эту тему с ссылкой на документацию. И верно ли утверждение,
что символы-ключи в хеше работают быстрее?

От себя ещё хотел бы добавить ещё один вопрос: я привык использовать symbol в качестве
ключа в hash. Но какое ещё применение им можно найти (в рамках Ruby-way, конечно)?
Не исключено, что именно из непонимания предназначения символов вытекают все мои глупые
вопросы.
    

Ответы

Ответ 1

Прежде чем начать, напомню, что в Ruby держаться за объекты можно только по ссылке.



Символы суть интернированные строки.
Ну, почти. На самом деле это уникальные идентфикаторы интернированных строк.

То есть, где-то в интерпретаторе есть глобальный мап { название =>
символ }. Значение символа само по себе не несёт никакого смысла, но поддаётся сравнению
(причём, быстрому) на равенство и содержит ссылку на своё название.

PrivateString это абстрактная деталь реализации: нечто очень похожее на строку и
имеющее возможность сравнения со String, но недоступное из Ruby.

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

Таким образом, названия и символы находятся в отношении 1-к-1. Таким образом:


  Только одна копия любого символа может существовать в единицу времени.


Можно ли изменять символы?.. После прочтения вышеизложенного должен возникнуть закономерный
вопрос: "А что там менять-то?" Символ определяется своим object_id и указателем на
PrivateString с его названием. И значение PrivateString получить невозможно. Так что:


  Символы -- неизменяемые объекты, т.е. они не могут быть изменёны после создания.


Осталось последнее. Быстрее ли они в качестве ключей, чем строки? (Предполагаю, что
речь о ключах в Hash) Принято считать, что да. Но что кто-то там считает неинтересно,
верно?

Берём лопату и идём смотреть асимптотику.


Символы сравниваются за О(1), по object_id, но при условии, что оба символа встречаются
не впервые: в противном случае их надо будет сначала поместить в глобальный мап. Один
раз за время их жизни.


Время жизни это отдельная тема. В Ruby 2.2 символы, наконец, начали собираться сборщиком
мусора! До этого символ, появившись в программе один раз, существовал до самого завершения.
Поэтому делать символы с названиями из пользовательского ввода было опасно. Невинный
params[:foo].to_sym мог случайно устроить вам Denial of Service.

Наивное сравнение строк O(N.size). Но если использовать хэширование, ситуация усложняется.
Хэши сравниваются за O(1), т. к. имеют фиксированную длину.


Брать хэши всё равно придётся за O(N.size), но их можно сохранять, они останутся
актуальными до очередного изменения строки.
Равенство хэшей значений не гарантирует равенство значений (коллизии!).


Но для заранее известных строк можно подготовить идеальную хэш-функцию, коллизии
в которой отсутствуют. Используется ли это в Ruby, я не знаю, но учитывая мутабельность
строк в Ruby, это было бы нерационально. В MRI используется библиотека gperf, но для
этого ли, я не в курсе. Предполагаю, что она используется для мапа символов, но не ручаюсь.

Когда объект сравнивается с самим собой... O(1).
В сухом остатке, строки придётся сравнивать в худшем случае за O(N.size).



Уф. Так что быстрее? Смотря в какой ситуации.

Если множество ключей невелико (или редко меняется), символы прекрасно справятся:
они будут быстренько добавлены в общий мап и далее все операции с ними будут молниеносными.
И обычно множество ключей действительно известно заранее и невелико.

Если множество ключей потенциально велико (пользовательский ввод), то ситуация усложнятся
(опять). Время добавления в глобальный мап всё-таки не нулевое, но если оперировать
с обычными строками, любой выигрыш во времени устранится уже за несколько операций.

Поэтому...


  Символы-ключи быстрее строк-ключей


...как правило. В каких-то искусственных условиях, вероятно, они могут вести себя
медленнее, но на практике такие случаи малореальны.



Обновление: начиная с MRI 2.3 появился режим frozen string literals, который литералы
строк в исходном коде воспринимает как замороженные, а потому неизменяемые, а потому
к ним можно применить те же оптимизации, что и к символам.