On Apr 30, 4:33 am, Rich Hickey <[email protected]> wrote:
> People don't consider sets, vectors, arrays or strings to have 'keys'.
> But, like maps, they all support fast lookup of some sort.
But of course we do. I point to the doc for contains? and get:
Usage: (contains? coll key)
Returns true if key is present in the given collection, otherwise
returns false.
Usage: (get map key)
(get map key not-found)
Returns the value mapped to key, not-found or nil if key not present.
Both reference the notion of a "key". If referencing keys in the
documentation doesn't hurt, and makes its usage more clear, I can't
see why that reasoning wouldn't follow to the function name itself,
especially if we allow for a contains-val? (which I know is also
> Would contains-val? be fast for sets?
As with any abstract method/function the worst-case is what's
documented. Anyone looking at contains-val? should expect worst-case
O(n), just as anyone looking at contains-key? should expect (near)
O(1).
The deeper question is: if an abstract method/function is documented
to be worst-case O(n), then must all implementations be written to
ensure the worst-case performance, even when it could be implemented
in O(1) time?
>As a user of sets, I consider
> them collections of values, and I absolutely would reach for contains-
> val? in any library that had it, for use with sets. If so, and I used
> contains-val?, and I moved code from using sets to maps (happens
> frequently), or vectors (also happens) my perf would suddenly stink.
> If not fast on sets, why not? The reason isn't supported by the name.
Your perf stinking is a product of you testing for values, and not
keys. The alternative would have been to use contains? with your sets
and watch (contains? s "foo") blow up when you tried to use the same
code against a vector.
> The mismatch with the seq values of maps is also disconcerting for
> something that would purport to be sequential, as the things returned
> by (seq amap) are key+value pairs.
Only seq-contains? purports to be related to seq, whereas contains-
val? purports to check if the value is in the collection, and to do so
in worst-case O(n) time. Going back to your earlier point about
swapping out datastructures, (contains-val? v "foo") written against
vectors would work just fine when handed a map; seq-contains? would
give false negatives.
> Renaming contains? is not on the table.
Very well.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
