Ruby中是否有类似于"lower_bound"的方法？

Question

在C++中，std::map#lower_bound查找元素并返回迭代器，如果元素不在映射中，则返回最接近该元素且小于它的元素的迭代器。

在Ruby中，是否有与std::map#lower_bound相同行为的方法适用于Hash实例？如果没有，我应该扩展Hash类来创建自己的方法，还是有一种函数组合可以实现相同的效果/复杂度？

- p1100i

Answer 1

这里有一个宝石rbtree。 它像Hash一样将键映射到值，但保持其元素按升序排列。接口与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]

- Said Kaldybaev

Answer 2

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

  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

- swdev

Answer 3

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

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

- fred271828

Answer 4

您也可以使用 higher_entry/higher_key 和 lower_entry/lower_key 進行上限和下限，使用 treemap library。

Treemap 可以是一個有效的性能驅動解決方案。使用類似 ceiling_entry、higher_entry 和 floor_entry 的 keys 可以分別給出上限和下限。在此以 _entry 结尾的 key 都可以在常數時間內檢索。相反，以 _key 結尾的相同函數可以提供 logN 解決方案。

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

- Prashanth Adepu