On Thu, 12 Mar 2009 15:50:16 -0700 Jason Wolfe <jawo...@berkeley.edu> wrote: > > On Mar 12, 2009, at 3:34 PM, Kyle Schaffrick wrote: > > > > > On Thu, 12 Mar 2009 12:45:00 -0700 (PDT) > > Jason Wolfe <jawo...@berkeley.edu> wrote: > >>> Also, union/difference/intersection/symmetric-diff are binary. > >>> Would there be any interest in a patch to make them n-ary? > >>> > >> > >> Union, difference, and intersection are all variadic as of a month > >> or so ago. Are you on the latest SVN? > >> > >> -Jason > > > > Oops, so they are. I am actually on SVN but referred to (apparently) > > out-of-date docs. That, or Rich has joined the circle of > > time-machine-owning dynamic-language-designing BDFLs. > > > > In that case, here's my two stabs at n-ary set symmetric difference: > > > > (defn symmetric-diff [& sets] > > (let [all-members (apply union sets) > > nr-memberships > > (fn [m] (apply + (for [s sets :when (contains? s m)] 1))) > > in-sym-diff (fn [m] (odd? (nr-memberships m)))] > > (set (filter in-sym-diff (seq all-members))))) > > > > (defn symmetric-diff > > ([s1] s1) > > ([s1 s2] > > (difference (union s1 s2) > > (intersection s1 s2))) > > ([s1 s2 & sets] > > (reduce symmetric-diff s1 (conj sets s2)))) > > > > -Kyle > > IIRC the docs all correspond to the last release, which was a couple > months ago. This means that by now they are quite out of date, but > at least they're stable for people who shy away from the bleeding > edge.
Yeah, I always forget about that. *high-fives self* > I suppose this might be good in clojure.contrib.set, if any of the > primary contributors want to OK it. Have you done any timing > tests? The first version could be improved by adding a "distinct" on > all- members before the filter. union does an implicit distinct operation, as it returns a set. I didn't think Clojure had multisets, unless we've had another Rich's Time Machine moment :) > My guess is that the second version would still be faster, but I'm not > sure. Also, (union (difference s1 s2) (difference s2 s1)) may be > faster than (difference (union s1 s2) (intersection s1 s2)), but again > I'm not sure. I generated 10 sets of 100 random integers between 0-200. Then I timed 3000 iterations applied to 1 thru 10 sets, on a -server VM. I warmed up the JIT on each version a couple of times. First version / second version: "Elapsed time: 462.881526 msecs" "Elapsed time: 1.445784 msecs" "Elapsed time: 901.305403 msecs" "Elapsed time: 357.005849 msecs" "Elapsed time: 1334.729903 msecs" "Elapsed time: 783.21756 msecs" "Elapsed time: 1746.563041 msecs" "Elapsed time: 1165.418231 msecs" "Elapsed time: 2264.295812 msecs" "Elapsed time: 1549.46746 msecs" "Elapsed time: 2569.731838 msecs" "Elapsed time: 1956.67962 msecs" "Elapsed time: 2854.096121 msecs" "Elapsed time: 2349.644787 msecs" "Elapsed time: 3278.285648 msecs" "Elapsed time: 2768.575964 msecs" "Elapsed time: 3529.430695 msecs" "Elapsed time: 3136.699357 msecs" "Elapsed time: 3854.478292 msecs" "Elapsed time: 3514.263823 msecs" It seems they're both linear complexity but the second is faster by a noticeable constant. Fascinating! -Kyle --~--~---------~--~----~------------~-------~--~----~ 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 To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
