Какие функции являются кандидатами на мемоизацию?

Question

Я решил использовать PostSharp (неотличимый от магии) для чтения атрибутов и запомнить функции.Хэш вызова функции будет ключом и кэшированным (в Скорость) результат будет возвращен вместо повторного вызова функции.Легко, с макаронами и сыром.

Я уже сдавшийся о возможности обнаружения побочных эффектов в декорированных функциях, что оказалось «сложной проблемой» даже для экспертов, которыми я, конечно, не являюсь.Далее мне нужно выяснить, какие еще функции являются кандидатами на мемоизацию.

• А как насчет методов, которые принимают в качестве параметров сложные ссылочные типы?
• А как насчет методов, которые зависят от данных внутри экземпляров, из которых они вызываются?

В последнем случае на ум приходят объекты данных в стиле ActiveRecord.

Придется ли мне реорганизовать код недельной давности для поддержки мемоизации?

Answer 1

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

Мемоизация зависит от детерминированного сопоставления входных и выходных данных.Каждый звонок в F(a, b, c) в которых a, b и c содержат одни и те же значения, должны возвращать один и тот же результат, чтобы было возможно запоминание.

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

public int MyFunction(MyType t)
{
   return t.Value;
}

Console.WriteLine(MyFunction(t));
t.Value++;
Console.WriteLine(MyFunction(t));

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

int Value = 0;

public int MyFunction(int input)
{
   return Value;
}

Console.WriteLine(MyFunction(1));
Value++;
Console.WriteLine(MyFunction(1));

И да поможет вам Бог, если ваша запомненная функция делает что-то кроме возврата значения или нового ссылочного типа:

int Value = 0;

public int MyFunction(int input)
{
   Value++;
   return input;
}

Если вы вызовете эту функцию 10 раз, Value будет 10.Если вы выполните рефакторинг для использования мемоизации, а затем вызовете его 10 раз, Value будет 1.

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

Если вы хотите реализовать мемоизацию в функции, принимающей ссылочный тип, правильным подходом будет рефакторинг той части функции, которая работает только с типами значений, и мемоизация этой функции, например:

public int MyFunction(MyType t)
{
   return t.Value + 1;
}

к этому:

public int MyFunction(MyType t)
{
   return MyMemoizableFunction(t.Value);
}

private int MyMemoizableFunction(int value)
{
   return value + 1;
}

Любой другой подход к реализации мемоизации, который вы используете, либо а) делает то же самое, но более неясными способами, или б) не будет работать.

Answer 2

Ну, любая функция, теоретически, является кандидатом на мемоизацию.Однако помните, что мемоизация — это обмен пространства на скорость.

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

Оба ваших примера — это, по сути, случаи, когда необходимо сохранить больше состояний.Это имеет два побочных эффекта.

Во-первых, для запоминания функции потребуется гораздо больше места в памяти, поскольку потребуется сохранить больше информации.

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

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

Я признаю, что это расплывчато, но это часть «художественности» в архитектуре.Не существует «правильного» ответа без реализации обоих вариантов (запоминаемых и незапоминаемых функций), профилирования и измерения.

Answer 3

Вы уже подумали о том, как предоставить АОП-решение для обеспечения запоминания функций. Foo, так что же осталось выяснить?

Да, вы можете передать объект произвольной сложности в качестве параметра запоминаемой функции, если он неизменен, как и все, от чего он зависит.Опять же, в настоящий момент это совсем не легко обнаружить статически.

Вы все еще верите в то, что можете статически исследовать код, чтобы дать своим пользователям совет по вопросу: «Хороша ли идея применить мемоизацию к функциям?» Foo?"

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