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

Question

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

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

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

Answer 1

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

triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]

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

Конечно, как уже указывалось, этот пример имеет решение в закрытой форме: triangle[x_] := x*(x+1)/2. Числа Фибоначчи - классический пример того, как добавление памятных записок дает резкое ускорение:

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

Хотя это также имеет эквивалент в замкнутой форме, хотя и более сложный: http://mathworld.wolfram.com/FibonacciNumber.html

Я не согласен с человеком, который предположил, что это неуместно для запоминания, потому что вы можете «просто использовать цикл». Точка запоминания заключается в том, что любые повторные вызовы функций выполняются за время O (1). Это намного лучше, чем O (n). Фактически, вы могли бы даже придумать сценарий, в котором запомненная реализация имеет лучшую производительность, чем реализация в закрытой форме!

Answer 2

Вы также задаете неправильный вопрос для вашей первоначальной проблемы;)

Это лучший способ для этого случая:

треугольник (n) = n * (n - 1) / 2

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

Answer 3

В C # 3.0 - для рекурсивных функций вы можете сделать что-то вроде:

public static class Helpers
{
    public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>,  R> f)
    {
        var map = new Dictionary<A, R>();
        Func<A, R> self = null;
        self = (a) =>
        {
            R value;
            if (map.TryGetValue(a, out value))
                return value;
            value = f(a, self);
            map.Add(a, value);
            return value;
        };
        return self;
    }        
}

Затем вы можете создать запомненную функцию Фибоначчи следующим образом:

var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));

Answer 4

Могу поспорить, что-то вроде этого должно работать со списками переменных аргументов в Lua:

local function varg_tostring(...)
    local s = select(1, ...)
    for n = 2, select('#', ...) do
        s = s..","..select(n,...)
    end
    return s
end

local function memoize(f)
    local cache = {}
    return function (...)
        local al = varg_tostring(...)
        if cache[al] then
            return cache[al]
        else
            local y = f(...)
            cache[al] = y
            return y
        end
    end
end

Возможно, вы могли бы также сделать что-то умное с метатаблицами с __tostring, чтобы список аргументов можно было просто преобразовать с помощью tostring (). О возможности.

Answer 5

Обновление : Комментаторы отметили, что запоминание является хорошим способом оптимизации рекурсии. По общему признанию, я не рассматривал это прежде, так как я обычно работаю на языке (C #), где обобщенное запоминание не так тривиально построить. Примите этот пост ниже, помня об этом.

Я думаю, У Люка, вероятно, есть наиболее подходящее решение для этой проблемы, но, как правило, запоминание не является решением любой проблемы переполнения стека.

Переполнение стека обычно вызывается рекурсией, идущей глубже, чем может обработать платформа. Языки иногда поддерживают « tail recursion », который повторно использует контекст текущего вызова, а не создает новый контекст для рекурсивного вызова. Но многие основные языки / платформы не поддерживают это. Например, в C # отсутствует встроенная поддержка хвостовой рекурсии. 64-разрядная версия .NET JITter может применять ее в качестве оптимизации на уровне IL, что практически бесполезно, если вам требуется поддержка 32-разрядных платформ.

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

Answer 6

в Scala (не проверено):

def memoize[A, B](f: (A)=>B) = {
  var cache = Map[A, B]()

  { x: A =>
    if (cache contains x) cache(x) else {
      val back = f(x)
      cache += (x -> back)

      back
    }
  }
}

Обратите внимание, что это работает только для функций arity 1, но с каррингом вы можете заставить это работать. Более тонкая проблема заключается в том, что memoize(f) != memoize(f) для любой функции f. Один очень хитрый способ исправить это будет примерно так:

val correctMem = memoize(memoize _)

Не думаю, что это скомпилируется, но это иллюстрирует идею.

Answer 7

function memoize (f)
   local cache = {}
   return function (x)
             if cache[x] then
                return cache[x]
             else
                local y = f(x)
                cache[x] = y
                return y
             end
          end
end

triangle = memoize(triangle);

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

Answer 8

Этот вопрос вдохновил меня на реализацию (еще одной) гибкой функции памятки в Lua.

https://github.com/kikito/memoize.lua

Основные преимущества:

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

Вставка кода здесь в качестве ссылки:

local globalCache = {}

local function getFromCache(cache, args)
  local node = cache
  for i=1, #args do
    if not node.children then return {} end
    node = node.children[args[i]]
    if not node then return {} end
  end
  return node.results
end

local function insertInCache(cache, args, results)
  local arg
  local node = cache
  for i=1, #args do
    arg = args[i]
    node.children = node.children or {}
    node.children[arg] = node.children[arg] or {}
    node = node.children[arg]
  end
  node.results = results
end


-- public function

local function memoize(f)
  globalCache[f] = { results = {} }
  return function (...)
    local results = getFromCache( globalCache[f], {...} )

    if #results == 0 then
      results = { f(...) }
      insertInCache(globalCache[f], {...}, results)
    end

    return unpack(results)
  end
end

return memoize

Answer 9

Вот кое-что, что работает без преобразования аргументов в строки. Единственное предостережение в том, что он не может обработать нулевой аргумент. Но принятое решение не может отличить значение nil от строки "nil", так что, вероятно, все в порядке.

local function m(f)
  local t = { }
  local function mf(x, ...) -- memoized f
    assert(x ~= nil, 'nil passed to memoized function')
    if select('#', ...) > 0 then
      t[x] = t[x] or m(function(...) return f(x, ...) end)
      return t[x](...)
    else
      t[x] = t[x] or f(x)
      assert(t[x] ~= nil, 'memoized function returns nil')
      return t[x]
    end
  end
  return mf
end

Answer 10

См. в этом блоге для общего решения Scala, до 4 аргументов.