与えられた1milのデータを整数の配列で検索する方法

Question

私はmtdが1mil以上のレコード（整数のarraylistとして格納されています）を検索してempIDのパスが保存されたレコード。

現在、私はforループを通して順次検索を使用しています。どのように効率的に/より速くするには？

def exist?(id) 
    for i in 0...$employee_list.length 
     if $employee_list[i] == id # match! 
      return true 
     elsif $employee_list[i] > id # have already gone beyond the point where id should've been found 
      return false 
     end 
    end 

return false # cannot find id in the list 
end 

また、次のようにハッシュを使用してみましたが、それでも十分に高速ではありません。

hash = $employee_list.map{ |i | i} 

if hash.include? id 
    return true 
else 
    return false 
end 

Answer 1

あなたはメモリを買う余裕はないことを証明した場合を除き、Setを使用します。

# Do this just once 
require 'set' 
$employee_ids = Set.new $employee_list 

# Do this each time you need to check 
def exist?(id) 
    $employee_ids.include?(id) 
end 

それは関係なく、あなたが持っているIDの数の、ほぼ瞬時になります。

Answer 2

あなたの代わりに（スペース上の理由から）ArrayのSetを使用することはできませんし、あなたのArrayがソートされている場合、あなたは（<=>のような）整数を返すブロックでArray#bsearchを使用することができます。

Answer 3

これは、アレイ上のバイナリ検索を行い、この

array.bsearch {|x| number <=> x } 

を試してみてください。配列はソートされなければなりません。

要素xは、宇宙船オペレータの右側にあることに注意してください。

riコマンドを使用して、bsearchメソッドに関するその他のドキュメントを参照してください。バイナリ検索の複雑さはO(log n)です。これは、長さ100万の配列に対してのみ20ステップです。