On Sun, Jul 18, 2010 at 11:32 AM, Carson <c.sci.b...@gmail.com> wrote: > I guess different people see things differently. I actually didn't > understand the intent of the imperative version, even though it takes > less lines I guess. There's quite a few things called convolution. > My naive implementation was functional and pretty fast. Turns out it > can be even faster with just a little work (still functional): > > (defn point-convolve [n ^doubles fs ^doubles gs] > (let [window-size (alength fs) > padding (repeat window-size 0.0) > padded-gs (concat padding gs padding) > window-of-gs (double-array (subvec (vec padded-gs) > (inc n) > (inc (+ n window-size)))) > reverse-window-fn (fn [i] (aget window-of-gs > (mod (- -1 i) window-size))) > reverse-window (map reverse-window-fn (range window-size))] > (reduce + (map * fs reverse-window)))) > > (defn convolve [^doubles fs ^doubles gs] > (map #(point-convolve % fs gs) > (range (+ (alength fs) (alength gs))))) > > (let [dxs (double-array (for [i (range 3000000)] (rand 100))) > dys (double-array (for [i (range 3000000)] (rand 100)))] > (time (dotimes [_ 10] (convolve dxs dys)))) > > "Elapsed time: 0.506432 msecs"
How about some common sense? The convolution algorithm everyone is discussing runs in O(n m) time. So your measured time would imply that a single of your computer's core is capable of 10 * 3,000,000^2 = 9 * 10^14 FLOPS, or about one peta-FLOPS. That should have tipped you off you aren't actually measuring anything useful. Wrap your (convolve dxs dys) calls with (doall ...). And you will want to reduce the three million number to something much smaller, or you'll be waiting for a very long time. By the way, no-one actually uses this quadratic-time algorithm for very wide kernels. For that you use FFTs and pointwise multiplication (look up the convolution theorem), which yields an O(n log n) algorithm. -Per -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
