アイテムが出てきてもアイテムのリストを追跡する：ruby

Question

アイテムのハッシュがあり、最大のキーの番号も保持しているとします。

 
L = {1=>"item1", 2=>"item2", 3=>"item3"}, hi = 3 

は、その後、私は1つのエントリに

 
L = {2=>"item2", 3=>"item3"}, hi = 3 

を取り出しそして今、私は別の項目を追加したかったが、再使用のキーを削除します。
どのように最初に利用可能なキーであるかを把握するのに必要な時間を最適化するように再設計することはできますか？

私はいつも1からhiまでループして、利用可能な最初のキーを返すことができますが、手動でループを呼び出して比較するのではなく、速い方法で書くこともできます。

Answer 1

明白なループを使用するよりも、慣れ親しんだRubyの書き方があります。このようなもの：

first_available = (1 .. hi+1).find { |k| !L.include? k } 

しかし、ロジックは同じです。利用可能な最小限のキーを追跡するために別の変数を使用しない限り、同様のことを避けることはできません。

Answer 2

だけが通過しなければならない数字の量を減らすために、1行1を行く回避する方法は本当にありません。例えば

あなたが追加した後は、別の変数内で使用可能な最小の番号を続ければ、あなたがしなければならないすべてはあなただけで使用したキーで始まる次の最低値のチェックです。あなたのハッシュは数百万個の鍵を保持する場合を除き、性能の面では

は、あなたがために、各キーに目を通すすることを心配する必要はありません。ハッシュに100万のキーがあっても、1秒未満で連続して最も低い値を見つけることができます。

Answer 3

たとえば、ハッシュをサブクラス化またはパッチして、利用可能な最下位番号（取得した最高の番号または必要な他の番号など）を追跡することができます。その後、

class MyHash < Hash 
    # override 
    def delete k 
    @min_available ||= 0 
    @min_available = k if k < @min_available 
    # or you can have an array here to keep track of all freed slots 
    # if you want to sacrifice some memory for speed in this situation 

    super k 
    end 

    def get_first_available 
    # use @min_available to serve this request 
    end 
end 

の線に沿って何かしかし、あなたは、あなたが何かを最適化する必要があると思う場合は、もう一度、あなたがより良い、その決定（ヒント：プロファイルと対策）をサポートするための番号を持っています。