如何通过相邻元素上的条件将数组拆分为有限数量的分区

Question

假设我有一系列数字,例如

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

我想在第一个点之间拆分数组,其中较小的数字跟随较大的数字.我的输出应该是:

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

我试过了slice_when,它非常接近:

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

但它也在13和之间分裂7,所以我必须加入其余的数组:

first, *rest = ary.slice_when { |i, j| i > j }.to_a
[first, rest.flatten(1)]
#=> [[1, 3, 6, 7, 10], [9, 11, 13, 7, 24]]

这看起来有点麻烦.在找到匹配项后继续比较项目似乎效率低下.

我正在寻找基于任意条件的通用解决方案.有数字元素,i > j只是一个例子.

有没有更好的方法来解决这个问题？

Answer 1

可能有更好的方法来做到这一点,但我的第一个想法是......

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]]

Answer 2

我不确定你会发现这更优雅,但它会阻止分裂和重新加入的机动:

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然后我只是将De Morgan定律应用于块.

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

Answer 3

另一种选择：

\n\n

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

\n\n

我相信空间是 O(n) 时间是 O(n)

\n\n

基准：

\n\n

Warming up --------------------------------------\n             anthony    63.941k i/100ms\n             steve_t    98.000  i/100ms\n              tadman   123.000  i/100ms\n              sergio    75.477k i/100ms\n               hoffm   101.000  i/100ms\nCalculating -------------------------------------\n             anthony    798.456k (\xc2\xb1 4.0%) i/s -      4.028M in   5.053175s\n             steve_t    985.736  (\xc2\xb1 5.0%) i/s -      4.998k in   5.083188s\n              tadman      1.229k (\xc2\xb1 4.1%) i/s -      6.150k in   5.010877s\n              sergio    948.357k (\xc2\xb1 3.7%) i/s -      4.755M in   5.020931s\n               hoffm      1.013k (\xc2\xb1 2.9%) i/s -      5.151k in   5.089890s\n\nComparison:\n              sergio:   948357.4 i/s\n             anthony:   798456.2 i/s - 1.19x  slower\n              tadman:     1229.5 i/s - 771.35x  slower\n               hoffm:     1012.9 i/s - 936.30x  slower\n             steve_t:      985.7 i/s - 962.08x  slower\n

\n\n

基准测试代码：

\n\n

require \'benchmark/ips\'\n\ndef anthony(ary)\n  index = ary.each_cons(2).find_index { |i, j| i > j }\n  [ary[0..index], ary[index + 1..-1]]\nend\n\ndef steve_t(ary)\n  break_done = false\n  ary.slice_when { |i, j| (break_done = i > j) unless break_done }.to_a\nend\n\ndef tadman(ary)\n  ary.each_with_object([[],[]]) do |v, a|\n    a[a[1][-1] ? 1 : (a[0][-1]&.>(v) ? 1 : 0)] << v\n  end\nend\n\ndef sergio(ary)\n  break_point = ary.each_cons(2).with_index do |(a, b), idx|\n    break idx if b < a # plug your block here\n  end + 1\n\n  [\n    ary.take(break_point),\n    ary.drop(break_point)\n  ]\nend\n\ndef split(ary)\n  split_done = false\n  ary.chunk_while do |i, j|\n    split_done || !(split_done = yield(i, j))\n  end.to_a\nend\n\ndef hoffm(ary)\n  split(ary) { |i, j| i > j }\nend\n\nary = Array.new(10_000) { rand(1..100) }\nBenchmark.ips do |x|\n  # Configure the number of seconds used during\n  # the warmup phase (default 2) and calculation phase (default 5)\n  x.config(:time => 5, :warmup => 2)\n\n  # Typical mode, runs the block as many times as it can\n  x.report("anthony") { anthony(ary) }\n  x.report("steve_t") { steve_t(ary) }\n  x.report("tadman") { tadman(ary) }\n  x.report("sergio") { sergio(ary) }\n  x.report("hoffm") { hoffm(ary) }\n\n    # Compare the iterations per second of the various reports!\n  x.compare!\nend\n

\n\n

令人着迷的是，#take@ #dropsergio\'s 的答案比 稍快Array#[range..range]，它们都在下面使用相同的 c 方法，所以我无法解释它。

\n