Crystal、哈希或 case 表达式查找哪个更快？

Question

根据已知组查找字符串，Hash(String=>Bool) 或 case?

哪个更快？

input = %w(a b c x y z)
valid = { "a" => true, "z" => true }
input.find { |x|

  !valid.has_key?(x)

  # or

  case x
  when "a", "z"
    false
  else
    true
  end
}

Answer 1

crystal 没有 .detect 但 .find 方法。（参见 Why）

Hash 正在分配堆内存，比 case 语句慢。

您也可以尝试使用像 NameTupple 这样的不可变结构，非常接近 case 性能

     hash  46.48M ( 21.51ns) (±14.08%)  3.90× slower
nametuple 173.82M (  5.75ns) (±15.75%)  1.04× slower
     case 181.28M (  5.52ns) (±13.24%)       fastest

Crystal, 450 字节

require "benchmark"

input = %w(a b c x y z)
valid1 = {"a" => true, "z" => true}
valid2 = {"a": true, "z": true}

Benchmark.ips do |x|
  x.report("hash") do
    input.find do |x|
      !valid1.has_key?(x)
    end
  end
  x.report("nametuple") do
    input.find do |x|
      !valid2.has_key?(x)
    end
  end
  x.report("case") do
    input.find do |x|
      case x
      when "a", "z"
        false
      else
        true
      end
    end
  end
end

Try it online!

Answer 2

对于在编译时已知的少量相对较小的比较值，采用直接比较肯定是最快且（正如 Faustino 指出的）最节省内存的。

case 和 NamedTuple 示例基本上可以归结为一系列 x == "a" || x == "z"。这非常简单，这意味着代码复杂度非常低，没有堆分配，比较速度快。

使用散列时，每次比较都会调用散列算法（因此得名），这会增加相当多的开销。然而，哈希是一种很好的数据结构，用于存储编译时未知的复杂值或动态值。

当比较较大的字符串集合时，在某些时候简单的方法不再那么有效，因为它需要比较每个项目的全长。一种更有效的方法是用于这种称为前缀树的查找的专用数据结构（有关 Crystal 实现，请参阅 https://github.com/luislavena/radix）。

Crystal、哈希或 case 表达式查找哪个更快？

Which would be faster in Crystal, a Hash or a case expression for lookups?

crystal-lang

Crystal, 450 字节