Для чего memoization хорош и является этим действительно все что полезный?

Мемуализация обменивает время на пространство.

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

Классическим примером является вычисление последовательности Фибоначчи. Определение из учебника является рекуррентным соотношением:

F (n) = F (n-1) + F (n-2)

Реализовано наивно, похоже this:

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

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

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

int fib(int n) {
  static bool initialized = false;
  static std::vector<int> memo;

  if (!initialized) {
    memo.push_back(0);
    memo.push_back(1);
    initialized = true;
  }

  if (memo.size() > n) {
    return memo[n];
  }
  else {
    const int val = fib(n-1) + fib(n-2);
    memo.push_back(val);
    return val;
  }
}

Синхронизация этих двух реализаций на моем ноутбуке, для n = 42, наивная версия занимает 6,5 секунды. Записанная версия занимает 0,005 секунды (все системное время, то есть оно связано с вводом / выводом). При n = 50 запомненная версия по-прежнему занимает 0,005 секунды, а наивная версия, наконец, заканчивается через 5 минут & amp; 7 секунд (не говоря уже о том, что они оба переполнили 32-битное целое число).

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

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

В ИИ использование такой памятки обычно упоминается как «таблица транспозиции».

В качестве примера того, как использовать запоминание для повышения производительности алгоритма, следующий пример выполняется примерно в 300 раз быстрее для этого конкретного теста. Раньше это занимало ~ 200 секунд; 2/3 запомнил.

class Slice:

    __slots__ = 'prefix', 'root', 'suffix'

    def __init__(self, prefix, root, suffix):
        self.prefix = prefix
        self.root = root
        self.suffix = suffix

################################################################################

class Match:

    __slots__ = 'a', 'b', 'prefix', 'suffix', 'value'

    def __init__(self, a, b, prefix, suffix, value):
        self.a = a
        self.b = b
        self.prefix = prefix
        self.suffix = suffix
        self.value = value

################################################################################

class Tree:

    __slots__ = 'nodes', 'index', 'value'

    def __init__(self, nodes, index, value):
        self.nodes = nodes
        self.index = index
        self.value = value

################################################################################

def old_search(a, b):
    # Initialize startup variables.
    nodes, index = [], []
    a_size, b_size = len(a), len(b)
    # Begin to slice the sequences.
    for size in range(min(a_size, b_size), 0, -1):
        for a_addr in range(a_size - size + 1):
            # Slice "a" at address and end.
            a_term = a_addr + size
            a_root = a[a_addr:a_term]
            for b_addr in range(b_size - size + 1):
                # Slice "b" at address and end.
                b_term = b_addr + size
                b_root = b[b_addr:b_term]
                # Find out if slices are equal.
                if a_root == b_root:
                    # Create prefix tree to search.
                    a_pref, b_pref = a[:a_addr], b[:b_addr]
                    p_tree = old_search(a_pref, b_pref)
                    # Create suffix tree to search.
                    a_suff, b_suff = a[a_term:], b[b_term:]
                    s_tree = old_search(a_suff, b_suff)
                    # Make completed slice objects.
                    a_slic = Slice(a_pref, a_root, a_suff)
                    b_slic = Slice(b_pref, b_root, b_suff)
                    # Finish the match calculation.
                    value = size + p_tree.value + s_tree.value
                    match = Match(a_slic, b_slic, p_tree, s_tree, value)
                    # Append results to tree lists.
                    nodes.append(match)
                    index.append(value)
        # Return largest matches found.
        if nodes:
            return Tree(nodes, index, max(index))
    # Give caller null tree object.
    return Tree(nodes, index, 0)

################################################################################

def search(memo, a, b):
    # Initialize startup variables.
    nodes, index = [], []
    a_size, b_size = len(a), len(b)
    # Begin to slice the sequences.
    for size in range(min(a_size, b_size), 0, -1):
        for a_addr in range(a_size - size + 1):
            # Slice "a" at address and end.
            a_term = a_addr + size
            a_root = a[a_addr:a_term]
            for b_addr in range(b_size - size + 1):
                # Slice "b" at address and end.
                b_term = b_addr + size
                b_root = b[b_addr:b_term]
                # Find out if slices are equal.
                if a_root == b_root:
                    # Create prefix tree to search.
                    key = a_pref, b_pref = a[:a_addr], b[:b_addr]
                    if key not in memo:
                        memo[key] = search(memo, a_pref, b_pref)
                    p_tree = memo[key]
                    # Create suffix tree to search.
                    key = a_suff, b_suff = a[a_term:], b[b_term:]
                    if key not in memo:
                        memo[key] = search(memo, a_suff, b_suff)
                    s_tree = memo[key]
                    # Make completed slice objects.
                    a_slic = Slice(a_pref, a_root, a_suff)
                    b_slic = Slice(b_pref, b_root, b_suff)
                    # Finish the match calculation.
                    value = size + p_tree.value + s_tree.value
                    match = Match(a_slic, b_slic, p_tree, s_tree, value)
                    # Append results to tree lists.
                    nodes.append(match)
                    index.append(value)
        # Return largest matches found.
        if nodes:
            return Tree(nodes, index, max(index))
    # Give caller null tree object.
    return Tree(nodes, index, 0)

