FAQ
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+unsubscribe@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

Search Discussions

  • Nathan Sorenson at Sep 23, 2011 at 5:39 am
    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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • F Lengyel at Sep 23, 2011 at 6:09 am

    On Sep 23, 1:39 am, Nathan Sorenson 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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • Andy Fingerhut at Sep 23, 2011 at 6:18 am
    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 wrote:

    On Sep 23, 1:39 am, Nathan Sorenson 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+unsubscribe@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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • F Lengyel at Sep 23, 2011 at 6:44 am

    On Sep 23, 2:18 am, Andy Fingerhut 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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • Kevin Livingston at Sep 23, 2011 at 6:24 am
    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 wrote:
    On Sep 23, 1:39 am, Nathan Sorenson 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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • F Lengyel at Sep 23, 2011 at 10:02 pm

    On Sep 23, 2:20 am, Kevin Livingston 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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • Alan Malloy at Sep 23, 2011 at 10:53 pm

    On Sep 23, 3:02 pm, F Lengyel wrote:
    On Sep 23, 2:20 am, Kevin Livingston

    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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en
  • Stefan Kamphausen at Sep 23, 2011 at 8:01 am
    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+unsubscribe@googlegroups.com
    For more options, visit this group at
    http://groups.google.com/group/clojure?hl=en

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupclojure @
categoriesclojure
postedSep 23, '11 at 5:23a
activeSep 23, '11 at 10:53p
posts9
users6
websiteclojure.org
irc#clojure

People

Translate

site design / logo © 2022 Grokbase