Proposal: "smarter" set operations that take size into account for speed
Jason Wolfe
difference between a small set and a large set. In this circumstance,
clojure.set/difference is needlessly slow. Because of this, in
general, a sequence of n clojure.set operations may run in O(n^2) time
when O(n) is easily achievable. Here's the basic idea:
(defn difference2 "Like difference, but fast for big s2 and small
s1" [s1 s2]
(reduce (fn [result item] (if (contains? s2 item) (disj result item)
result))
s1 s1))
(defn fast-difference "Like difference, but faster." [s1 s2]
(let [c1 (int (count s1))
c2 (int (count s2))]
(if (< c1 c2)
(difference2 s1 s2)
(clojure.set/difference s1 s2))))
user> (let [small-set (hash-set 1), big-set (set (range 10000))]
(doseq [fn [clojure.set/difference difference2 fast-difference]
[s1 s2] [[small-set big-set] [big-set small-set]]]
(time (dotimes [_ 1000] (fn s1 s2)))))
"Elapsed time: 3995.249 msecs" ; (set/difference small big)
"Elapsed time: 3.358 msecs" ; (set/difference big small)
"Elapsed time: 1.91 msecs" ; (difference2 small big)
"Elapsed time: 4935.183 msecs" ; (difference2 big small)
"Elapsed time: 3.088 msecs" ; (fast-difference small big)
"Elapsed time: 3.401 msecs" ; (fast-difference big small)
For the commutative operations (union and intersection), I suppose you
could argue that the user should know how the operations work and put
the arguments in the right (fast) order -- but sometimes, that
information will only be known at runtime. Overall, the possibility
of a big O improvement for a small constant penalty seems worth it to
me.
Questions or comments? Any objections/support for me adding this as
an issue?
Thanks,
Jason
Jason Wolfe
require the second argument to be a set. In the case that it's not, I
believe the current implementations (at least for difference) are as
good as it gets.
So, I guess fast-difference should read:
(defn fast-difference "Like difference, but faster." [s1 s2]
(> (int (count s1)) (int (count s2))))
(clojure.set/difference s1 s2)
(difference2 s1 s2)))
-Jason
Jason Wolfe
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]
(> (int (count s1)) (int (count s2))))
(fast-intersection- s2 s1)))
user> (let [small-set (hash-set 1), big-set (set (range 10000))]
(time (dotimes [_ 1000] (fn s1 s2)))))
"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]
(> (int (count s1)) (int (count s2))))
(reduce conj s2 s1)))
user> (let [small-set (hash-set 1), big-set (set (range 10000))]
(time (dotimes [_ 1000] (fn s1 s2)))))
"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
Jason Wolfe
On Jan 20, 4:44 pm, Jason Wolfe <jawo...@berkeley.edu> wrote:
> 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:
was a bug in fast-intersection when s2 was not a set. Fixed version:
(defn fast-intersection "Like intersection, but faster." [s1 s2]
(if (contains? s1 item)
result))
#{} s2)
:else
(fast-intersection- s2 s1)))
-Jason
Mark Engelberg
size of the two inputs, and adjust the algorithm accordingly.
pc
structures is extremely important.
But Rich and the Contributers must have tons of other stuff to worry
about. In the meantime I will
use Jason's fix.
Jason Wolfe
for adding them to clojure.contrib?
I can't say I like the idea of having two sets of functions that do
exactly the same thing, but ... sometimes you just don't want things
to run ~1000 times slower than they should.
-Jason
Mark Engelberg
>
> OK, if these are not wanted in core right now, will anyone sign off
> for adding them to clojure.contrib?
>
Well, *I* want these changes you've proposed in the core, but of
course, I'm not in charge. I guess the real question is, what is the
process to ensure that Rich sees and considers a potential core
improvement like this? I think the main mechanism for this is to post
it as an "issue" on google code, but I'm not certain whether you're
supposed to post an issue unless he's seen the newsgroup thread and
says, "Yes, that sounds good, please post it as an issue." But if he
misses the thread for some reason, that will never happen. So it's a
bit of a catch-22. Anyway, maybe someone can clarify the procedure.
Cosmin Stejerean
Cosmin Stejerean
http://offbytwo.com
Jason Wolfe
> On Fri, Jan 23, 2009 at 12:23 PM, Jason Wolfe <jaw...@berkeley.edu>
> wrote:
>>
>> OK, if these are not wanted in core right now, will anyone sign off
>> for adding them to clojure.contrib?
>>
>
> Well, *I* want these changes you've proposed in the core, but of
> course, I'm not in charge.
Thanks.
> I guess the real question is, what is the
> process to ensure that Rich sees and considers a potential core
> improvement like this? I think the main mechanism for this is to post
> it as an "issue" on google code, but I'm not certain whether you're
> supposed to post an issue unless he's seen the newsgroup thread and
> says, "Yes, that sounds good, please post it as an issue." But if he
> misses the thread for some reason, that will never happen. So it's a
> bit of a catch-22. Anyway, maybe someone can clarify the procedure.
Yes, it is not supposed to be posted as a core issue unless Rich OK's
it here.
I just had a discussion about just this "meta"-issue on IRC. Chouser
says that Rich still reads every message on the group. See also the
further-up discussion in [1] for more procedural details, where it is
also suggested that an explicit sign-off here should be required for
posting clojure.contrib issues.
[1] http://groups.google.com/group/clojure/msg/657291bc62c48f32?hl=en
Anyway, I'm feeling quite frustrated and won't try to push this (or
any other) issue further. I know Rich and the team are very busy, but
it really saps my will to contribute when I have to keep pushing to
get an authoritative answer (be it yes or no) on even (what seems to
me to be) a fairly uncontroversial change like this one, or [2].
[2] http://groups.google.com/group/clojure/browse_thread/thread/5d11bc0da25a7ecc?hl=en#
Sorry for taking your question as a jumping off point for whining
about not getting attention. I guess my short answer is: the policy
is fairly clear, but its current implementation may be discouraging
potential contributors like myself.
-Jason
Rich Hickey
On Jan 23, 4:19 pm, Jason Wolfe <jawo...@berkeley.edu> wrote:
> > On Fri, Jan 23, 2009 at 12:23 PM, Jason Wolfe <jawo...@berkeley.edu>
> Sorry for taking your question as a jumping off point for whining
> about not getting attention. I guess my short answer is: the policy
> is fairly clear, but its current implementation may be discouraging
> potential contributors like myself.
>
your needs. You have flooded the group with every idea you have, some
are bugs (important), some are good ideas, some not, but there are
simply too many to address at the rate you are producing them. In
addtion, sometimes you've made issues, and often blogged about them.
So, for #2 the issue was addressed and you found out about it that
way. I can't answer you (or anyone) in every forum.
I'd advise you to be more patient, build up a small library of helper
functions you use frequently, make contributions of the most important
of them to contrib. Clojure doesn't change that fast and it's not
going to. I like to consider things and I can't address every
suggestion as it is made.
Separate out the important things (like potential bugs) so they get
more attention.
As for these:
- 0-arg distinct? returns true, not an exception (so (apply distinct?
nil) = true)
Not now, will consider.
- rewrite concat so that (apply concat seq) doesn't evaluate the
first three elements of seq
No, may fall out of streams work.
- make every?, not-every?, some, not-any? take multiple seq args like
map, i.e., (every? not= [1 2 3] [2 3 4])
No.
- allow arguments to merge-with after the first to be lists of
pairs.
No.
Rich
Stephen C. Gilardi
Jason Wolfe
> I appreciate your desire to contribute, but Clojure is not just about
> your needs. You have flooded the group with every idea you have, some
> are bugs (important), some are good ideas, some not, but there are
> simply too many to address at the rate you are producing them.
OK, I am sorry. I know I have made at least one misguided post, and a
few quibbles about relatively minor things, but by and large I thought
I was being helpful. I have tried to meter out my posts, and focus on
issues of broader use to the community, but I guess I am failing on
both counts and will have to try harder.
> I'd advise you to be more patient, build up a small library of helper
> functions you use frequently, make contributions of the most important
> of them to contrib. Clojure doesn't change that fast and it's not
> going to. I like to consider things and I can't address every
> suggestion as it is made.
Fair enough.
> Separate out the important things (like potential bugs) so they get
> more attention.
>
> As for these:
>
> - 0-arg distinct? returns true, not an exception (so (apply distinct?
> nil) = true)
>
> Not now, will consider.
>
> - rewrite concat so that (apply concat seq) doesn't evaluate the
> first three elements of seq
>
> No, may fall out of streams work.
>
> - make every?, not-every?, some, not-any? take multiple seq args like
> map, i.e., (every? not= [1 2 3] [2 3 4])
>
> No.
>
> - allow arguments to merge-with after the first to be lists of
> pairs.
>
> No.
OK, thanks.
-Jason
Jason Wolfe
I just posted an issue here:
http://code.google.com/p/clojure-contrib/issues/detail?id=14
-Jason
P.S. I couldn't see how to make an "enhancement request" rather than a
"defect". The "Template" drop-down that shows up for the main Clojure
SVN doesn't show up here ... maybe it never got configured properly?
e
(ns my-ns(:use [clojure.set :exclude (difference)][clojure.contrib.set :only (difference)]))
Did you have to say ":exclude" or does the last thing override?
Stephen C. Gilardi
Rich Hickey
it's now the morning of the 24th and the first time I've had to really
look at the set issue.
I'm all for optimizing for size here, however, the fact that these
functions happen to work when the second argument is not a set is an
implementation artifact and not a promise of the interface, so I'm not
in favor of the set? testing or any other accommodation of that.
An issue w/patch for this would be welcome.
Thanks,
Rich
Jason Wolfe
> functions happen to work when the second argument is not a set is an
> implementation artifact and not a promise of the interface, so I'm not
> in favor of the set? testing or any other accommodation of that.
OK, from that I take it the Clojure way is to not call "set" on the
arguments either, and let whatever happens happen if you pass the
functions non-sets? Note that here this has the potential to be
especially confusing since, e.g., (union #{1 2 3} [4 5]) might succeed
while (union #{1 2} [3 4 5]) would error.
Second, should this be combined with this issue to make efficient
versions that take any number of arguments?
http://code.google.com/p/clojure/issues/detail?id=52&colspec=ID%20Type%20Status%20Priority%20Reporter%20Owner%20Summary
> An issue w/patch for this would be welcome.
Finally, I don't know how to make a patch, and found nothing in a
quick search of the wiki/newsgroup/website. I heard "Git" floating
around somewhere earlier; am I to check out the SVN with git-svn and
make a patch that way?
-Jason
Stephen C. Gilardi
On Jan 24, 2009, at 8:11 PM, Jason Wolfe wrote:
> Finally, I don't know how to make a patch, and found nothing in a
> quick search of the wiki/newsgroup/website. I heard "Git" floating
> around somewhere earlier; am I to check out the SVN with git-svn and
> make a patch that way?
To prepare a patch, use svn to checkout Clojure to a directory. Edit
the files within it to incorporate the changes you'd like included in
the patch, then cd to the top level of the checkout directory and
issue the command:
svn diff > my-patch.patch
You can also use the command:
svn status
from the top level of the checkout directory to see which files you
changed.
For completeness, if you'd like to apply such a patch to a fresh
Clojure checkout, copy the patch file to "/tmp", cd to the top level
of the checkout directory and issue the command:
patch -p0 < /tmp/my-patch.patch
Note: I used the /tmp temporary placeholder just to make the path in
the example literal.
--Steve
Jason Wolfe
Thanks for the detailed instructions!
-Jason