Hacker News Reader

Comment by thaumasiotes | Hacker News Reader

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.

View on HN

> 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-...

> 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.

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).

> 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.

Reply on news.ycombinator.com