从红宝石中的独家Range获得最大价值的最快方法

Question

好吧,所以说你在红宝石中有一个非常大的范围.我想找到一种方法来获得范围中的最大值.

范围是独占的(由三个点定义),这意味着它不包括结果中的结束对象.它可以由整数,字符串,时间,还是真的是响应任何物体#<=>和#succ.(这是Range中开始/结束对象的唯一要求)

以下是独家范围的示例:

  past  = Time.local(2010, 1, 1, 0, 0, 0)
  now   = Time.now
  range = past...now

  range.include?(now)  # => false

现在我知道我可以做这样的事情来获得最大值:

  range.max  # => returns 1 second before "now" using Enumerable#max

但这需要花费很多时间来执行.我也知道我可以从最终对象中减去1秒.但是,该对象可能不是Time,甚至可能不支持#-.我更愿意找到一个有效的通用解决方案,但我愿意将特殊案例代码与一般解决方案的后备结合起来(稍后会详细介绍).

如上所述,使用Range#last也不起作用,因为它是一个独占范围,并且不包括其结果中的最后一个值.

我能想到的最快的方法是:

  max = nil
  range.each { |value| max = value }

  # max now contains nil if the range is empty, or the max value

这类似于Enumerable#max(Range继承),除了它利用每个值将大于前一个的事实,因此我们可以跳过使用#<=>来比较每个值与前一个(方式Range#max)保存一个一点点时间.

我正在考虑的另一种方法是为常见的ruby类型(如Integer,String,Time,Date,DateTime)提供特殊的案例代码,然后使用上面的代码作为后备.它有点难看,但是当遇到这些对象类型时可能效率更高,因为我可以使用减法Range#last来获得最大值而无需任何迭代.

任何人都可以想到比这更有效/更快的方法吗？

Answer 1

我能想到的最简单的解决方案,适用于包容性和独家范围:

range.max

其他可能的解决方案:

range.entries.last
range.entries[-1]

这些解决方案都是O(n),对于大范围来说非常慢.原则上的问题是Ruby中的范围值是succ从所有值迭代地使用该方法枚举的,从头开始.元素不必实现返回先前值的方法(即pred).

最快的方法是找到最后一项的前任(O(1)解决方案):

range.exclude_end? ? range.last.pred : range.last

这仅适用于具有实现元素的范围pred.更高版本的Ruby实现pred了整数.如果它不存在,你必须自己添加方法(基本上等同于你建议的特殊情况代码,但实现起来稍微简单).

一些快速基准测试表明,对于大范围(在这种情况下range = 1...1000000),最后一种方法是最快的数量级,因为它是O(1):

                                          user     system      total        real
r.entries.last                       11.760000   0.880000  12.640000 ( 12.963178)
r.entries[-1]                        11.650000   0.800000  12.450000 ( 12.627440)
last = nil; r.each { |v| last = v }  20.750000   0.020000  20.770000 ( 20.910416)
r.max                                17.590000   0.010000  17.600000 ( 17.633006)
r.exclude_end? ? r.last.pred : r.last 0.000000   0.000000   0.000000 (  0.000062)

基准代码在这里.

在评论中建议使用range.last - (range.exclude_end? ? 1 : 0).它适用于没有其他方法的日期,但永远不会用于非数字范围.String#-不存在,并且对整数参数没有意义.String#pred但是,可以实现.