Как мне написать универсальную функцию памятки?

Question

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

function triangle (x)
   if x == 0 then return 0 end
   return x+triangle(x-1)
end

Но попытка вычислить первые 100 000 чисел треугольника не удалась с переполнением стека через некоторое время. Это идеальная функция для памятки , но я хочу решение, которое запомнит любую функцию, которую я ей передам.

Answer 1

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

Пример из его справочной страницы:

# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments);    # Is faster than it was before

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

Memoize.pm даже имеет средства для обеспечения постоянства кэша memento, поэтому его не нужно повторно заполнять при каждом вызове вашей программы!

Вот документация: http://perldoc.perl.org/5.8.8/Memoize.html

Answer 2

В духе публикации заметок на разных языках я хотел бы ответить на @ onebyone.livejournal.com примером C ++ без изменения языка.

Во-первых, памятка для функций с одним аргументом:

template <class Result, class Arg, class ResultStore = std::map<Arg, Result> >
class memoizer1{
public:
    template <class F>
    const Result& operator()(F f, const Arg& a){
        typename ResultStore::const_iterator it = memo_.find(a);
        if(it == memo_.end()) {
            it = memo_.insert(make_pair(a, f(a))).first;
        }
        return it->second;
    }
private:
    ResultStore memo_;
};

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

Далее, функция драйвера и реализация. только функция драйвера должна быть общедоступной int fib (int); // Водитель int fib_ (int); // реализация

Реализован:

int fib_(int n){
    ++total_ops;
    if(n == 0 || n == 1) 
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

И драйвер, чтобы запомнить

int fib(int n) {
    static memoizer1<int,int> memo;
    return memo(fib_, n);
}

Постоянная ссылка, показывающая вывод на codepad.org. Количество звонков измеряется для проверки правильности. (введите юнит-тест здесь ...)

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

Answer 3

Вот общая реализация C # 3.0, если она может помочь:

public static class Memoization
{
    public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
    {
        var cache = new Dictionary<T, TResult>();
        var nullCache = default(TResult);
        var isNullCacheSet = false;
        return  parameter =>
                {
                    TResult value;

                    if (parameter == null && isNullCacheSet)
                    {
                        return nullCache;
                    }

                    if (parameter == null)
                    {
                        nullCache = function(parameter);
                        isNullCacheSet = true;
                        return nullCache;
                    }

                    if (cache.TryGetValue(parameter, out value))
                    {
                        return value;
                    }

                    value = function(parameter);
                    cache.Add(parameter, value);
                    return value;
                };
    }
}

(цитируется по французской статье в блоге )

Answer 4

Пожалуйста, не повторяйте это. Либо используйте формулу x * (x + 1) / 2, либо просто повторяйте значения и запоминайте их по ходу.

int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
  sum+=i;
  memo[i] = sum;
}
return memo[n];

Answer 5

Рекурсия не нужна. Число n-го треугольника равно n (n-1) / 2, поэтому ...

public int triangle(final int n){
   return n * (n - 1) / 2;
}

Answer 6

Расширяя идею, можно также запоминать функции с двумя входными параметрами:

function memoize2 (f)
   local cache = {}
   return function (x, y)
             if cache[x..','..y] then
                return cache[x..','..y]
             else
                local z = f(x,y)
                cache[x..','..y] = z
                return z
             end
          end
end

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

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

function gcd (a, b) 
   if b == 0 then return a end
   return gcd(b, a%b)
end

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