[New-bugs-announce] [issue46721] Optimize set.issuperset() for non-set argument

Serhiy Storchaka report at bugs.python.org
Fri Feb 11 10:15:23 EST 2022

New submission from Serhiy Storchaka <storchaka+cpython at gmail.com>:

If the argument of set.issuperset() is not a set, it is first converted to a set. It is equivalent to the following code:

    if not isinstance(other, (set, frozenset)):
        other = set(other)
    # The following is equivalent to:
    # return set.issubset(other, self)
    for x in other:
        if x not in self
            return False
    return True

Two drawbacks of this algorithm:

1. It creates a new set, which takes O(len(other)) time and consumes O(len(set(other))) memory.
2. It needs to iterate other to the end, even if the result is known earlier.

The proposed PR straightforward the code. The C code is now larger, but it no longer need additional memory, performs less operations and can stop earlier.

components: Interpreter Core
messages: 413075
nosy: rhettinger, serhiy.storchaka
priority: normal
severity: normal
status: open
title: Optimize set.issuperset() for non-set argument
type: performance
versions: Python 3.11

Python tracker <report at bugs.python.org>

More information about the New-bugs-announce mailing list