On Mon, May 30, 2011 at 4:58 PM, Jonathan Fischer Friberg
<odysso...@gmail.com> wrote:
> I got an idea which probably doesn't perform very well although I found it a
> little interesting.
> https://gist.github.com/999430
>
> It simply groups the strings together, saying:
>
> * if the first and second characters are the same, they only differ in one
> position.
> * if the second and last characters ...
> * if the first and last characters ...
Still O(n^2). If you really want top performance, you'll have to go
with loop/recur, something like:
(defn pairs-off-one-fast [strs]
(loop [strs (seq strs) out []]
(if strs
(let [^String s1 (first strs)
l (unchecked-dec (int (.length s1)))
n (next strs)]
(recur
n
(loop [strs n out out]
(if strs
(let [^String s2 (first strs) n (next strs)]
(recur
n
(loop [i l diff? false]
(if (zero? i)
(if diff? (conj out [s1 s2]) out)
(if (= (.charAt s1 i) (.charAt s2 i))
(recur (unchecked-dec i) diff?)
(if diff? out (recur (unchecked-dec i) true)))))))
out))))
out)))
=> (pairs-off-one-fast ["abc" "abd" "aed" "axf" "zqr" "zbc" "aqd"])
[["abc" "abd"] ["abd" "aed"] ["abd" "zbc"] ["abd" "aqd"] ["aed" "aqd"]
["zqr" "aqd"]]
=> (time (dotimes [_ 10000] (doall (pairs-off-one ["abc" "abd" "aed"
"axf" "zqr" "zbc" "aqd"]))))
"Elapsed time: 1077.76876 msecs"
nil
=> (time (dotimes [_ 10000] (pairs-off-one-fast ["abc" "abd" "aed"
"axf" "zqr" "zbc" "aqd"])))
"Elapsed time: 53.93484 msecs"
nil
As you can see, the loop/primitive/type-hinted version is ~20x faster;
however, it is not lazy and might blow the heap with enough pairs of
off-by-one strings in a big enough input seq. Both versions
(necessarily) hold onto the head of the input seq until they're done.
--
Protege: What is this seething mass of parentheses?!
Master: Your father's Lisp REPL. This is the language of a true
hacker. Not as clumsy or random as C++; a language for a more
civilized age.
--
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
