0

假设我有一个项目哈希，并且我还保留了最大键的数量。

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

然后我删除了 1 条目

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

现在我想添加另一个项目，但想重新使用已删除的密钥。
如何重新设计它以优化确定哪个是第一个可用密钥所需的时间？

我总是可以从 1 循环到hi并返回第一个可用的键，但即便如此，也许有一种快速的方法来编写它，而不是手动调用循环并进行比较？

4

3 回答 3

1

嗯，有一种比使用显式循环更惯用的 Ruby 方法来编写它。像这样的东西：

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

但逻辑是一样的。除非您使用另一个变量来跟踪最小可用密钥，否则您无法真正避免类似的事情。

于 2012-05-09T01:52:13.237 回答
1

没有真正的方法可以避免一对一，只能减少您必须通过的数字数量。

例如，如果您将最小的可用数字保留在一个单独的变量中，那么在添加之后，您所要做的就是检查从您刚刚使用的键开始的下一个最小值。

在性能方面，除非您的散列将包含几百万个键，否则您不必担心必须按顺序查看每个键。即使散列中有 100 万个键，您也可以在不到 1 秒的时间内连续找到最小值。

于 2012-05-09T02:05:40.377 回答
1

例如，您可以对 Hash 进行子类化或修补，并跟踪最低可用数字（以及最高获取数字或您想要的任何其他数字）。类似的东西

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

但是话又说回来，如果你认为你需要优化某些东西，你最好有数字来支持这个决定（提示：profile 和 measure）。

于 2012-05-09T02:08:50.623 回答