Re: Addition of new a priori distinct element to a vector
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
Re: Addition of new a priori distinct element to a vector
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.comwrote: 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
Re: Addition of new a priori distinct element to a vector
what's the actual use case where you want this? it seems pretty weird just on it's own. it may in practice be more clever than other solutions, but that's not clear yet. if you just want a unique symbol there's (gensym) regarding vectors, I found this a helpful read a while back, it's a few years old, but I think it's still accurate, and may help you get a picture of what's under the hood. http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ Kevin On Sep 23, 12:09 am, 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
Re: Addition of new a priori distinct element to a vector
On Sep 23, 2:18 am, Andy Fingerhut andy.finger...@gmail.com wrote: 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. OK, thanks. 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. Nor did I imply or suggest that it would be different. FL -- 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
Re: Addition of new a priori distinct element to a vector
Hi, is there any particular reason not to use a Set instead of a vector? It solves the issue of distinct values. Or am I missing something? Regards, Stefan -- 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
Re: Addition of new a priori distinct element to a vector
On Sep 23, 2:20 am, Kevin Livingston kevinlivingston.pub...@gmail.com wrote: what's the actual use case where you want this? it seems pretty weird just on it's own. it may in practice be more clever than other solutions, but that's not clear yet. if you just want a unique symbol there's (gensym) For the sake of illustration, this function will chunk a vector into vectors of identical elements, in order (no assurance that it won't be weird in context): (defn grp [s] (- (reduce (fn [[v chunk] elt] (if (or (empty? chunk) (= elt (first chunk))) [v (conj chunk elt)] [(conj v chunk) [elt]])) [[][]] (conj s s)) (first))) user (grp []) [] user (grp [1 2 3 2 2 3]) [[1] [2] [3] [2 2] [3]] user (grp [1 1 4 4 4]) [[1 1] [4 4 4]] user regarding vectors, I found this a helpful read a while back, it's a few years old, but I think it's still accurate, and may help you get a picture of what's under the hood.http://blog.higher-order.net/2009/02/01/understanding-clojures-persis... Kevin That's helpful, thank you. -- 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
Re: Addition of new a priori distinct element to a vector
On Sep 23, 3:02 pm, F Lengyel florian.leng...@gmail.com wrote: On Sep 23, 2:20 am, Kevin Livingston kevinlivingston.pub...@gmail.com wrote: what's the actual use case where you want this? it seems pretty weird just on it's own. it may in practice be more clever than other solutions, but that's not clear yet. if you just want a unique symbol there's (gensym) For the sake of illustration, this function will chunk a vector into vectors of identical elements, in order (no assurance that it won't be weird in context): (defn grp [s] (- (reduce (fn [[v chunk] elt] (if (or (empty? chunk) (= elt (first chunk))) [v (conj chunk elt)] [(conj v chunk) [elt]])) [[][]] (conj s s)) (first))) (partition-by identity s) is simpler unless you have some very compelling reason to need vectors? user (grp []) [] user (grp [1 2 3 2 2 3]) [[1] [2] [3] [2 2] [3]] user (grp [1 1 4 4 4]) [[1 1] [4 4 4]] user regarding vectors, I found this a helpful read a while back, it's a few years old, but I think it's still accurate, and may help you get a picture of what's under the hood.http://blog.higher-order.net/2009/02/01/understanding-clojures-persis... Kevin That's helpful, thank you. -- 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
Addition of new a priori distinct element to a vector
Suppose I have a vector v. I would like to add a new element to v distinct from all of the elements of v, with the constraint that I assume nothing about v other than it is a vector. (There are cases where it is useful to do this with some algorithms involving reduce, for example.) One way to do this is (conj v v). Is the overhead of doing this in clojure the addition of a pointer (of some kind) to v, or is it something else? Thanks. F Lengyel -- 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
Re: Addition of new a priori distinct element to a vector
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. -- 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
