I have a solution (gist here https://gist.github.com/aria42/5026109, key
bits pasted below). It's pretty short (15 lines) and readable (I think) and
only 50% slower than the Java version on my machine (averaging over 25 runs
of your benchmark function).
Generally, I've found it's really easy when you just translate Java code
like this into Clojure, the Clojure will read worse than the original Java;
to boot it will also be slower! And not to be insulting, but I think the
other Clojure solutions I saw in this thread seem to have this property.
You usually have to pull out some abstraction in order to regain on the
readability and concentrate on performance there. Here, I think it's a
macro you'll probably use all over the place, arr-max, which will find the
largest value of an expression looping over an array's index and values.
Then lcs is just nested uses of arr-max that I think is pretty reasonable.
The thing which clutters the remaining code are the prev/cur swapping which
I don't have a slick way of handling.
(defmacro arr-max
"return maximum value of `expr` over the indices
and values of array `arr`, where `idx-symb` and `val-symb`
are bound to index and values of `arr`"
[arr idx-symb val-symb expr]
`(let [arr# ~arr
n# (alength arr#)]
(loop [~idx-symb 0 max-val# java.lang.Long/MIN_VALUE]
(if (= ~idx-symb n#)
max-val#
(let [~val-symb (aget arr# ~idx-symb)
val# ~expr]
(recur (inc ~idx-symb)
(if (> val# max-val#)
val# max-val#)))))))
(defn lcs [^objects a1 ^objects a2]
(let [prev-ref (atom (long-array (inc (alength a2))))
cur-ref (atom (long-array (inc (alength a2))))]
(arr-max a1 i v1
(let [^longs prev @prev-ref
^longs cur @cur-ref
max-len (arr-max a2 j v2
(let [match-len (if (.equals v1 v2)
(inc (aget prev j))
0)]
(aset cur (inc j) match-len)
match-len))]
(reset! prev-ref cur)
(reset! cur-ref prev)
(long max-len)))))
On Sunday, February 24, 2013 12:45:18 PM UTC-8, Marko Topolnik wrote:
>
>
>
> On Sunday, February 24, 2013 9:15:45 PM UTC+1, puzzler wrote:
>>
>>
>> As I mentioned before, I'm generally happy with Clojure's performance,
>> but the few times I've had performance problems, I ended up rewriting the
>> code at least three different ways in order to try to find the magic
>> combination that would boost performance.
>>
>
> Lately I've leaned towards going full monty the first time out: stop
> guessing and optimize everything past the entry point to the critical
> section. It sounds like more work up front, but in the end it's the "smart"
> approach that results in more total effort.
>
>
>> Fortunately, dropping down to Java is relatively painless. But I still
>> wonder whether there might be some benefit to having a "low-level DSL"
>> within Clojure, a mode that lets you choose to write your code in a way
>> where the semantics are closer to the underlying platform.
>>
>
> Just one feature would make a huge difference: reassignable locals.
>
>
>> I haven't used Clojurescript much, but I get the impression that
>> Clojurescript is already a step in that direction, with a simpler story
>> regarding how mutation, arrays, and primitives are translated to the
>> underlying platform, arguably making it easier to get good performance when
>> you need it.
>>
>
> The gap between Clojure and JavaScript is far less than Java because both
> are dynamic. I think that plays a big part in why ClojureScript can be more
> transparent.
>
>
--
--
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
---
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
