last and nth are "bad"?
clojurefanxx
i'm asked to write a function, which when given a list or vector,
returns the last, penultimate, or an arbitrary nth element,
respectively.
for problem #19 (return last element), using the function last was not
accepted as a good solution for both lists and vectors, but the
following was accepted:
user=> (#(nth % (- (count %) 1)) '(5 4 3))
3
user=> (#(nth % (- (count %) 1)) '[1 2 3 4 5])
5
for problem #21, (return arbitrary element) , using the function nth
or get was not accepted.
---------------------------------------------------------------------------------------------
Write a function which returns the Nth element from a sequence.
(= (__ '(4 5 6 7) 2) 6)
(= (__ [:a :b :c] 0) :a)
(= (__ [1 2 3 4] 1) 2)
(= (__ '([1 2] [3 4] [5 6]) 2) [5 6])
------------------------------------------------------------------------------------------------
i think using the nth or get functions on vectors to return an element
at index position n should be fine performance-wise,
but what's a general solution for lists that will perform better than
O(n)? (i 'm assuming that's the reason why
last, nth, and get were rejected when I tried them out as candidate
solutions??)
thanks for any help!
James Estes
19-21 are trying to make you do exactly what you are doing: consider
the performance characteristics for various operations on a vector vs
a list or sequence.
Problem 19, for example, is highlighting that
1 - Last is slow for a vector. The last function is really meant to
operate on sequences, and therefore is restricted to only being able
to use first/next in its implementation, so for a vector, it has to
walk the entire vector to get to the end.
2 - Vectors can efficiently get the last value with "peek".
So, for 19, it seems to make sense to convert to a vector and just peek:
#(peek (vec %))
For 21, the same is true: nth is a sequence operation and therefore
must walk the vector. The solution here is actually what you tried
(use get), but you'd need to convert the lists to a vector first:
#(get (vec %) %2)
So, my "lesson learned" here is: If you need random access or, mostly
need access to the end of a fixed-length (ie non-infinite), use, or
convert to a vector. But, again I'm new too :)
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
Sunil S Nandihalli
Sean Corfield
> (i 'm assuming that's the reason why
> last, nth, and get were rejected when I tried them out as candidate
> solutions??)
The 4clojure tests are intended to get you to write solutions without
the "simple, obvious" function. Sometimes they actually want you to
specifically write your own version of one of the core functions, to
show you understand how such functions really work.
When I took Amit Rathore's ProClojure Boot Camp course a year ago, the
first section was all about us writing our own versions of map,
reduce, filter and so on to make sure we understand the basics of
processing data structures.
--
Sean A Corfield -- (904) 302-SEAN
An Architect's View -- http://corfield.org/
World Singles, LLC. -- http://worldsingles.com/
Railo Technologies, Inc. -- http://www.getrailo.com/
"Perfection is the enemy of the good."
-- Gustave Flaubert, French realist novelist (1821-1880)
James Estes
user=> (source last)
(def
^{:arglists '([coll])
:doc "Return the last item in coll, in linear time"
:added "1.0"}
last (fn last [s]
(if (next s)
(recur (next s))
(first s))))
unless i'm missing something with multimethod or protocol magic :)
Meikel Brandmeyer
Am Freitag, 10. Juni 2011 06:49:41 UTC+2 schrieb Sunil Nandihalli:
as long as (reversible? of-whatever-collection) is true , last is almost a constant time operation
In theory, but not in practice. last will always be O(N) in it's current implementation. The only fast way to get the last element is peek on a vector or (first (rseq ...)) for collections supporting rseq.
Sincerely
Meikel
Sunil S Nandihalli
clojurefanxx
last is bad!" or "You tripped the alarm! nth is bad!",
I'm merely being told not to use last or nth as the candidate
solutions but instead to write my own functions that achieve
the same goal. So the messages "last is bad!" or "nth is bad!"
probably just meant "last is forbidden!' or "nth is forbidden!".
My bad! Sorry ...
Nick Zbinden
iternaly? We allready have a internal reduce-protocoll why not have
one for other functions like last? The seq library should only drop to
first/rest if there is no better implementation.