Самый быстрый способ получить максимальное значение от эксклюзивного Range в рубине

Question

Хорошо, скажем, у вас действительно большой диапазон в рубине.Я хочу найти способ получить максимальное значение в диапазоне.

Диапазон является эксклюзивным (определяется тремя точками), что означает, что он не включает конечный объект в свои результаты.Он может состоять из Integer, String, Time или любого другого объекта, который отвечает на #<=> и #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 секунду из того, чем является конечный объект.Однако объект может быть чем-то отличным от времени, и он может даже не поддерживать #-.Я бы предпочел найти эффективное общее решение, но я хочу объединить код специального случая с откатом к общему решению (подробнее об этом позже).

Как упоминалось выше, использование 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 делает)сэкономив немного времени.

Другой подход, о котором я думал, - это иметь специальный код для общих типов рубинов, таких как 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, однако, может быть имплантировано .

Answer 2

Я не могу думать, что есть какой-то способ достичь этого, который не включает перечисление диапазона, по крайней мере, если, как уже упоминалось, у вас есть другая информация о том, как будет построен диапазон, и, следовательно, можете вывести желаемое значение без перечисления , Из всех предложений я бы выбрал #max, так как он кажется наиболее выразительным.

require 'benchmark'
N = 20
Benchmark.bm(30) do |r|
  past, now  = Time.local(2010, 2, 1, 0, 0, 0), Time.now
  @range = past...now
  r.report("range.max") do
    N.times { last_in_range = @range.max }
  end
  r.report("explicit enumeration") do
    N.times { @range.each { |value| last_in_range = value } }
  end
  r.report("range.entries.last") do
    N.times { last_in_range = @range.entries.last }
  end
  r.report("range.to_a[-1]") do
    N.times { last_in_range = @range.to_a[-1] }
  end
end
                                user     system      total        real
range.max                      49.406000   1.515000  50.921000 ( 50.985000)
explicit enumeration           52.250000   1.719000  53.969000 ( 54.156000)
range.entries.last             53.422000   4.844000  58.266000 ( 58.390000)
range.to_a[-1]                 49.187000   5.234000  54.421000 ( 54.500000)

Я заметил, что 3-й и 4-й вариант значительно увеличили системное время. Я ожидаю, что это связано с явным созданием массива, что кажется хорошей причиной избегать их, даже если за истекшее время они явно не дороже.

Answer 3

Я не уверен в скорости (и начальные тесты не кажутся невероятно быстрыми), но следующее может сделать то, что вам нужно:

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

range.to_a[-1]

Очень базовое тестирование (считая в моей голове)показал, что это заняло около 4 секунд, в то время как метод, который вы предоставили, занял около 5-6.Надеюсь, это поможет.

Редактировать 1: убрано второе решение, так как оно было полностью неверным.