################################################################################

import time
a = tuple(range(50))
b = (48, 11, 5, 22, 28, 31, 14, 18, 7, 29, 49, 44, 47, 36, 25, 27,
     34, 10, 38, 15, 21, 16, 35, 20, 45, 2, 37, 33, 6, 30, 0, 8, 13,
     43, 32, 1, 40, 26, 24, 42, 39, 9, 12, 17, 46, 4, 23, 3, 19, 41)

start = time.clock()
old_search(a, b)
stop = time.clock()

print('old_search() =', stop - start)

start = time.clock()
search({}, a, b)
stop = time.clock()

print('search() =', stop - start)

Ссылка: Как можно применить запоминание к этому алгоритму?

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

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

3! это проблема сама по себе, но это также подзадача для n! где n> 3, например 4! = 4 * 3! Функция, вычисляющая факториалы, может работать намного лучше с мемоизацией, потому что она всегда вычисляет только 3! один раз и сохраните результат внутри хеш-таблицы. Когда попадается 3! и снова он будет искать значение в таблице, а не пересчитывать его.

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

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

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

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

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

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

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

Если вы знаете свой диапазон значений во время компиляции, скажем, потому что вы используете n! а n - 32-битное целое число, тогда лучше использовать статический массив.

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

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

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

Я думаю, что в основном все рассмотрели основы мемоизации, но я приведу вам несколько практических примеров, где можно использовать moization чтобы делать некоторые удивительные вещи (imho):

1. В C # вы можете отразить функцию и создать для нее делегат, затем вы можете динамически вызывать делегат ... но это ДЕЙСТВИТЕЛЬНО медленно! Это примерно в 30 раз медленнее, чем прямой вызов метода. Если вы запомните вызов метода, вы можете сделать вызов почти таким же быстрым, как вызов метода напрямую.
2. В генетическом программировании это может уменьшить накладные расходы, связанные с многократным вызовом одной и той же функции с аналогичными входными параметрами для сотен и тысяч экземпляров в популяции.
3. При выполнении деревьев выражений: вам не нужно постоянно переоценивать дерево выражений, если вы уже запомнили его ...

Конечно, есть намного больше практических примеров где можно использовать мемоизацию, но это лишь некоторые из них.

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

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

Это часто важный прием при решении задач с помощью динамического программирования.

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

Еще одно применение: Перечислите факториалы чисел от 0 до 100. Вы не хотите вычислять 100! используя 100 * 99 * ... * 1. Вы уже вычислили 99! , поэтому повторно используйте этот ответ и просто умножьте 100 на 99! . Вы можете запомнить ответ на каждом из этих шагов (работая от 1 до 100), чтобы сэкономить значительное количество вычислений.

Для примера, для моей задачи по решению сетки выше (задача из задачи по программированию):

Мемоизированный:

real  0m3.128s
user  0m1.120s
sys   0m0.064s

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

real 24m6.513s
user 23m52.478s
sys   0m6.040s

На мой взгляд, вычисления Фибоначчи и факторные вычисления - не лучшие примеры. Мемоизация действительно вступает в свои права, когда у вас есть:

1. Огромный диапазон потенциальных входных данных для рассматриваемого вычисления, но диапазон все еще четко ограничен и известен
2. Вы заранее знаете, что любое фактическое использование программы будет использовать только небольшое подмножество возможных входных данных для ваших вычислений (Фибоначчи и факториал терпят неудачу)
3. Вы не знаете , какие именно входные данные будут использоваться во время выполнения, и, следовательно, какие конкретные результаты потребуются быть мемоизированным (Фибоначчи и факториал тоже терпят неудачу, до определенной степени)

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

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

Обратите внимание, что многое из этого может быть вероятностным (или интуитивным) - конечно, кто-то может попробовать все 10 ^ 13 возможных входных данных для вашего магического расчета, но вы знаете, что на самом деле это не так. Если они это сделают, накладные расходы на запоминание фактически не принесут им пользы. Но вы вполне можете решить, что это приемлемо, или позволить в таких обстоятельствах обойтись без воспоминаний.

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

В некоторых прошивках, которые я написал, одна часть программы принимает чтение из АЦП, которое может быть любым числом от 0x000 до 0xFFF , и вычисляет вывод для некоторых другая часть программы. Этот расчет также требует набора настраиваемых пользователем чисел, но они считываются только при запуске программы. Этот расчет производит большое впечатление при первом запуске.

Заблаговременное создание таблицы поиска - это нелепо. Входной домен - это декартово произведение [ 0x000 , ..., 0xFFF ] и (большой диапазон значений с плавающей запятой) и (другой большой диапазон ...) и. .. Нет, спасибо.

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

Учитывая определение «медленно меняющихся условий», которое ожидает типичный пользователь, это значение АЦП установится на определенное значение и останется в пределах примерно 0x010 от установленного значения. Какое значение зависит от условий.

Таким образом, результат расчета может быть запомнен для этих 16 потенциальных входов. Если условия окружающей среды действительно изменяются быстрее, чем ожидалось, то "самое дальнее" чтение АЦП из самого последнего отбрасывается (например, если я кэшировал 0x210 в 0x21F, а затем я прочитал 0x222, я отбрасываю результат 0x210 ).

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