[Python-ideas] exclusively1, common, exclusively2 = set1 - set2, set1 & set2, set2 - set1

[Juancarlo Añez]

On Thu, Jul 4, 2013 at 9:45 AM, Oscar Benjamin
<oscar.j.benjamin at gmail.com>wrote:

> If you're worried about optimal branch flow for large sets then you
> might consider swapping so that the first loop is over the smaller of
> the two sets (assuming that the for/if branch is slightly faster than
> the for/else branch). However the swapping difference is not really an
> algorithmic difference in the sense that it would be for computing
> only the intersection.
>

One of my points was (I haven't looked) that the native set operations
probably do the swapping, and preallocate the result sets.

Preallocation is an important performance booster, and may be part of an
algorithm. In the double-loop implementation, one could try to copy() to
the resulting sets, and then use remove() instead of add(). The swapping
based on length is also easy to do.

I guess that the point is that, in algorithm analysis, when the O() is
good, like O(N), one should take a look at the constant parts part of the
actual O(N*C+M*D) (for example), as they make all the difference. These
kind of considerations went into Python's choice of implementation for
sort(), for example.

-- 
Juancarlo *Añez*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20130704/6da7c82c/attachment.html>