Что быстрее в ruby ​​- поиск по хешу или функция с оператором case?

Question

У нас есть несколько мест в критичном ко времени сценарии, где мы конвертируем старые идентификаторы в строки. На данный момент мы используем операторы case внутри функции, например:

def get_name id
  case id
    when 1
      "one thing"
    when 3
      "other thing"
    else
      "default thing"
  end
end

Я подумываю заменить это поиском по хешу, вот так:

NAMES = {
  1 => "one thing",
  3 => "other thing",
}
NAMES.default = "default thing"

Такое ощущение, что использовать NAMES[id] должно быть быстрее, чем get_name(id) - но так ли это?

Answer 1

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

Мой инстинкт инстинкта заключается в том, что хеши будут быстрее, потому что (опять же, я думаю,оператор case должен проверять каждое условие по очереди (делая поиск элементов O (n) вместо O (1)).Но давайте проверим!

Полный код сравнения в https://gist.github.com/25 По сути, он генерирует файл, который определяет соответствующий регистр / хэш, а затем использует их.Я пошел дальше и включил поиск хеша в вызов метода, чтобы издержки не были фактором, но в реальной жизни нет причин, по которым он должен застрять внутри метода.

Вот что я получаю,В каждом случае я делаю 10 000 поисков.Время - это время пользователя в секундах

Case statement, 10 items  0.020000
Hash lookup, 10 items     0.010000

Case statement, 100 items  0.100000
Hash lookup, 100 items     0.010000

Case statement, 1000 items  0.990000
Hash lookup, 1000 items     0.010000

Итак, очень похоже, что оператор case равен O (n) (шокера там нет).Также обратите внимание, что 10K-поиск - это всего лишь секунда даже в операторе case, поэтому, если вы не выполняете метрическую загрузку этих поисков, вам лучше сосредоточиться на остальной части кода.

Answer 2

Так как это зависит от ряда факторов (сколько разных идентификаторов вы хотите преобразовать, насколько грамотно компилятор может компилировать case when государственных деятелей), мой совет: Измерьте :

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

Answer 3

Вот пример, который показывает случай быстрее для поиска символа.Предыдущие примеры были целочисленными ключами.

https://gist.github.com/02c8f8ca0cd4c9d9ceb2

Answer 4

$ ruby -v
ruby 1.9.2p0 (2010-08-18 revision 29036) [i686-linux]

$ cat hash_vs_case.rb 
require 'benchmark'

def get_from_case(id)
  case id
    when 1
      "one thing"
    when 3
      "other thing"
    else
      "default thing"
  end
end

NAMES = {
  1 => "one thing",
  3 => "other thing",
}
NAMES.default = "default thing"

def get_from_hash(arg)
  NAMES[arg]
end

n = 1000000
Benchmark.bm do |test|
  test.report("case  1") { n.times do; get_from_case(1); end }
  test.report("hash  1") { n.times do; get_from_hash(1); end}
  test.report("case 42") { n.times do; get_from_case(42); end }
  test.report("hash 42") { n.times do; get_from_hash(42); end}
end

$ ruby -w hash_vs_case.rb 
      user     system      total        real
case  1  0.330000   0.000000   0.330000 (  0.422209)
hash  1  0.220000   0.000000   0.220000 (  0.271300)
case 42  0.310000   0.000000   0.310000 (  0.390295)
hash 42  0.320000   0.010000   0.330000 (  0.402647)

И вот почему вы хотите обновить:

$ ruby -v
ruby 1.8.7 (2009-06-12 patchlevel 174) [i486-linux]

$ ruby -w hash_vs_case.rb 
      user     system      total        real
case  1  1.380000   0.870000   2.250000 (  2.738493)
hash  1  1.320000   0.850000   2.170000 (  2.642013)
case 42  1.500000   0.960000   2.460000 (  3.029923)
hash 42  1.890000   0.890000   2.780000 (  3.456969)

Answer 5

Как сказал Мартин, это зависит от того, сколько идентификаторов вы хотите проверить. Вы выбираете идентификатор и соответствующие строки из базы данных или хотите жестко его кодировать. Если есть только пара проверок, то вы можете пойти с CASE. Но нет никакой возможности изменить пару ID / String, если возникнет такая необходимость.

С другой стороны, если вы выбираете много идентификаторов из базы данных, вы можете использовать что-то вроде словаря для хранения пар имя / значение.

Пока словарь находится в памяти, поиск может быть быстрым.

Но, в конце концов, все зависит от того, работаете ли вы с постоянно меняющейся парой ID / строка или только с несколькими константами.

Answer 6

Почему бы не использовать оператор case, встроенный в критическую по времени часть вашего кода, вместо того, чтобы делать это своим собственным вызовом функции? Это позволяет избежать затрат на стек вызовов, а также избежать затрат на поиск хеша.

Вы также всегда можете сделать тест самостоятельно. Сделайте что-то вроде этого:

t = Time.now
1_000_000.times { ...your code... }
secs = Time.now - t

Замена "вашего кода" каждой опцией.

Answer 7

case when имеет n сложность.
hash lookup имеет ln (n) сложность, но использование дополнительного объекта (хеша) и вызов его методов имеют свой штраф.

Так что, если у вас много дел (тысячи, миллионы, ...), поиск хеша лучше. Но в вашем случае, когда у вас есть только 3 варианта, case when, конечно, будет намного быстрее.