将数字序列转换为条件/范围

Question

我有一个由数字和对应值组成的数组：

a = [[2, :foo], [5, :bar], ..., [17, :baz]]

假设没有两个数对具有相同的数字，并且这些数对按照其数字的值排序。基于数组a，我想传递一个数字i，该数字始终在a中的最小数字和最大数字之间，并返回与不超过i的数字配对的值。一些预期的返回值如下：

2 # => :foo
4 # => :foo
5 # => :bar
17 # => :baz

什么是最好的方法？使用哈希作为关键字处理范围存在问题，而使用case语句则难以动态适应a。

- sawa

---

哈希和范围有什么问题？ - js-coder

Answer 1

如果你想要对数复杂度，你需要使用二分搜索或者某种平衡搜索树。为了简单起见，我建议使用rbtree宝石：

require 'rbtree'

a = [[2, :foo], [5, :bar], [17, :baz]]
t = RBTree[a]

t.upper_bound 4  # => [2, :foo]
t.upper_bound 5  # => [5, :bar]
t.upper_bound 1  # => nil

- Niklas B.

---

感谢您的帮助。目前看来，这是最好的选择。 - sawa

Answer 2

对于即将到来的Range#bsearch，这是一项完美的工作 :-) 这样你就可以获得正确的日志复杂度。

bsearch被设置为查找最小值，而您需要查找最大值，因此需要反转数组。享受吧：

DATA = [[2, :foo], [5, :bar], [12, :hello], [17, :baz]].reverse

def lookup(i)
  nb, val = DATA.bsearch{|nb, val| i >= nb}
  val
end

lookup 2  # => :foo
lookup 4  # => :foo
lookup 5  # => :bar
lookup 17 # => :baz

从今天开始可以使用 require 'backports/2.0.0' :-)

- Marc-André Lafortune

---

感谢提供这么好的信息。在接下来的一两天里，Niklas的回答可能是最好的，但我也会尝试你提供的后移版本。当Ruby 2.0发布时，我可能会像你建议的那样切换到Range#bsearch。我刚刚发现这个新功能已经被期待了很久，它的出现应该是令人兴奋的。 - sawa

我想知道为什么这个特性在这么长的时间里还没有出现，因为它几乎可以轻松实现（尽管如果我正确地解释了Marc的回溯，2.0中的实际语义似乎相当晦涩）。 - Niklas B.

@NiklasB。许多功能在Ruby中不存在，因为对于名称、功能等没有达成一致的协议...例如，nil.to_h在C中只需一行，但在被添加到Ruby 2.0.0之前引起了很多讨论。而Enumerable#to_h则未能实现。 - Marc-André Lafortune

Answer 3

我不太明白你对哈希的问题，但如果我理解正确，这个方法可以正常工作。

a = [[2, :foo], [5, :bar], [17, :baz]]
h = Hash[a]

class Hash
  def get(i)
    return nil if i < keys.min
    i -= 1 until include?(i)
    self[i]
  end
end

h.get(4) #=> :foo
h.get(5) #=> :bar
h.get(1) #=> nil # No key below 2 exists.

- js-coder

---

考虑 a = [[1000000000, :foo], [2000000000, :bar]] 与 h.get(1999999999) 的组合 :) 另外，请不要扩展 stdlib 类。相反，使用 def h.get 或等效的东西。 - Niklas B.

前两个 self 是多余的，与 min 相比，它是低效的，最好使用 rindex 而不是循环... 最后，这是一个 O(n) 的解决方案，而存在一个 O(log n) 的解决方案。 - Marc-André Lafortune

只要你不在 gem 中进行扩展（除了像 activesupport 这样专门为此目的存在的 gem），扩展 stdlib 类是可以的。 - Alex D

欢迎来到 Ruby :-）。我指的是 first.first，因为 first 给出了第一对 [nb, val]。我建议阅读 https://github.com/bbatsov/ruby-style-guide。至于 rindex，我会让你自己处理 :-)。 - Marc-André Lafortune

@js-coder：不，哈希表没有固有的顺序。但在Ruby 1.9中，它们保留插入顺序（或者说，按照你在文字中指定的顺序）。因此，keys.first != keys.min通常是成立的，除非你确保按排序顺序插入元素（你可以使用Hash[a.sort_by(&:first)]来实现）。但这样做会防止你添加新元素。我认为Marc暗示的是，在这里使用哈希表是不必要的，因为你实际上并没有使用它提供的快速查找功能。你可以直接遍历a。 - Niklas B.