Как разбить массив на условие на смежные элементы на ограниченное количество разделов

Ответ 1

Еще одна альтернатива:

index = ary.each_cons(2).find_index { |i, j| i > j }
[ary[0..index], ary[index + 1..-1]]
#=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

Я считаю, что пространство O (n) и время O (n)

Benchmark:

Warming up --------------------------------------
             anthony    63.941k i/100ms
             steve_t    98.000  i/100ms
              tadman   123.000  i/100ms
              sergio    75.477k i/100ms
               hoffm   101.000  i/100ms
Calculating -------------------------------------
             anthony    798.456k (± 4.0%) i/s -      4.028M in   5.053175s
             steve_t    985.736  (± 5.0%) i/s -      4.998k in   5.083188s
              tadman      1.229k (± 4.1%) i/s -      6.150k in   5.010877s
              sergio    948.357k (± 3.7%) i/s -      4.755M in   5.020931s
               hoffm      1.013k (± 2.9%) i/s -      5.151k in   5.089890s

Comparison:
              sergio:   948357.4 i/s
             anthony:   798456.2 i/s - 1.19x  slower
              tadman:     1229.5 i/s - 771.35x  slower
               hoffm:     1012.9 i/s - 936.30x  slower
             steve_t:      985.7 i/s - 962.08x  slower

для эталона:

require 'benchmark/ips'

def anthony(ary)
  index = ary.each_cons(2).find_index { |i, j| i > j }
  [ary[0..index], ary[index + 1..-1]]
end

def steve_t(ary)
  break_done = false
  ary.slice_when { |i, j| (break_done = i > j) unless break_done }.to_a
end

def tadman(ary)
  ary.each_with_object([[],[]]) do |v, a|
    a[a[1][-1] ? 1 : (a[0][-1]&.>(v) ? 1 : 0)] << v
  end
end

def sergio(ary)
  break_point = ary.each_cons(2).with_index do |(a, b), idx|
    break idx if b < a # plug your block here
  end + 1

  [
    ary.take(break_point),
    ary.drop(break_point)
  ]
end

def split(ary)
  split_done = false
  ary.chunk_while do |i, j|
    split_done || !(split_done = yield(i, j))
  end.to_a
end

def hoffm(ary)
  split(ary) { |i, j| i > j }
end

ary = Array.new(10_000) { rand(1..100) }
Benchmark.ips do |x|
  # Configure the number of seconds used during
  # the warmup phase (default 2) and calculation phase (default 5)
  x.config(:time => 5, :warmup => 2)

  # Typical mode, runs the block as many times as it can
  x.report("anthony") { anthony(ary) }
  x.report("steve_t") { steve_t(ary) }
  x.report("tadman") { tadman(ary) }
  x.report("sergio") { sergio(ary) }
  x.report("hoffm") { hoffm(ary) }

    # Compare the iterations per second of the various reports!
  x.compare!
end

Увлекательно, что #take и #drop из ответа @sergio немного быстрее, чем Array#[range..range], они оба используют один и тот же метод c, поэтому я не могу его объяснить.

Ответ 2

Вероятно, лучший способ сделать это, но моя первая мысль...

break_done = false
ary.slice_when { |i, j| (break_done = i > j) unless break_done }.to_a
#=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

Ответ 3

Я не уверен, что вы найдете это более изящным, но он предотвращает маневр раскола и воссоединения:

def split(ary)
  split_done = false
  ary.slice_when do |i, j|
    !split_done && (split_done = yield(i, j))
  end.to_a
end

Использование:

ary = [1, 3, 6, 7, 10, 9, 11, 13, 7, 24]    
split(ary){ |i, j| i > j }
#=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

Обновление

Некоторые могут найти этот вариант более читабельным. #chunk_while является обратным к #split_when, а затем я просто применил закон Де Моргана к блоку.

def split(ary)
  split_done = false
  ary.chunk_while do |i, j|
    split_done || !(split_done = yield(i, j))
  end.to_a
end

Ответ 4

Здесь другая версия. Не особенно элегантный или эффективный, но достаточно эффективен (см. Комментарии).

break_point = ary.each_cons(2).with_index do |(a, b), idx|
  break idx if b < a # plug your block here
end + 1

[
  ary.take(break_point), 
  ary.drop(break_point)
] # => [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

Ответ 5

Это не должно быть такой трудной проблемой, как это доказывает. slice_when не принимает максимальное количество срезов в качестве аргумента, но если это было бы легко,

Здесь один оптимизирован вокруг двух разделов:

def slice_into_two(ary)
  ary.each_with_object([[],[]]) do |v, a|
    a[a[1][-1] ? 1 : (a[0][-1]&.>(v) ? 1 : 0)] << v
  end
end

Ответ 6

Первый подход

Просто подумал, что я опубликую этот путь, перечислитель в перечислителе, создающий раздел. Первая ветвь if (как и другие, такие как тадман) реализована в случае пустого массива.

arr = [1, 3, 6, 7, 10, 9, 11, 13, 7, 24]

Enumerator.new { |y|
  if arr.empty?
    y << []
  else
    enum = arr.each
    a = enum.next

    #collect elements until rule is broken
    arr1 = loop.with_object([a]) { |_,o|
      break o if enum.peek < a
      o << a = enum.next
    }

    #collect remainder of elements
    arr2 = loop.with_object([]) { |_,o| o << enum.next }

    #incase the rule is never met; just return arr elements
    arr2 == [] ? arr.each { |e| y << e } : y << arr1; y << arr2

}.entries

#=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

Второй подход

Это несколько получается из подхода тадмана, то есть раздел предопределен и опустошен и заполнен соответствующим образом.

arr = [1, 3, 6, 7, 10, 9, 11, 13, 7, 24]

loop.with_object([[],arr.dup]) { |_,o|
  if o.last == []
    break o
  elsif o.last[0] < o.last[1]
    o.first << o.last.shift
  else
    o.first << o.last.shift
    break o
  end
}

#=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

Цитирование через массив (хотя и дубликат), возвращающий секционированный массив, как только правило прерывается.

Ответ 7

first, *last = ary
first = [first]
while last.any? && first.last <= last.first do
  first << last.shift 
end
[first, last]
  #=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

По-другому:

f = ary.lazy.slice_when { |i, j| i > j }.first
  #=> [1, 3, 6, 7, 10] 
[f, ary[f.size..-1]]
  #=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]