To be very precise, (conj v new-elem) is O(log n) in time and space, but it is "constant-ish" because the base of the logarithm is something like 32, rather than something like 2, so the constant factor multiplying the log n is typically pretty small.
Also, there is no difference in Clojure's behavior in this case whether the new element is different than all elements previously conj'd onto the vector. They could all be the same, and the time and space requirements would be exactly the same as if they were all distinct. If you happen to know that they are all distinct, that's your business :-) Andy On Thu, Sep 22, 2011 at 11:09 PM, F Lengyel <florian.leng...@gmail.com>wrote: > > On Sep 23, 1:39 am, Nathan Sorenson <n...@sfu.ca> wrote: > > Just to clarify, you want to conj a vector to itself? i.e. [1 2 3 4] --> > [1 > > 2 3 4 [1 2 3 4]] I'm curious what the application of this is. > > > > Regarding the overhead of conj-ing to a vector: Clojure's data structures > > make use of structural sharing so conjoining an element to the end of a > > vector won't require any copying of entire vectors. It's a cheap, > > constant(ish) time operation. > > > Good: (conj v v) is O(1) in time and space, and appends an element > distinct from the preceding elements (if any). I meant to add that > querying > the vector is not allowed. The reason is to use reduce in situations > where > some data structure is created based on a previous and current > element. If the last element is guaranteed to be different from those > preceding it, then an edge case is eliminated (or rather, encoded into > the sequence at minimal cost). > > -- > 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 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
