3 ms·

cljs.user=> (source clojure.set/union) (defn union "Return a set that is the union of the input sets" ([] #{}) ([s1] s1) ([s1 s2]

cljs.user=> (source clojure.set/union) (defn union "Return a set that is the union of the input sets" ([] #{}) ([s1] s1) ([s1 s2] (if (< (count s1) (count s2)) (reduce conj s2 s1) (reduce conj s1 s2))) ([s1 s2 & sets] (let [bubbled-sets (bubble-max-key count (conj sets s2 s1))] (reduce into (first bubbled-sets) (rest bubbled-sets))))) nil cljs.user=> (source clojure.set/intersection) (defn intersection "Return a set that is the intersection of the input sets" ([s1] s1) ([s1 s2] (if (< (count s2) (count s1)) (recur s2 s1) (reduce (fn [result item] (if (contains? s2 item) result (disj result item))) s1 s1))) ([s1 s2 & sets] (let [bubbled-sets (bubble-max-key #(- (count %)) (conj sets s2 s1))] (reduce intersection (first bubbled-sets) (rest bubbled-sets))))) nil

thaumasiotes 10y ago
I don't feel that I know any more now than I did before you posted this "reply". The third branch ([s1 s2]) adds the elements of the smaller collection one by one onto the larger collection. Conceptually, it does this by constructing a new copy of the result for every addition, since conj is not destructive. It is buggy and will return a result of whatever type the larger collection is, with data being duplicated if that type allows for it. My question was, why does efficient set union of two collections require one of the two collections to support fast membership tests? As an answer to that question, you've posted code that doesn't involve membership tests at all and supplied no discussion of why it is or isn't efficient.
- muhuk 10y ago
  I wanted to give you an answer and started following down the call trail: https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L75 https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L661 https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentTreeSet.java#L51 https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L667 Then I gave up. I am curious too. Where I left off, we had a Cons cell. And I am hoping it will get converted to a set later (via empty).
- brandonbloom 10y ago
  > why does efficient set union of two collections require one of the two collections to support fast membership tests Sorry, I misspoke / used bad shorthand. Union should have efficient set addition for the larger argument and set _intersection_ requires efficient membership tests.
- mvc 10y ago
  > Conceptually, it does this by constructing a new copy of the result for every addition, since conj is not destructive That's not how persistent data structures work http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-... > why does efficient set union of two collections require one of the two collections to support fast membership tests I haven't thought much about this but it seems intuitively true to me. You want to take the smaller set, and add each item to the larger set if it doesn't already exist. That last part is why you need a fast membership test. If you're still unconvinced, try loading up two similarly structured database tables with a million rows and get the union of them (with and without indices). The indexed one will be orders of magnitude quicker.

thaumasiotes 10y ago

I don't feel that I know any more now than I did before you posted this "reply". The third branch ([s1 s2]) adds the elements of the smaller collection one by one onto the larger collection. Conceptually, it does this by constructing a new copy of the result for every addition, since conj is not destructive. It is buggy and will return a result of whatever type the larger collection is, with data being duplicated if that type allows for it. My question was, why does efficient set union of two collections require one of the two collections to support fast membership tests? As an answer to that question, you've posted code that doesn't involve membership tests at all and supplied no discussion of why it is or isn't efficient.

muhuk 10y ago
I wanted to give you an answer and started following down the call trail: https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L75 https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L661 https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentTreeSet.java#L51 https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L667 Then I gave up. I am curious too. Where I left off, we had a Cons cell. And I am hoping it will get converted to a set later (via empty).
brandonbloom 10y ago
> why does efficient set union of two collections require one of the two collections to support fast membership tests Sorry, I misspoke / used bad shorthand. Union should have efficient set addition for the larger argument and set _intersection_ requires efficient membership tests.
mvc 10y ago
> Conceptually, it does this by constructing a new copy of the result for every addition, since conj is not destructive That's not how persistent data structures work http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-... > why does efficient set union of two collections require one of the two collections to support fast membership tests I haven't thought much about this but it seems intuitively true to me. You want to take the smaller set, and add each item to the larger set if it doesn't already exist. That last part is why you need a fast membership test. If you're still unconvinced, try loading up two similarly structured database tables with a million rows and get the union of them (with and without indices). The indexed one will be orders of magnitude quicker.