在不使用ruby中的循环的情况下反转数组
我有一个编码挑战来反转一个包含5个元素的数组。 如果不使用反向方法，我该怎么做？
码：
def reverse(array) array end p reverse(["a", 1, "apple", 8, 90]) 您可以将数组视为堆栈并从末尾pop元素：
def reverse(array) rev = [] rev << array.pop until array.empty? rev end
或者如果您不喜欢修改对象，请使用更多function类似的reduce ：
def reverse(array) array.reduce([]) {|acc, x| [x] + acc} end
Cary在评论中提到了性能。 function方法可能不是最快的方法，所以如果你真的想快速完成它，创建一个buffor数组，只需从最后添加项目开始：
def reverse(array) reversed = Array.new(array.count) array.each_with_index do |item, index| reversed[-(index + 1)] = item end reversed end
如果你不打算使用循环，递归确实是解决方案。 while或者仍然是一个循环，并且使用不进行递归的内置方法也可能仍在内部使用循环。
#!/usr/bin/env ruby a = [1, 2, 3] def reverse(array) t = array.pop reverse(array) if array.length > 0 array.unshift t end puts reverse(Array.new(a)).inspect # [3, 2, 1]
更新
自然递归有限制，因为它取决于堆栈，但如果你不想使用循环，这是你可以拥有的最好的。 继Cary Swoveland的post之后 ，这是8500元素的基准：
user system total real @Grych 0.060000 0.010000 0.070000 ( 0.073179) @ArupRakshit 0.000000 0.000000 0.000000 ( 0.000836) @konsolebox 0.000000 0.000000 0.000000 ( 0.001771) @JörgWMittag recursion 0.050000 0.000000 0.050000 ( 0.053475) @Jörg tail 0.210000 0.040000 0.250000 ( 0.246849) @Jörg fold 0.040000 0.010000 0.050000 ( 0.045788) @Jörg loop 0.000000 0.000000 0.000000 ( 0.000924) Cary rotate 0.060000 0.000000 0.060000 ( 0.059954) Cary boring 0.000000 0.000000 0.000000 ( 0.001004)
先生们，启动你的引擎吧！
[编辑：从@Grych添加两个方法，结果为n = 8_000。]
@Grych，@ ArupRakshit，@ konsolebox和@JörgWMittag：请检查我是否正确编写了您的方法。
方法
def grych_reduce(array) array.reduce([]) {|acc, x| [x] + acc} end def grych_prebuild(array) reversed = Array.new(array.count) array.each_with_index do |item, index| reversed[-(index + 1)] = item end reversed end def arup(ary) ary.values_at(*(ary.size-1).downto(0)) end def konsolebox(array) t = array.pop konsolebox(array) if array.length > 0 array.unshift t end def jorg_recurse(array) return array if array.size < 2 reverse(array.drop(1)) + array.first(1) end def jorg_tail(array, accum=[]) return accum if array.empty? reverse(array.drop(1), array.first(1) + accum) end def jorg_fold(array) array.reduce([]) {|accum, el| [el] + accum } end def jorg_loop(array) array.each_with_object([]) {|el, accum| accum.unshift(el) } end def cary_rotate(arr) arr.size.times.with_object([]) { |_,a| a << arr.rotate!(-1).first } end def cary_boring(arr) (arr.size-1).downto(0).with_object([]) { |i,a| a << arr[i] } end
基准
require 'benchmark' arr = [*(1..n)] puts "n = #{n}" Benchmark.bm(16) do |bm| bm.report('grych_reduce') { grych_reduce(arr) } bm.report('grych_prebuild') { grych_prebuild(arr) } bm.report('arup') { arup(arr) } bm.report('konsolebox') { konsolebox(arr) } bm.report('jorg_recurse') { jorg_recurse(arr) } bm.report('jorg_tail') { jorg_tail(arr) } bm.report('jorg_fold') { jorg_fold(arr) } bm.report('jorg_loop') { jorg_loop(arr) } bm.report('cary_rotate') { cary_rotate(arr) } bm.report('cary_boring') { cary_boring(arr) } bm.report('grych_destructo') { grych_destructo(arr) } end
星期三：热身（n = 8_000）
user system total real grych_reduce 0.060000 0.060000 0.120000 ( 0.115510) grych_prebuild 0.000000 0.000000 0.000000 ( 0.001150) arup 0.000000 0.000000 0.000000 ( 0.000563) konsolebox 0.000000 0.000000 0.000000 ( 0.001581) jorg_recurse 0.060000 0.040000 0.100000 ( 0.096417) jorg_tail 0.210000 0.070000 0.280000 ( 0.282729) jorg_fold 0.060000 0.080000 0.140000 ( 0.138216) jorg_loop 0.000000 0.000000 0.000000 ( 0.001174) cary_rotate 0.060000 0.000000 0.060000 ( 0.056863) cary_boring 0.000000 0.000000 0.000000 ( 0.000961) grych_destructo 0.000000 0.000000 0.000000 ( 0.000524)
星期四：试验＃1（n = 10_000）
user system total real grych_reduce 0.090000 0.080000 0.170000 ( 0.163276) grych_prebuild 0.000000 0.000000 0.000000 ( 0.001500) arup 0.000000 0.000000 0.000000 ( 0.000706) jorg_fold 0.080000 0.060000 0.140000 ( 0.139656) jorg_loop 0.000000 0.000000 0.000000 ( 0.001388) cary_rotate 0.090000 0.000000 0.090000 ( 0.087327) cary_boring 0.000000 0.000000 0.000000 ( 0.001185) grych_destructo 0.000000 0.000000 0.000000 ( 0.000694)
konsolebox ， jorg_recurse和jorg_tail消除了（堆栈级别太深）。
星期五：试验＃2（n = 50_000）
user system total real grych_reduce 2.430000 3.490000 5.920000 ( 5.920393) grych_prebuild 0.010000 0.000000 0.010000 ( 0.007000) arup 0.000000 0.000000 0.000000 ( 0.003826) jorg_fold 2.430000 3.590000 6.020000 ( 6.026433) jorg_loop 0.010000 0.010000 0.020000 ( 0.008491) cary_rotate 2.680000 0.000000 2.680000 ( 2.686009) cary_boring 0.010000 0.000000 0.010000 ( 0.006122) grych_destructo 0.000000 0.000000 0.000000 ( 0.003288)
星期六：资格（n = 200_000）
user system total real grych_reduce 43.720000 66.140000 109.860000 (109.901040) grych_prebuild 0.030000 0.000000 0.030000 ( 0.028287) jorg_fold 43.700000 66.490000 110.190000 (110.252620) jorg_loop 0.030000 0.010000 0.040000 ( 0.030409) cary_rotate 43.060000 0.050000 43.110000 ( 43.118151) cary_boring 0.020000 0.000000 0.020000 ( 0.024570) grych_destructo 0.010000 0.000000 0.010000 ( 0.013338)
消除了arup_verse （堆栈级别太深）; grych_reduce ， jorg_fold和cary_rotate淘汰（没有竞争力）。
周日：决赛（n = 10_000_000）
user system total real grych_prebuild 1.450000 0.020000 1.470000 ( 1.478903) jorg_loop 1.530000 0.040000 1.570000 ( 1.649403) cary_boring 1.250000 0.040000 1.290000 ( 1.288357) grych_destructo 0.640000 0.030000 0.670000 ( 0.689819)
一想法： –
ary = ["a", 1, "apple", 8, 90] ary.values_at(*(ary.size-1).downto(0)) # => [90, 8, "apple", 1, "a"]
ary.size.downto(0)给出# 。 并且*#只是一个Enumerable#to_a方法调用，它将Enumerator Enumerable#to_a为[4, 3, 2, 1, 0] Enumerable#to_a [4, 3, 2, 1, 0] 。 最后， Array#values_at正如记录的 Array#values_at工作。
显而易见的解决方案是使用递归：
def reverse(array) return array if array.size < 2 reverse(array.drop(1)) + array.first(1) end
我们可以使用标准累加器技巧使这个尾递归：
def reverse(array, accum=[]) return accum if array.empty? reverse(array.drop(1), array.first(1) + accum) end
但是当然，尾递归与循环同构。
我们可以使用折叠：
def reverse(array) array.reduce([]) {|accum, el| [el] + accum } end
但折叠等同于循环。
def reverse(array) array.each_with_object([]) {|el, accum| accum.unshift(el) } end
实际上， each_with_object是一个迭代器，它是fold的副作用表兄弟，所以实际上有两个原因可以解释为什么这相当于一个循环。
这是另一种非破坏性的方法：
arr = ["a", 1, "apple", 8, 90] arr.size.times.with_object([]) { |_,a| a << arr.rotate!(-1).first } #=> [90, 8, "apple", 1, "a"] arr #=> ["a", 1, "apple", 8, 90]
另一个是可以想象的最无趣的方法：
(arr.size-1).downto(0).with_object([]) { |i,a| a << arr[i] } #=> [90, 8, "apple", 1, "a"] arr #=> ["a", 1, "apple", 8, 90]
Konsolebox是对的。 如果他们要求没有循环的方法，那只是意味着你不能使用任何类型的循环，无论是map，each，while，until，甚至任何甚至内置的使用循环的方法，如长度，大小和计数等。
一切都需要递归：
def recursive_reversal(array) return array if array == [] # or array.empty? last_element = array.pop return [last_element, recursive_reversal(array)].flatten end
Ruby使用递归来展平，因此展平不会引起任何类型的循环。
def reverse(array) array.values_at(*((array.size-1).downto 0)) end