将Ruby数组根据其中的连续元素分块

Question

摘要： 这里的基本问题是，我已经发现，是否可以将代码块传递给一个Ruby数组，它实际上会将该数组的内容减少到另一个数组，而不是单个值（ inject 的方式）。简短的答案是“否”。

我接受了这个答案。感谢Squeegy提供了一个很好的循环策略来从数组中获取连续的元素。

挑战： 在不显式地循环遍历数组的情况下减少数组的元素。
输入： 所有从-10到10的整数（除0外）随机排序。
期望输出： 代表正数或负数连续出现的数组。例如，-3表示三个连续的负数。2表示两个连续的正数。

示例脚本：

original_array = (-10..10).to_a.sort{rand(3)-1}
original_array.reject!{|i| i == 0} # remove zero

streaks = (-1..1).to_a # this is a placeholder.  
# The streaks array will contain the output.
# Your code goes here, hopefully without looping through the array

puts "Original Array:"
puts original_array.join(",")
puts "Streaks:"
puts streaks.join(",")
puts "Streaks Sum:"
puts streaks.inject{|sum,n| sum + n}

样例输出:

Original Array:
3,-4,-6,1,-10,-5,7,-8,9,-3,-7,8,10,4,2,5,-2,6,-1,-9
Streaks:
1,-2,1,-2,1,-1,1,-2,5,-1,1,-2
Streaks Sum:
0


Original Array:
-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9,10
Streaks:
-10,10
Streaks Sum:
0

请注意以下几点：

• streaks数组具有交替的正负值。
• streaks数组元素之和始终为0（原始数组之和也是如此）。
• streak数组绝对值之和始终为20。

希望这很清楚！

编辑：我确实意识到像reject!这样的构造实际上在后台循环遍历数组。我不排除循环遍历是因为我是一个刻薄的人。只是想了解这种语言。如果需要显式迭代，那没问题。

- Rich Armstrong

---

为什么不遍历数组呢？你打算如何处理数组的内容而不通过循环来实现。即使你使用某个方法来完成这个过程，它内部仍然会进行循环遍历数组。 - Alex Wayne

你应该意识到你代码示例中调用的每个方法实际上都在循环遍历数组... - kgrad

没错，没有循环遍历数组就无法对其进行缩减...因为无法访问内容。 - cdmckay

我认为他想要一种优雅的方式，其中循环被抽象成更有意义和更简单的东西。这是关于优雅代码的问题，而不是大O符号。 - Iraimbilanja

然后扩展Array，添加一个执行此操作的方法。Ruby中没有内置的方法可以完成所有这些操作。 - Alex Wayne

如果你只是想隐藏循环，那么如何在方法中调用隐藏了循环的方法呢？根据我的经验，“优雅”的设计几乎总是会导致更糟糕的结果——这些天每当我听到这个词时，我都会感到不安。 - Bill K

Answer 1

好的，如果您更喜欢一行版本，这里是一个：

streaks = original_array.inject([]) {|a,x| (a.empty? || x * a[-1] < 0 ? a << 0 : a)[-1] += x <=> 0; a}

如果使用inject还是太复杂了，这里有一种非常愚蠢的方法:

  streaks = eval "[#{original_array.join(",").gsub(/((\-\d+,?)+|(\d+,?)+)/) {($1[0..0] == "-" ? "-" : "") + $1.split(/,/).size.to_s + ","}}]"

但我认为很明显，你最好采用更加简单明了的方法：

streaks = []
original_array.each do |x|
  xsign = (x <=> 0)
  if streaks.empty? || x * streaks[-1] < 0
    streaks << xsign
  else
    streaks[-1] += xsign
  end
end

除了更易于理解和维护外，"循环"版本的运行时间大约是注入版本的三分之二，并且是评估/正则表达式版本的六分之一。

附注：这里还有一个可能有趣的版本：

a = [[]]
original_array.each do |x|
  a << [] if x * (a[-1][-1] || 0) < 0
  a[-1] << x
end
streaks = a.map {|aa| (aa.first <=> 0) * aa.size}

这种方法需要两个步骤，首先建立一个区间数组的数组，然后将数组的数组转换为一个带符号大小的数组。在Ruby 1.8.5中，这比上面的注入版本略快（虽然在Ruby 1.9中稍慢），但无聊的循环仍然是最快的。

- glenn mcdonald

---

可以加上一两个注释。我知道你已经解释过了，但在代码中添加注释是经常被忽视的事情。 - Greg M. Krsak

Answer 2

new_array = original_array.dup
<Squeegy's answer, using new_array>

咔嚓！不需要循环原始数组。虽然在dup内部有一个MEMCPY，但我想在汇编级别上可能被认为是一个循环？

http://www.ruby-doc.org/doxygen/1.8.4/array_8c-source.html

编辑： ;)

- Sarah Mei

Answer 3

original_array.each do |num|
  if streaks.size == 0
    streaks << num
  else
    if !((streaks[-1] > 0) ^ (num > 0))
      streaks[-1] += 1
    else
      streaks << (num > 0 ? 1 : -1)
    end
  end
end

这里的魔法在于使用了“^”异或运算符。

true ^ false  #=> true
true ^ true   #=> false
false ^ false #=> false

如果数组中的最后一个数字与正在处理的数字在零的同侧，则将其添加到连续序列中，否则将其添加到连续序列数组中以开始新的连续序列。请注意，由于 true ^ true 返回 false，我们必须否定整个表达式。

- Squeegy

---

这个看起来不正确。你是在计数还是求和？ - jcrossley3

哎呀，我有点误解了。这个是对“连续值”的求和，而不是计数。你是对的。我会把它修正的。 - Alex Wayne

谢谢！这很有帮助。异或的解决方案非常好。即使我接受了另一个答案，我还是投了你的赞 :) - Rich Armstrong

Answer 4

更多的字符串滥用，就像Glenn McDonald一样，只是不同：

runs = original_array.map do |e|
  if e < 0
    '-'
  else
    '+'
  end
end.join.scan(/-+|\++/).map do |t|
  "#{t[0..0]}#{t.length}".to_i
end

p original_array
p runs
# => [2, 6, -4, 9, -8, -3, 1, 10, 5, -7, -1, 8, 7, -2, 4, 3, -5, -9, -10, -6]
# => [2, -1, 1, -2, 3, -2, 2, -1, 2, -4]

- Wayne Conrad

Answer 5

自 Ruby 1.9 版本以来，有一种更简单的方法来解决这个问题：

original_array.chunk{|x| x <=> 0 }.map{|a,b| a * b.size }

Enumerable.chunk会通过块的输出将数组中所有连续的元素分组在一起：

>> original_array.chunk{|x| x <=> 0 }
=> [[1, [3]], [-1, [-4, -6]], [1, [1]], [-1, [-10, -5]], [1, [7]], [-1, [-8]], [1, [9]], [-1, [-3, -7]], [1, [8, 10, 4, 2, 5]], [-1, [-2]], [1, [6]], [-1, [-1, -9]]]

这几乎就是 OP 所要求的，除了需要对结果分组计数以获得最终的 streaks 数组。

- user12341234

---

谢谢！这正是我最初要寻找的。 - Rich Armstrong