0

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

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

次に、1つのエントリを削除しました

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

そして今、別のアイテムを追加したかったのですが、削除されたキーを再利用したい.
最初に使用可能なキーを特定するのに必要な時間を最適化するために再設計するにはどうすればよいですか?

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

4

3 に答える 3

1

1行1列になるのを避ける方法は実際にはありませんが、通過する必要のある数を減らすためだけです。

たとえば、使用可能な最小の数値を別の変数に保持する場合、追加した後は、使用したばかりのキーから次に小さい値をチェックするだけです。

パフォーマンスの観点から、ハッシュが数百万のキーを保持しない限り、各キーを順番に調べる必要があることを心配する必要はありません。ハッシュに100万個のキーがある場合でも、1秒未満で連続して最小値を見つけることができます。

于 2012-05-09T02:05:40.377 に答える
1

明示的なループを使用するよりも、より慣用的な Ruby の書き方があります。このようなもの：

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

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

于 2012-05-09T01:52:13.237 に答える
1

たとえば、ハッシュをサブクラス化またはパッチして、利用可能な最小数 (および取得した最大数、またはその他の必要な数) を追跡できます。の線に沿った何か

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

しかし、繰り返しになりますが、何かを最適化する必要があると思われる場合は、その決定をサポートする数値を用意することをお勧めします (ヒント:プロファイルと測定)。

于 2012-05-09T02:08:50.623 に答える