Apologies for multiple posts; I will try to thoroughly investigate
things before starting posting next time. Anyway, to round out the
thread, here are corresponding results for intersection and union:
(defn- fast-intersection- "Expects s1 and s2 sets, s1 bigger than
s2." [s1 s2]
(reduce (fn [result item]
(if (contains? s1 item)
result
(disj result item)))
s2 s2))
(defn fast-intersection "Like intersection, but faster." [s1 s2]
(if (or (not (set? s2))
(> (int (count s1)) (int (count s2))))
(fast-intersection- s1 s2)
(fast-intersection- s2 s1)))
user> (let [small-set (hash-set 1), big-set (set (range 10000))]
(doseq [fn [clojure.set/intersection fast-intersection]
[s1 s2] [[small-set big-set] [big-set small-set]]]
(time (dotimes [_ 1000] (fn s1 s2)))))
"Elapsed time: 3976.334 msecs" ; (clojure.set/intersection small big)
"Elapsed time: 18059.634 msecs" ; (clojure.set/intersection big small)
"Elapsed time: 9.68 msecs" ; (fast-intersection small big)
"Elapsed time: 7.598 msecs" ; (fast-intersection big small)
As you can see, it looks like clojure.set/intersection is fast for
*neither* ordering of sets if they are of disparate size.
(defn fast-union "Like union, but faster." [s1 s2]
(if (or (not (set? s2))
(> (int (count s1)) (int (count s2))))
(reduce conj s1 s2)
(reduce conj s2 s1)))
user> (let [small-set (hash-set 1), big-set (set (range 10000))]
(doseq [fn [clojure.set/union fast-union]
[s1 s2] [[small-set big-set] [big-set small-set]]]
(time (dotimes [_ 1000] (fn s1 s2)))))
"Elapsed time: 20444.035 msecs" ; (clojure.set/union small big)
"Elapsed time: 0.956 msecs" ; (clojure.set/union big small)
"Elapsed time: 2.906 msecs" ; (fast-union small big)
"Elapsed time: 2.826 msecs" ; (fast-union big small)
And, finally, clojure.set/union is fast for one order of arguments but
(especially) slow for the other.
-Jason
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
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
-~----------~----~----~----~------~----~------~--~---
