On Mon, May 30, 2011 at 5:19 PM, Ken Wesson <kwess...@gmail.com> wrote:
> "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.
Actually, there is one further speedup. Both versions assume the
strings are all the same length, but not that that length is three.
Moving l out of the let it's in and into an outer (let [l (int 2)]
...) wrapping the whole function body might afford a minor additional
speedup for the case that the strings are only ever of length three.
It will then bomb on inputs containing shorter strings (IOOBE) and on
inputs containing longer strings will return pairs with the property
that of the first three characters of the two strings exactly two are
the same. Without that change, the loop/recur version bombs if strings
are not nondecreasing in length in the input seq and both versions
check for a shorter string differing by exactly one character from a
longer string's prefix of equal length. A quick O(n) input validation
could be prefixed that verifies that all the strings are equal in
length, or even that they are of length 3 specifically:
(defn validate-strings [strs]
(if-let [s (seq strs)]
(let [l (.length ^String (first s))
s (next s)]
(loop [s s]
(if s
(if (== l (.length ^String (first s)))
(recur (next s))
(throw (IllegalArgumentException. "boo!"))))))))
=> (validate-strings ["foo" "bar" "baz"])
nil
=> (validate-strings ["fooq" "barq" "bazq"])
nil
=> (validate-strings ["fooq" "barq" "bazqz"])
#<CompilerException java.lang.IllegalArgumentException: boo! (NO_SOURCE_FILE:0)>
For length 3 specifically, change the let bindings to just [l (int 3)]:
=> (validate-strings ["foo" "bar" "baz"])
nil
=> (validate-strings ["fooq" "barq" "bazq"])
#<CompilerException java.lang.IllegalArgumentException: boo! (NO_SOURCE_FILE:0)>
--
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
