Geo <[email protected]> writes:
> I am cross-posting my Clojure question from StackOverflow. I am trying to
> get an algorithm in Clojure to match Java speed and managed to get the
> performance to within one order of magnitude and wondering if more is
> possible. The full question is here:
>
> http://stackoverflow.com/questions/14949705/clojure-performance-for-expensive-algorithms
So, I was curious about this. So, you've done everything using java
arrays. What would happen if you used clojure data structures.
So I tried this instead.
(defn lcs-native
[n1 n2]
(let [n1-len (count n1)
n2-len (count n2)
prev {}
curr {}]
(loop [i 0 max-len 0 prev prev curr curr]
(if (< i n1-len)
(recur (inc i)
(loop [j 0 max-len max-len]
(if (< j n2-len)
(if (= (nth n1 i) (nth n2 j))
(let [match-len (inc (get prev j 0))]
(do
(assoc curr (inc j) match-len)
(recur (inc j) (max max-len match-len))))
(do
(assoc curr (inc j) 0)
(recur (inc j) max-len)))
max-len))
curr
prev)
max-len))))
This is slower, but interesting only by about 1/3 which is less than you
might have thought, assuming I have got the code correct.
Perhaps, then, using transients would speed things up.
(defn lcs-native-transient
[n1 n2]
(let [n1-len (count n1)
n2-len (count n2)
prev (transient {})
curr (transient {})]
(loop [i 0 max-len 0 prev prev curr curr]
(if (< i n1-len)
(recur (inc i)
(loop [j 0 max-len max-len]
(if (< j n2-len)
(if (= (nth n1 i) (nth n2 j))
(let [match-len (inc (get prev j 0))]
(do
(assoc! curr (inc j) match-len)
(recur (inc j) (max max-len match-len))))
(do
(assoc! curr (inc j) 0)
(recur (inc j) max-len)))
max-len))
curr
prev)
max-len))))
Curiously, this is a disaster, taking over about 10x longer. Not what I
was expecting at all.
Guess this doesn't shed any light on your problem at all, but just
thought it would be good to share.
Phil
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
