def haar_1d(a)
r = []
(Math.log(a.length) / Math.log(2) - 1).to_i.downto(0) { |j|
as = []
ad = []
(1 << j).times { |k|
u = 2 * k
au = a[u] * 0.5
av = a[u + 1] * 0.5
as << au + av
ad << au - av
}
a = as
r = ad + r
}
a + r
end
Refactorings
No refactoring yet !
danielharan
January 26, 2009, January 26, 2009 04:31, permalink
Oy, I'd want unit tests before I tried a major refactoring. And benchmarking before any real optimizations.
The main thing that jumps out is on lines 8-9, where it seems computations are repeated?
def haar_1d(a)
r = []
(Math.log(a.length) / Math.log(2) - 1).to_i.downto(0) { |j|
as = []
ad = []
a_halved = a.collect {|e| e * 0.5 }
(1 << j).times { |k|
u = 2 * k
au = a_halved[u]
av = a_halved[u + 1]
as << au + av
ad << au - av
}
a = as
r = ad + r
}
a + r
end
data.map.myopenid.com
January 27, 2009, January 27, 2009 21:49, permalink
Thanks for your help, but after running some benchmarking it appears your code is a bit slower. Both methods produce the correct output, so any arbitrary data will do. I suppose this is what you mean by unit tests (correct me if I'm wrong):
def assert(bool, msg)
raise "Assertion failed: #{msg}" unless bool
end
tests = [
["constant signal", [ 5, 5, 5, 5 ], [ 5, 0, 0, 0 ]],
["simple", [ 1, 0, 1, 0 ], [ 0.5, 0.0, 0.5, 0.5 ]],
["longer", [ 0, 1, 2, 10, 2, 1, 0, 0 ], [ 2.0, 1.25, -2.75, 0.75, -0.5, -4.0, 0.5, 0.0 ]],
["complex", [ 50, 20, 90, 40, 5, 60, 35, 80 ], [ 47.5, 2.5, -15.0, -12.5, 15.0, 25.0, -27.5, -22.5 ]],
["short", [ 4, 2, 5, 5 ], [ 4.0, -1.0, 1.0, 0.0 ]]
]
tests.each_with_index { |test, index|
assert(haar_1d(test[1]) == test[2], "Test #{index + 1} (#{test[0]})")
}
puts "Tests passed!"
require 'benchmark'
array = (1..(1<<7)).map { rand }
n = 20000
Benchmark.bm do |x|
x.report { n.times { haar_1d(array) } }
end
Diego Nieto Cid
January 30, 2009, January 30, 2009 03:22, permalink
Im really sorry for the funny functions but Im afraid I cannot write proper ruby code. Could you please try the sugested change? The amount of multiplications is halved, so it should be a little faster, but probably not much faster.
Also the "Fast Haar Transform" is fast because averages and differences are not sorted on each step. Computations are written inplace ( a[u] <- av, a[u+1] <- diff ). You have to adjust the step of the iteration and the location the "even" input for each level of the transform.
Like this:
level 0: step=+2, even=+1
level n: step=step(n-1)*2, even=even(n-1)*2
Regards
def trythis(dummy)
au = a[u]
av = (au + a[u + 1]) * 0.5
as << av
ad << au - av
end
def insteadof(dummy)
au = a[u]* 0.5
av = a[u + 1] * 0.5
as << au + av
ad << au - av
end
data.map.myopenid.com
January 30, 2009, January 30, 2009 22:21, permalink
This is a good improvement! Thanks for the explanation. I will continue to experiment with rewriting the logic to squeeze some extra speed from it.
I was reading about an algorithm that processes 4 values at a time (instead of 2). Here's the link:
http://www.waset.org/pwaset/v26/v26-96.pdf
Anyone want to translate this to ruby? :)
Anyone want to help me optimize this algorithm for speed? I know that C would probably be the quickest, but I wanted to try something easy while I'm learning about image processing. This code is as far as I got without major logic restructuring. Input is a one-dimensional array of 2^n length.
Edit: L's looked too similar to 1's.