On Tue, Jul 1, 2008 at 11:29 AM, Max W.
[email protected] wrote:
jim finucane wrote:
Jim, this wins the elegance prize i think! It’s almost magical…i
can’t quite get my head round it.
It runs into biiig performance issues for n >> size, and worse it does
not use inject
look at these benchmarks
==================================
require ‘benchmark’
def robert n, size
(1…n).inject([[]]){
|perms, ele|
perms.concat( perms.map{|perm| perm+[ele]} ).
uniq.delete_if{|p| p.size > size}
}
end
def jim n, size
result = [[]]
for i in 1…n
result +=result.collect{|x| x.length<size ? x +=[i] : [] }
end
result.uniq - [[]]
end
N,S,R = ARGV.map{|x| x.to_i}
Benchmark::bmbm do | report |
report.report(“robert”) do
R.times do
robert N, S
end
end
report.report(“jim”) do
R.times do
jim N, S
end
end
end
528/28 > ruby perms.rb 4 2 10000
Rehearsal ------------------------------------------
robert 1.328000 0.032000 1.360000 ( 1.359000)
jim 1.000000 0.015000 1.015000 ( 1.016000)
--------------------------------- total: 2.375000sec
user system total real
robert 1.344000 0.032000 1.376000 ( 1.375000)
jim 1.016000 0.031000 1.047000 ( 1.047000)
529/29 > ruby perms.rb 10 2 100
Rehearsal ------------------------------------------
robert 0.141000 0.000000 0.141000 ( 0.141000)
jim 0.484000 0.016000 0.500000 ( 0.500000)
--------------------------------- total: 0.641000sec
user system total real
robert 0.141000 0.000000 0.141000 ( 0.141000)
jim 0.453000 0.000000 0.453000 ( 0.453000)
530/30 > ruby perms.rb 20 2 10
Rehearsal ------------------------------------------
robert 0.125000 0.000000 0.125000 ( 0.125000)
jim 53.922000 0.656000 54.578000 ( 54.610000)
-------------------------------- total: 54.703000sec
user system total real
robert 0.140000 0.000000 0.140000 ( 0.141000)
jim 57.750000 0.531000 58.281000 ( 58.297000)
of course if n and size are large there is not much that can be done
on the exponential runtime
as O(n!) is just O(e**n)
531/31 > ruby perms.rb 20 15 1
Rehearsal ------------------------------------------
robert 95.469000 0.312000 95.781000 ( 95.890000)
jim 95.703000 0.266000 95.969000 ( 96.219000)
------------------------------- total: 191.750000sec
user system total real
robert 95.422000 0.281000 95.703000 ( 96.141000)
jim 91.843000 0.172000 92.015000 ( 92.141000)
HTH
Robert
–
http://ruby-smalltalk.blogspot.com/
AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF