ruby - Ruby 中是否有类似“lower_bound”的方法？

Question

在 C++ 中，std::map#lower_bound查找元素并在其上返回一个迭代器，或者如果它不在地图中，则在地图中最近的较小元素上返回一个迭代器。

Ruby 中是否有与std::map#lower_bound的实例具有相同行为的方法Hash？如果不是，我应该Hash用我的方法扩展类，还是有功能组合来实现相同的效果/复杂性？

Answer 1

有一个宝石rbtree。它将键映射到像哈希一样的值，但以升序键顺序维护其元素。接口与Hash的接口几乎相同。

gem install rbtree

例子：

require "rbtree"

rbtree = RBTree["a", 20, "b", 40, "c", 60, "d", 80, "e", 100]

itlow = rbtree.lower_bound("b")
itup = rbtree.upper_bound("d")

rbtree.bound(itlow.first, itup.first) do |k, v|
  puts "- #{[k, v]}"
end

输出：

-- ["b", 40]
-- ["c", 60]
-- ["d", 80]

Answer 2

Ruby Hash 没有这种能力，因为没有办法在 Hash 中找到最接近 Hash 中不存在的元素的元素。这是所有哈希的属性，而不仅仅是 Ruby 哈希。即使它们的值非常接近，两个元素也可以存储得很远——这完全取决于所使用的散列函数。

在 C++ 中可以使用 map.lower_bound 的原因是因为 std::map 是一棵树，而不是哈希，因此树查找涉及访问树的所有 (log n) 层（在最坏的情况下），而不管键是否存在与否。正如 Said 所说，如果您需要类似 lower_bound 的行为，请使用 rbtree（或其他一些平衡的树状数据结构，例如https://github.com/Kanwei/Algorithms/ ）。

Answer 3

关于使用树而不是哈希的建议可能是最好的。但是您也可以使用更暴力的方式来获取这些值。

  def get_lower_bound(hash, dt)
      lb_key = nil
      lb_val = nil
      hash.each do |key, val|
          if lb_key == nil or lb_key <= key and key <= dt
              lb_key = key
              lb_val = val
          end
      end
      lb_val
  end

  def get_upper_bound(hash, dt)
      ub_key = nil
      ub_val = nil
      hash.each do |key, val|
          if ub_key == nil or ub_key >= key and key >= dt
              ub_key = key
              ub_val = val
          end
      end
      ub_val
  end

Answer 4

您还可以使用treemap库将higher_entry/higher_key和lower_entry/lower_key用于upper_bound和lower_bound

Treemap 可以是一种有效的性能驱动解决方案。使用像 ceiling_entry、higher_entry 和 floor_entry 这样的键可以分别给出上限和下限。这里以 _entry 结尾的键给出了一个恒定的时间检索。相反，以 _key 结尾的相同函数可以给出 logN 解决方案。

https://github.com/davidkellis/treemap/blob/master/lib/treemap/tree_map.rb https://github.com/davidkellis/treemap