I have a coding challenge to reverse a an array with 5 elements in it. How would I do this without using the reverse method?
Code:
def reverse(array)
array
end
p reverse(["a", 1, "apple", 8, 90])
可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):
问题:
回答1:
You can treat array as a stack and pop the elements from the end:
def reverse(array)
rev = []
rev << array.pop until array.empty?
rev
end
or if you don't like modifying objects, use more functional-like reduce:
def reverse(array)
array.reduce([]) {|acc, x| [x] + acc}
end
Cary mentioned in the comment about the performance. The functional approach might not be the fastest way, so if you really want to do it fast, create a buffor array and just add the items from the end to begin:
def reverse(array)
reversed = Array.new(array.count)
array.each_with_index do |item, index|
reversed[-(index + 1)] = item
end
reversed
end
回答2:
Gentlemen, start your engines!
[Edit: added two method from @Grych and results for n = 8_000.]
@Grych, @ArupRakshit, @konsolebox and @JörgWMittag: please check that I've written your method(s) correctly.
Methods
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
Benchmark
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
Wednesday: warm-up (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)
Thursday: trials #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 and jorg_tail eliminated (stack level too deep).
Friday: trials #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)
Saturday: qualifications (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 eliminated (stack level too deep); grych_reduce, jorg_fold and cary_rotate eliminated (uncompetitive).
Sunday: final (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)
回答3:
Recursion indeed is the solution if you're not going to use a loop. while or until is still a loop, and using built-in methods not doing recursion may also still be using a loop internally.
#!/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]
Update
Naturally recursion has limits since it depends on the stack but that's the best you can have if you don't want to use a loop. Following Cary Swoveland's post, this is the benchmark on 8500 elements:
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)
回答4:
One thought :-
ary = ["a", 1, "apple", 8, 90]
ary.values_at(*(ary.size-1).downto(0))
# => [90, 8, "apple", 1, "a"]
ary.size.downto(0) gives #<Enumerator: ...>. And *#<Enumerator: ...> is just a Enumerable#to_a method call which splats the Enumerator to [4, 3, 2, 1, 0]. Finally, Array#values_at is working as documented.
回答5:
The obvious solution is to use recursion:
def reverse(array)
return array if array.size < 2
reverse(array.drop(1)) + array.first(1)
end
We can make this tail-recursive using the standard accumulator trick:
def reverse(array, accum=[])
return accum if array.empty?
reverse(array.drop(1), array.first(1) + accum)
end
But of course, tail recursion is isomorphic to looping.
We could use a fold:
def reverse(array)
array.reduce([]) {|accum, el| [el] + accum }
end
But fold is equivalent to a loop.
def reverse(array)
array.each_with_object([]) {|el, accum| accum.unshift(el) }
end
Really, each_with_object is an iterator and it is the side-effectful cousin of fold, so there's actually two reasons why this is equivalent to a loop.
回答6:
Here's another non-destructive approach:
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]
Another would the most uninteresting method imaginable:
(arr.size-1).downto(0).with_object([]) { |i,a| a << arr[i] }
#=> [90, 8, "apple", 1, "a"]
arr
#=> ["a", 1, "apple", 8, 90]
回答7:
Konsolebox is right. If they are asking for the method without loops, that simply means that you cannot use any kind of loop whether it is map, each, while, until or any even built in methods that use loops, like length, size and count etc.
Everything needs to be recursive:
def recursive_reversal(array)
return array if array == [] # or array.empty?
last_element = array.pop
return [last_element, recursive_reversal(array)].flatten
end
Ruby uses recursion to flatten, so flatten will not entail any kind of loop.
回答8:
def reverse(array)
array.values_at(*((array.size-1).downto 0))
end
