| msg189806 - (view) |
Author: hhm (hhm) |
Date: 2013-05-22 11:58 |
| It says here (http://docs.python.org/2/library/stdtypes.html#set-types-set-frozenset) that some of the set methods take iterables as a parameter. Usually, the expected behavior is for a iterator consumer to consume only as much data as it needs. For example, for the code `any(itertools.repeat(True))`, the code will complete speedily, in contrast to when all() is used instead of any(), in which case the code will go forever. A least some of the set methods have semantics such that they can consume only some of the input; for example, "issubset" only needs to make sure that all of the items in the set are in the iterable, and once this is the case, it can return "True". However in such a case, the methods will *still* go forever. The docs should specify that this is the case, to disambiguate the semantics. (Tested on Python 3.2.3 and 2.7.3). |
|
|
| msg190133 - (view) |
Author: Raymond Hettinger (rhettinger) *  |
Date: 2013-05-27 07:59 |
| We don't normally document implementation details or the presences or absence of internal optimizations. This gives us freedom to change the implementation and it allows freedom for other implementations (such as Jython, IronPython, and PyPy) to make their own choices. Often those implementations start out with the simplest correct approach and then become increasingly optimized over time. I'm leaving this one open as a possible CPythhon performance enhancement, adding early-out behavior to issubset() when the argument is a non-set, non-dict iterable: def issubset(self, iterable): n = len(self) seen = set() for x in iterable: if x not in seen and x in self: seen.add(x) n -= 1 if not n: return True # early-out return False |
|
|
| msg203416 - (view) |
Author: Dustin Haffner (dhaffner) * |
Date: 2013-11-19 19:19 |
| I've made an attempt at patching set_issubset() to match the Python from Raymond's message. I've rearranged the set_issubset function so that it checks for a set/frozenset, dict, or iterable in that order. In the iterable case it will create a temporary set and add elements to it as it consumes them from the iterable, returning early when possible. This is my first patch, please let me know how I may improve it! |
|
|
| msg221338 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2014-06-23 03:24 |
| The patch looks good. I'll go over it in more detail shortly. |
|
|
| msg221382 - (view) |
Author: Josh Rosenberg (josh.r) *  |
Date: 2014-06-23 23:07 |
| Patch needs some work. See comments on patch. |
|
|
| msg231760 - (view) |
Author: Bruno Cauet (bru) * |
Date: 2014-11-27 13:38 |
| Here is an updated patch based on Dustin's work with Josh's comments. I also added a test which takes forever on an unpatched python interpreter. Since it's a performance issue, I've benchmarked the results. They don't change for the most part (argument is a set or a dict) but they're way better for iterables. For every type of argument I test 1 case where "set.issubset" returns True and 1 case where it returns False. (a) simple argument (results unchanged) $ ./python -m timeit -s "s1 = set(range(1000)); s2 = set(range(1000))" "s1.issubset(s2)" Unpatched: 10000 loops, best of 3: 63.7 usec per loop Patched: 10000 loops, best of 3: 63.5 usec per loop $ ./python -m timeit -s "s1 = set(range(1000)); s2 = set(range(1, 1000))" "s1.issubset(s2)" Unpatched: 1000000 loops, best of 3: 0.248 usec per loop Patched: 1000000 loops, best of 3: 0.25 usec per loop $ ./python -m timeit -s "s1 = set(range(1000)); s2 = dict(enumerate(range(1000)))" "s1.issubset(s2)" Unpatched: 10000 loops, best of 3: 107 usec per loop Patched: 10000 loops, best of 3: 108 usec per loop $ ./python -m timeit -s "s1 = set(range(1000)); s2 = dict(enumerate(range(1, 1000)))" "s1.issubset(s2)" Unpatched: 10000 loops, best of 3: 43.5 usec per loop Patched: 10000 loops, best of 3: 42.6 usec per loop (b) iterable argument (speed improvement) 1) no improvements/slight degradation when everything must be consumed $ ./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1000))" Unpatched: 1000 loops, best of 3: 263 usec per loop Patched: 1000 loops, best of 3: 263 usec per loop $ ./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1, 1000))" Unpatched: 10000 loops, best of 3: 201 usec per loop Patched: 1000 loops, best of 3: 259 usec per loop $ ./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1, 1000))" Unpatched: 1000 loops, best of 3: 198 usec per loop Patched: 1000 loops, best of 3: 218 usec per loop 2) tremendous improvements when it can return early $ ./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1000))" Unpatched: 1000 loops, best of 3: 209 usec per loop Patched: 100000 loops, best of 3: 12.1 usec per loop $ ./python -m timeit -s "s1 = set('a'); s2 = ['a'] + ['b'] * 10000" "s1.issubset(s2)" Unpatched: 1000 loops, best of 3: 368 usec per loop Patched: 1000000 loops, best of 3: 0.934 usec per loop $ ./python -m timeit -s "s1 = set('a'); from itertools import repeat" "s1.issubset(repeat('a'))" Unpatched: NEVER FINISHES Patched: 1000000 loops, best of 3: 1.33 usec per loop |
|
|
| msg244155 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2015-05-27 10:44 |
| In C implementation no need to create set object seen. More efficient way is to use bit array. Here is a patch that uses this approach. ./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1000))" Unpatched : 10000 loops, best of 3: 115 usec per loop bru's patch: 10000 loops, best of 3: 114 usec per loop My patch : 10000 loops, best of 3: 92.6 usec per loop ./python -m timeit -s "s1 = set(range(1000))" "s1.issubset(range(1, 1000))" Unpatched : 10000 loops, best of 3: 73.4 usec per loop bru's patch: 10000 loops, best of 3: 114 usec per loop My patch : 10000 loops, best of 3: 93 usec per loop ./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1, 1000))" Unpatched : 10000 loops, best of 3: 73.6 usec per loop bru's patch: 10000 loops, best of 3: 89 usec per loop My patch : 10000 loops, best of 3: 62.4 usec per loop ./python -m timeit -s "s1 = set(range(100))" "s1.issubset(range(1000))" Unpatched : 10000 loops, best of 3: 75.5 usec per loop bru's patch: 100000 loops, best of 3: 8.77 usec per loop My patch : 100000 loops, best of 3: 5.34 usec per loop ./python -m timeit -s "s1 = set('a'); s2 = ['a'] + ['b'] * 10000" "s1.issubset(s2)" Unpatched : 1000 loops, best of 3: 326 usec per loop bru's patch: 1000000 loops, best of 3: 0.394 usec per loop My patch : 1000000 loops, best of 3: 0.409 usec per loop ./python -m timeit -s "s1 = set('a'); from itertools import repeat" "s1.issubset(repeat('a'))" Unpatched : NEVER FINISHES bru's patch: 1000000 loops, best of 3: 0.794 usec per loop My patch : 1000000 loops, best of 3: 0.725 usec per loop |
|
|
| msg244158 - (view) |
Author: Bruno Cauet (bru) * |
Date: 2015-05-27 12:38 |
| Serhiy, that sounds good but I think that you have forgotten to attach the mentioned patch. |
|
|
| msg244163 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2015-05-27 13:00 |
| Oh, sorry. Here is it. |
|
|
| msg244246 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2015-05-28 03:01 |
| Personally I don't sure that this optimization is worth to apply. Its cost is high and optimized case is not common. This is rather an experiment, how large can be maximal effect of the optimization. |
|
|
| msg244250 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2015-05-28 03:12 |
| > Personally I don't sure that this optimization is worth to apply. I concur. Closing as "not worth it" :-) |
|
|