Почему A.issuperset (B) намного медленнее, чем все (b в A вместо b в B)? - PullRequest
Новая
       56

Почему A.issuperset (B) намного медленнее, чем все (b в A вместо b в B)?

0 голосов
/ 02 августа 2020

Рассмотрите возможность проверки того, является ли набор A надмножеством итерируемого B, один раз с методом набора именно для этого и один раз с моим собственным выражением с использованием определения надмножества: 

>>> A = set(range(1000))
>>> B = range(-1000, 0)
>>> A.issuperset(B)
False
>>> all(b in A for b in B)
False

Теперь рассчитаем время: 

>>> from timeit import timeit
>>> timeit(lambda: A.issuperset(B))
52.666367300000005
>>> timeit(lambda: all(b in A for b in B))
0.9698789999999917

Собственный метод набора намного медленнее. Зачем? Предположительно он может / должен делать то же самое, но со скоростью C, поэтому должно быть быстрее .

Я использую CPython 3.8.1.

Ответы [ 2 ]

3 голосов
/ 02 августа 2020

Реализация из set.issubset и set.issuperset настаивает на построении набора из аргумента в первую очередь: 

static PyObject *
set_issubset(PySetObject *so, PyObject *other)
{
    setentry *entry;
    Py_ssize_t pos = 0;
    int rv;

    if (!PyAnySet_Check(other)) {
        PyObject *tmp, *result;
        tmp = make_new_set(&PySet_Type, other);
        if (tmp == NULL)
            return NULL;
        result = set_issubset(so, tmp);
        Py_DECREF(tmp);
        return result;
    }
    if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
        Py_RETURN_FALSE;

    while (set_next(so, &pos, &entry)) {
        rv = set_contains_entry((PySetObject *)other, entry->key, entry->hash);
        if (rv < 0)
            return NULL;
        if (!rv)
            Py_RETURN_FALSE;
    }
    Py_RETURN_TRUE;
}

PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");

static PyObject *
set_issuperset(PySetObject *so, PyObject *other)
{
    PyObject *tmp, *result;

    if (!PyAnySet_Check(other)) {
        tmp = make_new_set(&PySet_Type, other);
        if (tmp == NULL)
            return NULL;
        result = set_issuperset(so, tmp);
        Py_DECREF(tmp);
        return result;
    }
    return set_issubset((PySetObject *)other, (PyObject *)so);
}

PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");

issuperset создает набор из аргумента, затем звонит other.issubset(self). (issubset также настаивает на наличии набора в качестве аргумента, но он получает его, поэтому в этом случае преобразование не требуется.) Они могли бы довольно легко добавить путь кода к issuperset для обработки неустановленных аргументы без преобразования набора, но они этого не сделали.

Я подозреваю, что причиной этого может быть ошибка при вызовах типа {1}.issuperset([2, [3]]), где аргумент содержит нехешируемые элементы. Однако также вероятно, что никто не удосужился его оптимизировать. Поиск в системе отслеживания проблем Python для issuperset обнаруживает 0 проблем с оптимизацией issuperset, даже не закрытых проблем. Существует закрытая проблема о еще сложная оптимизация для issubset, что удивительно, но хотя это привело бы к аналогичным изменениям поведения исключения, ни один из ответов по проблеме ничего не сказал об этом .

1 голос
/ 02 августа 2020

Кажется, что разница заключается в том, что в вашем тесте вы фактически запускаете issuperset не между двумя наборами, а скорее между набором и диапазоном. Большая часть времени уходит на преобразование диапазона в набор. Учитывайте следующие тайминги: 

A = set(range(1000))
B_set = set(range(-1000, 0))
B_range = range(-1000, 0)
B_list = list(range(-1000, 0))

%%timeit 
A.issuperset(B_set)
654 ns ± 6.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit 
A.issuperset(B_range)
29.9 µs ± 259 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%%timeit 
A.issuperset(B_list)
15.4 µs ± 233 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)


# Creating a set from a range. 
%%timeit
B_set = set(B_range)
29.2 µs ± 209 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%%timeit 
all(b in A for b in B_set)
816 ns ± 16.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit 
all(b in A for b in B_range)
474 ns ± 4.74 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
...