Как символы быстрее, чем строки в хэш-поисках?

Question

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

Что я не понимаю, так это то, что символы быстрее, чем строки в поиске хэша. Я посмотрел на ответы здесь, но до сих пор не совсем понял.

Если :foo.hash == :foo.object_id возвращенный true, тогда это имело бы какой-то смысл, потому что тогда он мог бы использовать идентификатор объекта в качестве значения для хеша и не должен был бы вычислять его каждый раз. Однако это не так и :foo.object_id не равно :foo.hash, Отсюда мое замешательство.

Answer 1

Там нет никаких обязательств для hash быть эквивалентным object_id, Эти две вещи служат совершенно другим целям. Точка hash должен быть как можно более детерминированным и в то же время случайным, чтобы значения, которые вы вставляете в ваш хэш, были равномерно распределены. Точка object_id заключается в определении уникального идентификатора объекта, хотя нет требования, чтобы они были случайными или равномерно распределенными. На самом деле, рандомизировать их контрпродуктивно, это просто сделало бы вещи медленнее без причины.

Причиной того, что символы имеют тенденцию быть быстрее, является то, что память для них выделяется один раз (не считая проблем со сборкой мусора) и перерабатывается для всех экземпляров одного и того же символа. Строки не такие. Они могут быть построены множеством способов, и даже две строки, которые являются побайтовыми, могут быть разными объектами. На самом деле, безопаснее предположить, что это так, чем иначе, если вы точно не знаете, что это один и тот же объект.

Теперь, когда дело доходит до вычислений hashзначение должно быть случайным образом отличным, даже если строка изменяется очень мало. Поскольку символ не может изменить вычисления, его можно оптимизировать больше. Вы можете просто вычислить хеш object_id так как это не изменится, например, в то время как строка должна учитывать содержимое самого себя, которое предположительно является динамическим.

Попробуйте сравнительный анализ вещей:

require 'benchmark'

count = 100000000

Benchmark.bm do |bm|
  bm.report('Symbol:') do
    count.times { :symbol.hash }
  end
  bm.report('String:') do
    count.times { "string".hash }
  end
end

Это дает мне такие результаты:

       user     system      total        real
Symbol:  6.340000   0.020000   6.360000 (  6.420563)
String: 11.380000   0.040000  11.420000 ( 11.454172)

Что в этом самом тривиальном случае легко в 2 раза быстрее. Основываясь на некотором базовом тестировании, производительность строкового кода ухудшается за O(N), так как строки становятся длиннее, но время символов остается постоянным.

Answer 2

Просто хочу добавить, что я не совсем согласен с числами, которые придумал @tadman. В моем тестировании это не более чем в 1,5 раза быстрее использовать calcualte '#hash'. я использовал benchmark/ips проверить производительность.

require 'benchmark/ips'

Benchmark.ips do |bm|
  bm.compare!
  bm.report('Symbol:') do
    :symbol.hash
  end
  bm.report('String:') do
    'string'.hash
  end
end

И это приводит к

Comparison:
             Symbol:: 10741305.8 i/s
             String::  7051559.3 i/s - 1.52x slower

Кроме того, если вы включите "фиксированные строковые литералы" (которые будут использоваться по умолчанию в будущих версиях ruby), разница уменьшится до коэффициента 1.2:

# frozen_string_literal: true

Comparison:
             Symbol::  9014176.3 i/s
             String::  7532196.9 i/s - 1.20x slower

Answer 3

Дополнительные издержки для строк в качестве хеш-ключей заключаются в том, что, поскольку строки являются изменяемыми, а также обычно используются хеш-ключи, класс Hash делает копию всех строковых ключей (вероятно, с помощью метода, такого как dup или clone), для защиты целостности хеш от повреждения ключа.

Рассматривать:

irb(main):001:0> a = {}
=> {}
irb(main):002:0> b = "fred"
=> "fred"
irb(main):003:0> a[b] = 42
=> 42
irb(main):004:0> a
=> {"fred"=>42}
irb(main):005:0> b << " flintstone"
=> "fred flintstone"
irb(main):006:0> a
=> {"fred"=>42}
irb(main):007:0> b
=> "fred flintstone"
irb(main):008:0>
irb(main):008:0> b.object_id
=> 17350536
irb(main):009:0> a.keys[0].object_id
=> 15113052
irb(main):010:0>

Символы неизменны и не нуждаются в таких решительных мерах.