Crystal、ハッシュ、ルックアップの大文字小文字のどちらの方が速いでしょうか？

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

caseパフォーマンスに非常に近く、NameTuppleのような不変の構造を使用して試すことができます比較的小さい比較vコンパイル時によく知られているように、確かに最速であり（Faustinoが指摘したように）、直接比較を使用するのに最もメモリ効率が良い。

caseおよびNamedTupleの例は、基本的に一連のx == "a" || x == "z"まで沸騰します。これは、コードの複雑さが非常に低く、ヒープ割り当てがなく、高速で比較されるという意味で、単純なものです。

ハッシュを使用する場合、各比較ではかなりのオーバーヘッドが追加されるハッシュアルゴリズム（したがって名前）が呼び出されます。しかし、ハッシュはコンパイル時に知られていない複雑な値や動的な値を格納するための素晴らしいデータ構造です。

大規模な文字列のコレクションを比較すると、ある時点では、完全な長さのすべてのアイテムを比較する必要があるため、単純化されたアプローチは効率的ではありません。より効率的なアプローチは、プレフィックスツリーと呼ばれるこのようなルックアップのための特殊なデータ構造です（Crystal実装についてはhttps://github.com/luislavena/radixを参照してください）。

Answer 2

結晶は、.detectではなく、.findの方法である。 （Whyを参照）

Hashはヒープメモリを割り当てるので、caseステートメントよりも遅いです。また

あなたは

Crystal

 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 

、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!