Почему одна стратегия запоминания медленнее другой?

Итак, эта страница о мемоизации меня заинтересовала. Я провел собственные тесты.

1) Изменяемый словарь по умолчанию:

%%timeit
def fibo(n, dic={}) :
    if n not in dic :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
    return dic[ n ]
fibo(30)

Из:

100000 loops, best of 3: 18.3 µs per loop

2) Та же идея, но по принципу «Легче попросить прощения, чем разрешения»:

In [21]:

%%timeit
def fibo(n, dic={}) :
    try :
        return dic[n]
    except :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
        return dic[ n ]
fibo(30)

Из:

10000 loops, best of 3: 46.8 µs per loop

Мои вопросы

  • Почему 2) такой медленный по сравнению с 1)?

Редактировать

Как предполагает @kevin в комментариях, я совершенно неправильно понял декоратор, поэтому удалил его. Остаток в силе! (Я надеюсь)


python python-decorators memoization fibonacci
person usual me    schedule 25.08.2014    source источник
comment
Это очень необычный декоратор. Обычно, когда вы декорируете функцию где-то в декораторе, вы в конечном итоге вызываете эту функцию после выполнения некоторой работы. Но ваш декоратор никогда не вызывает f. Когда вы декорируете fibo, вы фактически отбрасываете определение этой функции и заменяете его функцией из примера 1.   -  person Kevin    schedule 25.08.2014
comment
Перехват исключений (что означает трассировку стека) может быть очень дорогим: docs.python.org/2/faq/design.html#how-fast-are-exceptions   -  person Dmitry Bychenko    schedule 25.08.2014
comment
@DmitryBychenko Вы должны опубликовать это как ответ, я думаю.   -  person Sylvain Leroux    schedule 25.08.2014
comment
Откуда взялся принцип Легче попросить прощения, чем разрешения? :0 В контексте программирования это звучит довольно неразумно.   -  person BartoszKP    schedule 25.08.2014
comment
@BartoszKP Это довольно распространенный принцип в Python, который обычно используется, чтобы отговорить людей, привыкших к статически типизированным языкам, от чрезмерной проверки типов перед использованием переменных. На самом деле это справедливо только в том случае, если а) код не относится к области, чувствительной к производительности, или б) вы ожидаете, что в большинстве случаев вам не нужно будет просить прощения :)   -  person dano    schedule 25.08.2014
comment
@dano Из того, что я видел, в случае проверки типов вообще нет прощения. TypeError или NameError обычно просто сворачивают приложение и все :-)   -  person BartoszKP    schedule 25.08.2014
comment
@BartoszKP Это правда. И в большинстве случаев пользователь, вероятно, даст вам правильную вещь. Вот почему лучше предположить, что они дали вам правильную вещь, и просто обработать исключение, если она неверна. Таким образом, вы избежите накладных расходов на hasattr или if key in d:. Другая область, в которой этот принцип часто используется, — это проверка существования ключей/атрибутов перед попыткой их использования, что (иногда) с большей вероятностью будет прощено.   -  person dano    schedule 25.08.2014

Ответы (2)


arrow_upward
7
arrow_downward

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

https://docs.python.org/2/faq/design.html#how-fast-are-exceptions

Исключения очень эффективны в двух случаях:

  1. try ... finally
  2. try ... except при условии, что исключение не выдается

Однако, когда исключение возникло и было перехвачено, необходимая трассировка стека приводит к значительным накладным расходам.

person Dmitry Bychenko    schedule 25.08.2014

arrow_upward
0
arrow_downward

Первый подход выполняет всего три поиска (n not in dic:, вставка dic[n] = и возврат dic[n]). Второй подход также выполняет три поиска в наихудшем случае (попытка извлечения dic[n] = , вставка dic[n] = и возврат dic[n]) и дополнительно включает обработку исключений.

Если один подход делает ту же работу, что и другой, и что-то к этому добавляет, он, очевидно, не может быть быстрее и, скорее всего, будет медленнее.

Рассмотрите возможность сравнения эффективности в сценарии, когда мемоизация может оказаться полезной, например, запускать функцию несколько раз, чтобы сравнить амортизированную сложность. Таким образом, наихудшая ситуация для второго подхода будет случаться реже, и вы сможете получить что-то от одного поиска меньше.

Версия 1:

def fibo(n, dic={}) :
    if n not in dic :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
    return dic[ n ]

for i in range(10000):
    fibo(i)

Версия2:

def fibo(n, dic={}) :
    try :
        return dic[n]
    except :
        if n in (0,1) :
            dic[n] = 1
        else :
            dic[n] = fibo(n-1)+fibo(n-2)
        return dic[ n ]

for i in range(10000):
    fibo(i)

И тест:

C:\Users\Bartek\Documents\Python›python -m timeit -- import version1
1000000 циклов, лучшее из 3: 1,64 мкс на цикл

C:\Users\Bartek\Documents\Python›python -m timeit -- import version2
1000000 циклов, лучшее из 3: 1,6 мкс на цикл

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

person BartoszKP    schedule 25.08.2014