I know your question was a technical one rather than a question about
Clojure coding, but your solution led me to wonder about a number of
Clojure coding points.
My solution to the palindrome detector also needed to calculate the
size of half the list. New Clojurians quickly discover that the "/"
function returns ratio results (not necessarily whole numbers). I see
you used Java to call Math.floor to get your integer. At first, I
used a cast: (int (/ (count list))). Then I found the whole-number
functions for dividing: "quot" (quotient) and "rem" (remainder).
Your overall design includes building a list of booleans which are
tested to see if they're all true. I'm wondering if there's something
in Clojure that's a little more concise than #(= true %) to see if
something is true. I don't see a "true?" predicate. I wonder if the
fact that we're looking for one means "we're doing it wrong"?
My last point of wondering relates to performance. I'm still wrapping
my head around the basics of Clojure, so I'm not yet totally sure how
to mentally judge what's going on behind the scenes (or what -may- go
on, depending on the type of collections passed in to these functions)
with respect to performance.
My solution was to calculate the size of half of the collection, then
just compare the equality of the first half of the list with the
reverse of the last half of the list.
#(let [n (quot (count %) 2)]
(= (take n %) (reverse (take-last n %))))
I think this is nicely expressed and readable, but for all I know it
might be terrible performance-wise.
I'm curious if anyone can give a quick explanation of the big-O
behaviors of both of these solutions. I'd like to be able to get more
natural insight on how to think about what's happening (or again, what
-may- happen depending on collection type) behind the scenes.
My original strategy involved a loop/recur where each iteration
compared the 1st and last element of the list, then "and" that with a
recursive call on a new list with the 1st and last elements removed.
But I worried that this would potentially yield unfavorable O(n^2)
performance, since popping-off the last element of a list (as in a
Clojure linked list) would be an O(n) operation on each iteration
(..right?)
However, I don't know if I didn't just sweep some O(n^2) operations
under the rug with my "readable" solution above.
If anyone has a hint on a technique/approach that yields better big-O
performance, let me know!
> I know your question was a technical one rather than a question about
> Clojure coding, but your solution led me to wonder about a number of
> Clojure coding points.
> My solution to the palindrome detector also needed to calculate the
> size of half the list. New Clojurians quickly discover that the "/"
> function returns ratio results (not necessarily whole numbers). I see
> you used Java to call Math.floor to get your integer. At first, I
> used a cast: (int (/ (count list))). Then I found the whole-number
> functions for dividing: "quot" (quotient) and "rem" (remainder).
> Your overall design includes building a list of booleans which are
> tested to see if they're all true. I'm wondering if there's something
> in Clojure that's a little more concise than #(= true %) to see if
> something is true. I don't see a "true?" predicate. I wonder if the
> fact that we're looking for one means "we're doing it wrong"?
> My last point of wondering relates to performance. I'm still wrapping
> my head around the basics of Clojure, so I'm not yet totally sure how
> to mentally judge what's going on behind the scenes (or what -may- go
> on, depending on the type of collections passed in to these functions)
> with respect to performance.
> My solution was to calculate the size of half of the collection, then
> just compare the equality of the first half of the list with the
> reverse of the last half of the list.
> #(let [n (quot (count %) 2)]
> (= (take n %) (reverse (take-last n %))))
> I think this is nicely expressed and readable, but for all I know it
> might be terrible performance-wise.
> I'm curious if anyone can give a quick explanation of the big-O
> behaviors of both of these solutions. I'd like to be able to get more
> natural insight on how to think about what's happening (or again, what
> -may- happen depending on collection type) behind the scenes.
> My original strategy involved a loop/recur where each iteration
> compared the 1st and last element of the list, then "and" that with a
> recursive call on a new list with the 1st and last elements removed.
> But I worried that this would potentially yield unfavorable O(n^2)
> performance, since popping-off the last element of a list (as in a
> Clojure linked list) would be an O(n) operation on each iteration
> (..right?)
> However, I don't know if I didn't just sweep some O(n^2) operations
> under the rug with my "readable" solution above.
> If anyone has a hint on a technique/approach that yields better big-O
> performance, let me know!
Ha! Well, paint me stupid. Next time I should try the REPL. I went
to http://clojuredocs.org/quickref/Clojure%20Core and did ctrl-F for
true? and it's not there. There must be some built-in predicates
that aren't documented on that page or something. Or they just missed
that one.
On Sep 19, 11:42 am, panther-tamer <panther.tamer.awes...@gmail.com>
wrote:
> On Sep 19, 4:32 pm, chepprey <chepp...@gmail.com> wrote:
> > I know your question was a technical one rather than a question about
> > Clojure coding, but your solution led me to wonder about a number of
> > Clojure coding points.
> > My solution to the palindrome detector also needed to calculate the
> > size of half the list. New Clojurians quickly discover that the "/"
> > function returns ratio results (not necessarily whole numbers). I see
> > you used Java to call Math.floor to get your integer. At first, I
> > used a cast: (int (/ (count list))). Then I found the whole-number
> > functions for dividing: "quot" (quotient) and "rem" (remainder).
> > Your overall design includes building a list of booleans which are
> > tested to see if they're all true. I'm wondering if there's something
> > in Clojure that's a little more concise than #(= true %) to see if
> > something is true. I don't see a "true?" predicate. I wonder if the
> > fact that we're looking for one means "we're doing it wrong"?
> > My last point of wondering relates to performance. I'm still wrapping
> > my head around the basics of Clojure, so I'm not yet totally sure how
> > to mentally judge what's going on behind the scenes (or what -may- go
> > on, depending on the type of collections passed in to these functions)
> > with respect to performance.
> > My solution was to calculate the size of half of the collection, then
> > just compare the equality of the first half of the list with the
> > reverse of the last half of the list.
> > #(let [n (quot (count %) 2)]
> > (= (take n %) (reverse (take-last n %))))
> > I think this is nicely expressed and readable, but for all I know it
> > might be terrible performance-wise.
> > I'm curious if anyone can give a quick explanation of the big-O
> > behaviors of both of these solutions. I'd like to be able to get more
> > natural insight on how to think about what's happening (or again, what
> > -may- happen depending on collection type) behind the scenes.
> > My original strategy involved a loop/recur where each iteration
> > compared the 1st and last element of the list, then "and" that with a
> > recursive call on a new list with the 1st and last elements removed.
> > But I worried that this would potentially yield unfavorable O(n^2)
> > performance, since popping-off the last element of a list (as in a
> > Clojure linked list) would be an O(n) operation on each iteration
> > (..right?)
> > However, I don't know if I didn't just sweep some O(n^2) operations
> > under the rug with my "readable" solution above.
> > If anyone has a hint on a technique/approach that yields better big-O
> > performance, let me know!
Funny, I had the same issue for a while on the exact same page. Next
time, just click Clojure Core above Quick Ref link. :) Or,
http://clojuredocs.org/clojure_core
On Sep 19, 7:46 pm, chepprey <chepp...@gmail.com> wrote:
> Ha! Well, paint me stupid. Next time I should try the REPL. I went
> tohttp://clojuredocs.org/quickref/Clojure%20Coreand did ctrl-F for
> true? and it's not there. There must be some built-in predicates
> that aren't documented on that page or something. Or they just missed
> that one.
> On Sep 19, 11:42 am, panther-tamer <panther.tamer.awes...@gmail.com>
> wrote:
> > As I am also only a clojure beginner, I would like to hear someone`s
> > opinion on this as well. However, I would like to make just one
> > correction:
> > On Sep 19, 4:32 pm, chepprey <chepp...@gmail.com> wrote:
> > > I know your question was a technical one rather than a question about
> > > Clojure coding, but your solution led me to wonder about a number of
> > > Clojure coding points.
> > > My solution to the palindrome detector also needed to calculate the
> > > size of half the list. New Clojurians quickly discover that the "/"
> > > function returns ratio results (not necessarily whole numbers). I see
> > > you used Java to call Math.floor to get your integer. At first, I
> > > used a cast: (int (/ (count list))). Then I found the whole-number
> > > functions for dividing: "quot" (quotient) and "rem" (remainder).
> > > Your overall design includes building a list of booleans which are
> > > tested to see if they're all true. I'm wondering if there's something
> > > in Clojure that's a little more concise than #(= true %) to see if
> > > something is true. I don't see a "true?" predicate. I wonder if the
> > > fact that we're looking for one means "we're doing it wrong"?
> > > My last point of wondering relates to performance. I'm still wrapping
> > > my head around the basics of Clojure, so I'm not yet totally sure how
> > > to mentally judge what's going on behind the scenes (or what -may- go
> > > on, depending on the type of collections passed in to these functions)
> > > with respect to performance.
> > > My solution was to calculate the size of half of the collection, then
> > > just compare the equality of the first half of the list with the
> > > reverse of the last half of the list.
> > > #(let [n (quot (count %) 2)]
> > > (= (take n %) (reverse (take-last n %))))
> > > I think this is nicely expressed and readable, but for all I know it
> > > might be terrible performance-wise.
> > > I'm curious if anyone can give a quick explanation of the big-O
> > > behaviors of both of these solutions. I'd like to be able to get more
> > > natural insight on how to think about what's happening (or again, what
> > > -may- happen depending on collection type) behind the scenes.
> > > My original strategy involved a loop/recur where each iteration
> > > compared the 1st and last element of the list, then "and" that with a
> > > recursive call on a new list with the 1st and last elements removed.
> > > But I worried that this would potentially yield unfavorable O(n^2)
> > > performance, since popping-off the last element of a list (as in a
> > > Clojure linked list) would be an O(n) operation on each iteration
> > > (..right?)
> > > However, I don't know if I didn't just sweep some O(n^2) operations
> > > under the rug with my "readable" solution above.
> > > If anyone has a hint on a technique/approach that yields better big-O
> > > performance, let me know!
Whoa.. I like this better than my solution. I think my brain is still
in the death-throws of Java-think.
Your solution is smaller and more readable... it reads basically like
the definition of palindrome. And it doesn't do a count.
Since the = function (I assume) "short circuits", and since seq and
reverse are lazy, then I think this should be at worst an O(n)
operation, where the worst case is if your collection happens to be a
palindrome.
Or wait a minute... what is the performance of reverse on a list?
O(n^2)? Are Clojure lists singly or doubly linked?
On Sep 20, 5:35 am, finbeu <info_pe...@t-online.de> wrote:
