New submission from Josh Rosenberg <[email protected]>:
At present, set_intersection (the C name for set.intersection) optimizes for
pairs of sets by iterating the smallest set and only adding entries found in
the larger, meaning work is proportionate to the smallest input.
But when the other input isn't a set, it goes with a naive solution, iterating
the entire non-set, and adding entries found in the set. This is fine when the
intersection will end up smaller than the original set (there's no way to avoid
exhausting the non-set when that's the case), but when the intersection ends up
being the same size as the original, we could add a cheap length check and
short-circuit at that point.
As is, {4}.intersection(range(10000)) takes close to 1000 times longer than
{4}.intersection(range(10)) despite both of them reaching the point where the
outcome will be {4} at the same time.
Since the length check for short-circuiting only needs to be performed when
input set actually contains the value, the cost should be fairly low.
I figure this would be the worst case for the change:
{3, 4}.intersection((4,) * 10000)
where it performs the length check every time, and doesn't benefit from
short-circuiting. But cases like:
{4}.intersection((4,) * 10000)
or
{4}.intersection(range(10000))
would finish much faster. A similar optimization to set_intersection_multi (to
stop when the intermediate result is empty) would make cases like:
{4000}.intersection([1], range(10000), range(100000, 200000))
also finish dramatically quicker in the (I'd assume not uncommon case) where
the intersection of many iterables is empty, and this could be known quite
early on (the cost of this check would be even lower, since it would only be
performed once per iterable, not per-value).
Only behavioral change this would cause is that errors resulting from
processing items in an iterable that is no longer run to exhaustion due to
short-circuiting wouldn't happen ({4}.intersection([4, []]) currently dies, but
would succeed with short-circuiting; same foes for {4}.intersection([5], [[]])
if set_intersection_multi is optimized), and input iterators might be left only
partially consumed. If that's acceptable, the required code changes are trivial.
----------
components: C API
keywords: easy (C)
messages: 388442
nosy: josh.r
priority: normal
severity: normal
status: open
title: set intersections should short-circuit
versions: Python 3.10
_______________________________________
Python tracker <[email protected]>
<https://bugs.python.org/issue43464>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
