Почему любые () и все () неэффективны при лечении булевых?

голоса
2

Я просто понял , что - то, играя с timeitи and, or, any(), all()я полагал , что я мог бы поделиться здесь. Вот скрипт для измерения производительности:

def recursion(n):
    A slow way to return a True or a False boolean.
    return True if n == 0 else recursion(n-1)       

def my_function():
    The function where you perform all(), any(), or, and.
    a = False and recursion(10)

if __name__ == __main__:
    import timeit
    setup = from __main__ import my_function
    print(timeit.timeit(my_function(), setup=setup))

А вот некоторые тайминги:

a = False and recursion(10)
0.08799480279344607

a = True or recursion(10)
0.08964192798430304

Как и следовало ожидать, True or recursion(10)а также False and recursion(10)очень быстро вычислить , потому что только первый член вопросы и операция возвращается немедленно.

a = recursion(10) or True # recursion() is False
1.4154556830951606 

a = recursion(10) and False # recursion() is True
1.364157978046478

Наличие or Trueили and Falseв линии не ускорить вычисление здесь , потому что они оцениваются вторыми и вся рекурсия должна быть выполнена первым. В то время как раздражает, это логично и вытекает приоритет правил эксплуатации.

Что более удивительно то , что all()и any()всегда имеют худшую производительность , независимо от случая:

a = all(i for i in (recursion(10), False))) # recursion() is False
1.8326778537880273

a = all(i for i in (False, recursion(10))) # recursion() is False
1.814645767348111

Я ожидал бы вторую оценку гораздо быстрее, чем первый.

a = any(i for i in (recursion(10), True))) # recursion() is True
1.7959248761901563

a = any(i for i in (True, recursion(10))) # recursion() is True
1.7930442127481

Те же самые неудовлетворенные ожидания здесь.

Так что , похоже , как any()и all()далеки от того , чтобы быть удобным способом писать соответственно большим orи большим , andесли производительность имеет значение в вашем приложении. Это почему?

Изменить: на основе комментариев, кажется поколение кортеж медленно. Я не вижу причин, почему сам Python не может использовать это:

def all_faster(*args):
    Result = True
    for arg in args:
        if not Result:
            return False
        Result = Result and arg
    return True

def any_faster(*args):
    Result = False
    for arg in args:
        if Result:
            return True
        Result = Result or arg
    return False

Это быстрее, чем уже встроенные функции и, кажется, механизм короткого замыкания.

a = faster_any(False, False, False, False, True)
0.39678611016915966

a = faster_any(True, False, False, False, False)
0.29465180389252055

a = faster_any(recursion(10), False) # recursion() is True
1.5922580174283212

a = faster_any(False, recursion(10)) # recursion() is True
1.5799157924820975

a = faster_all(False, recursion(10)) # recursion() is True
1.6116566893888375

a = faster_all(recursion(10), False) # recursion() is True
1.6004807187900951

Edit2: Хорошо это быстрее с передаваемыми аргументами один за другим, но медленнее с генераторами.

Задан 19/09/2018 в 13:22
источник пользователем
На других языках...                            


2 ответов

голоса
2

На самом деле, any()эквивалентна цепи orи all()эквивалентна цепи and, в том числе короткого замыкания. Проблема заключается в том , как вы выполнить тест.

Рассмотрим следующий пример:

def slow_boolean_gen(n, value=False):
    for x in range(n - 1):
        yield value
    yield not value

generator = slow_boolean_gen(10)

print([x for x in generator])
# [False, False, False, False, False, False, False, False, False, True]

и следующие микро-тесты:

%timeit generator = slow_boolean_gen(10, True); next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator)
# 492 ns ± 35.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator) or next(generator)
# 1.18 µs ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator)
# 1.19 µs ± 11.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator) and next(generator)
# 473 ns ± 6.27 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit generator = slow_boolean_gen(10, True); any(x for x in generator)
# 745 ns ± 15 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); any(x for x in generator)
# 1.29 µs ± 12.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); all(x for x in generator)
# 1.3 µs ± 22.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); all(x for x in generator)
# 721 ns ± 8.05 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit generator = slow_boolean_gen(10, True); any([x for x in generator])
# 1.03 µs ± 28.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); any([x for x in generator])
# 1.09 µs ± 27.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); all([x for x in generator])
# 1.05 µs ± 11.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); all([x for x in generator])
# 1.02 µs ± 11.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Вы можете ясно видеть , что короткое замыкание работает, но если вы первый построить list, что принимает постоянное время , которое компенсирует любой прирост производительности , который вы получите от короткого замыкания.

РЕДАКТИРОВАТЬ:

Руководство реализация не покупает нам никакого выигрыша в производительности:

def all_(values):
    result = True
    for value in values:
        result = result and value
        if not result:
            break
    return result

def any_(values):
    result = False
    for value in values:
        result = result or value
        if result:
            break
    return result

%timeit generator = slow_boolean_gen(10, True); any_(x for x in generator)
# 765 ns ± 6.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); any_(x for x in generator)
# 1.48 µs ± 8.97 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, True); all_(x for x in generator)
# 1.47 µs ± 5.71 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit generator = slow_boolean_gen(10, False); all_(x for x in generator)
# 765 ns ± 8.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Ответил 19/09/2018 в 14:11
источник пользователем

голоса
1

anyи allкороткое замыкание в порядке.

Проблема заключается в том, что здесь , в обоих случаях, вы должны построить tupleдо передать его anyтак что порядок не делает разницу: время , потраченное все та же. Давайте разложим это с переменным:

t = (True, recursion(10))   # recursion is called
a = any(i for i in t)       # this is very fast, only boolean testing

Когда Вы достигаете вторую линию, то время уже потрачено.

Это отличается с andили orкаким коротким замыканием.

Случай , когда anyи allинтересны, когда вы оценки данных при тестировании:

any(recusion(x) for x in (10,20,30))

Если вы хотите , чтобы избежать оценок, можно передать кортеж лямбды (встроенные функции) до anyи вызова функции:

сейчас:

a = any(i() for i in (lambda:recursion(10), lambda:True))) 

а также:

a = any(i() for i in (lambda:True,lambda:recursion(10)))) 

имеют очень разное время исполнения (последнее происходит мгновенно)

Ответил 19/09/2018 в 13:23
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more