Eeep. Seems I never actually sent this email... I hate it when I do
that....
It bugged me that my fancy new algorithym wasn't faster than the old
one, so I MADE it faster, goddammit. This beats out the
facets/array/each_permutation by 6-60%, depending on array size. The
second method seems to run slightly faster than the first, but they're
really much of a muchness, and the first is a lot more readable. I think
I was wrong about the difference in memory usage between my solutions
and facets - I don't think memory usage is an advantage here. I think
the advantage here is that this method is not recursive, so it's not
prone to stack overflows, and (now) it's faster.
This is my favourite - it's fastest, and displays the permutations in
the 'correct' order (ie, the first permutation of the first permutation
is equal to the second permutation of the original).
def each_permutation_new3()
pos = Array.new(size) {|i| i}
s = (0...size).to_a.reverse
out = nil
while true
out = []
pos.each_with_index {|p,i| out.insert(p, self[i]) }
yield out
break if s.each { |i|
break if pos[i] > 0 && pos[i] -= 1
pos[i] = i
}
end
end
Benchmarks against the old method for doing permutations on arrays up to
size 9:
user system total real
old 2x100000: 4.328000 0.016000 4.344000 ( 4.438000)
new3 2x100000: 4.172000 0.031000 4.203000 ( 4.234000)
···
--
old 3x10000: 1.765000 0.000000 1.765000 ( 1.828000)
new3 3x10000: 1.172000 0.000000 1.172000 ( 1.219000)
--
old 4x2000: 1.610000 0.016000 1.626000 ( 1.641000)
new3 4x2000: 1.062000 0.000000 1.062000 ( 1.062000)
--
old 5x1000: 4.328000 0.031000 4.359000 ( 4.438000)
new3 5x1000: 2.985000 0.016000 3.001000 ( 3.078000)
--
old 6x200: 5.406000 0.046000 5.452000 ( 5.687000)
new3 6x200: 4.187000 0.032000 4.219000 ( 4.297000)
--
old 7x50: 10.016000 0.109000 10.125000 ( 10.422000)
new3 7x50: 8.125000 0.031000 8.156000 ( 8.375000)
--
old 8x20: 32.812000 0.063000 32.875000 ( 33.344000)
new3 8x20: 29.016000 0.203000 29.219000 ( 29.766000)
--
old 9x2: 30.594000 0.172000 30.766000 ( 31.375000)
new3 9x2: 28.844000 0.140000 28.984000 ( 29.406000)
(Benchmarks for higher array sizes are left as an exercise for the
reader's supercomputer).
#####################################################################################
This email has been scanned by MailMarshal, an email content filter.
#####################################################################################
